不确定DNA 有限状态自动机在基因网络中
的应用#
李汪根*
基金项目：国家自然科学基金（61070060），安徽省高校自然科学研究重点项目（KJ2010A140）
作者简介：李汪根，（1973-），男，副教授，主要研究方向为生物计算和生物信息学. E-mail:
xchen@mail.ahnu.edu.cn
5 （安徽师范大学数学计算机科学学院，安徽 芜湖 241003）
摘要：传统电子计算机产生的随机数是伪随机数，因而其随机算法不是严格意义上的随机计
算。由于生化反应的随机性，随机分子生物计算机比确定性分子生物计算机更适合解决随机
性问题。本文将不确定DNA 有限状态自动机应用于基因表达网络，分析了基因表达网络的不
确定性，给出了不确定DNA 有限状态自动机各组成部分编码的形式描述。本文的研究可为
10 DNA 计算在生物信息学中的应用提供新的思路。
关键词：DNA 计算机；不确定有限状态自动机；DNA 编码
中图分类号：TP384, TP311.12
The Application of Non-deterministic DNA Finite State
15 Automaton in Gene Expression Networks
LI Wanggen
(Mathematics and Computer Science School, Anhui Normal University, AnHui WuHu 241003)
Abstract: The random number generated by traditional computer is a pseudo-random numbers, so
it is not strictly a random algorithm on random calculations. Because of the randomness of
20 biochemical reactions, random molecular biology computer is more suitable for random issues
than the deterministic solution. This paper proposed a non-deterministic DNA finite state automata
used in gene expression networks, and described the DNA encoding of the components formally.
This study provides new ideas for DNA computing in the application of bioinformatics.
Keywords: DNA computer; Non-deterministic Finite State Automaton; DNA encoding
25
0 引言
基因调节机制是一个非常复杂的过程[1-4]。生物信号通过一对一的调节机制逐渐地被转
移和扩散到下游基因，从而达到调控基因表达的目的。从细胞生物学的观点来看，基因表达
水平影响基因调节过程。在不同的基因调节机制下，基因表达水平的表达水平也不尽相同。
30 正常细胞中的基因通过多步调节机制来控制细胞生长、差异、重生和细胞凋亡过程。癌症是
由于许多外界因素导致基因调节机制的改变。基于传统的观点，基因的调节状态可以被简化
地归为激活和抑制两类。
基因网络的行为关系到基因之间的相互作用。从生物观点来看，基因网络表示了基因在
染色体中的顺序、功能和相互作用；从逻辑的观点来看，基因网络包括表达基因之间的二元
35 甚至几元关系。
DNA 计算机是分子范围内的可编程计算机，其输入、输出、软件和硬件都由生物分子
构成[5-9]。DNA 计算机有望以一种生物分子内在的形式来直接分析生物信息学问题，而不需
要转换成电子计算机的信号[10, 11]。2004 年， Benenson 等人就设计了确定性DNA 自动机用
于疾病体外分子诊断[12]。通过对疾病分子信标的识别和分析，一种预先编程的称作分子药
40 物的反义DNA 链会释放，以破坏疾病基因的表达。由于分子生物系统固有的随机性，随机
 分子生物计算机比这种确定性分子生物计算机可能更适合解决这类问题。
1 基因表达网络的不确定有限状态自动机模型
为了搞清基因表达之间的相互制约关系，Peter 等人采用了其有正（positive）、负
（negative）控制的基因网络的一个形式化模型-有限状态自动机[13,14]。具体地讲，基因被激
45 活后，将在一段时间后出现产生物蛋白质；基因被抑制后，在一段时间后停止出现蛋白质。
如果把单个基因的状态看成on 和off，产生物（例如蛋白质）的状态表示成absent 和present，
就得了一个基因的逻辑模型。进一步地，把单个基因X 的状态on 和off 以及X 的产生物状
态present 和absent 看作自动机的输入，并分别用符号α、γ、β 和λ 表示，可进一步构造其
对应的有限状态自动机。
50 Peter 等人的模型用来表达基因网络行为有局限性：在基因和其产生物之间，未必不会
有意外发生，比如可以是基因状态的异常，也可以是产生物的异常。要描述这种异常，首先
要引入异常状态，其次建立不确定有限状态自动机模型。
一个基因X 及其产生物蛋白质组成的非确定型有限状态自动机G=（Q,Σ,Δ,q,F），其中
状态集合Q={0,1,2,3,4 }，其中4 为异常状态；输入字符集合Σ={α,γ,β,λ}；初始状态q={0}；
55 终止状态集合F={Ф}。其所对应的不确定有限状态自动机如下图1 所示。
0 2
3
4
1
α
α
γ
γ
γ
α
β
λ
γ,β
λ,α
图1 基因X 表达所对应的不确定有限状态自动机
2 不确定DNA 有限状态自动机
60 在确定有限状态自动机中，对于每一个状态-符号组合，在状态转移规则集合中最多有
一个可以选择。下图2 给出了随机有限状态自动机的形式描述[15]，其中S0 是初始状态。相
对于确定有限状态机而言，随机有限状态自动机都会按照一定的概率潜在地选择状态转移规
则集合中的每一条规则，也就是说每一条规则都有一个预先定义的概率来刻画，而对于一个
给定的状态-符号组合，其对应状态转移规则的概率和为1。例如，在S0 状态下，读取字符
65 a 的两条规则选取的概率分别为0.8 和0.2。不确定有限状态自动机的输出结果是通过计算到
达同一最终状态的所有可行状态转移规则的概率和得到每一个最终状态的概率。图3 给出了
该不确定有限状态自动机的计算过程的形式描述[15]。
 70
图2 不确定有限状态自动机形式描述
图3 不确定有限状态自动机的计算过程
75
Shapiro 等人在2004 年提出了不确定DNA 有限状态自动机的实现方法[15]。该方法中通
过调整表示每一个状态转移规则的DNA 分子片段的摩尔浓度来表征每一条转移规则的潜在
概率。实验结果表明：通过这种方式刻画的转移分子的概率相对于输入DNA 片段分子的浓
度和软件分子片段的浓度具有很强的鲁棒性；对于多步计算，预测的理论值和实际结果能够
80 很好的吻合。下图4 给出了这种不确定DNA 有限状态自动机计算竞争过程的形式描述[15]。
 图4 不确定DNA 有限状态自动机的随机选择过程
Shapiro 等人在文献[15]中指出：当输入分子的浓度很大时，特定最终状态的概率可以直
85 接用表征该状态的输出分子的浓度来度量。通过调整转移分子的浓度可以达到调整转移概率
的目的。由于在生物实验中，实验条件的微小变化可能会引起实验结果的截然不同，文章作
了大量的实验，找到了转移分子的相对浓度和转移分子的概率之间的函数关系。
3 不确定DNA 有限状态自动机的实现
下面我们讨论上述基因表达网络对应的不确定DNA 有限状态自动机模型的建立[14]，包
90 括模型中完成状态转移的状态转移规则，输入符号及状态转移规则的形式描述等。
（1）状态转移规则
对应于上述不确定有限状态自动机模型，其状态转移规则如下图5 所示。
T1: ( 0, α ) 1
T2: ( 0, α ) 4
T3: ( 1,γ ) 0
T4: ( 1,γ ) 4
T5: ( 1, β ) 2
T6: ( 1, β ) 4
T8: ( 2, γ ) 4
T7: ( 2, γ ) 3
T9: ( 3, α ) 2
T10: ( 3, α ) 4
T11: ( 3, λ ) 0
T12: ( 3, λ ) 4
95 图5 状态转移规则
（2）编码的形式描述
1）输入符号编码
这里我们选择FokI 为限制性内切酶。FokI 限制性内切酶的识别位点是5’-GGATG-3’, 酶
100 切位点是（9，13），酶切后会形成一段4bp 的粘性末端。这个粘性末端编码了不同的状态
和符号的组合。该粘性末端在连接酶作用下与带有互补粘性末端的相应的转移分子粘连，形
成一段新的DNA 片段，编码新的状态。对于图5 所示的有限状态自动机，我们设计输入符
号α 为5’-ATCACGTC-3’ ， 输入符号γ 为5’-ACGGTACA-3’ ， 输入符号β 为
5’-AGCGTAGC-3’， 输入符号λ 为5’-ACGGATCC-3’，终止符号t 为5’-GTACCTTT-3’。
105 2）状态转移规则编码
输入分子在FokI 内切酶的消化下会形成含4bp 粘性末端的片段。状态转移分子应含有
与对应的输入分子酶切片段互补的粘性末端，以便在连接酶的作用下形成代表新状态的
DNA 片段以完成状态的转移。
我们在编码这些状态转移规则时，根据FokI 内切酶的特点，将0，1，2，3 这四种状态
 110 分别对应输入字符从左至右开始的四个位置，以表示<状态\符号>的不同组合。由于在设计
输入字符的编码时已经考虑组合的不同，所以不会产生相同的粘性末端。
4 结论
本文我们研究了不确定DNA 自动机的实现方法。给出了不确定DNA 有限状态自动机
在基因表达网络上的应用。这些成果表明在DNA 计算领域，完全有可能以生物分子内在固
115 有的形式来处理生物信息学问题，而不需要像现有电子计算机解决生物信息学问题那样，将
生物分子转换成数字信号。本文的研究成果有望让DNA 计算在生物信息学上发挥重要作用。