（计算机软件与理论专业论文）dna计算的模型与用于解决np难问题的算法设计.pdf

d n a 计算的模型与用于解决n p 类问题的算法设计 摘要 本文综述了生物计算中的热点d n a 计算，给出了d n a 计算的一些实际算 法和模型。在第一章中，简述了d n a 的结构和d n a 计算所需的生物技术；第 二章中，说明了以d n a 为计算介质的计算具有完备性的基础：第三章总结了 目前已有的d n a 计算模型，给出了它们的图灵等价性的主要结论，最后设计 了一个不用限制性酶，模拟图灵机运行的一个d n a 模型，这个模型可以有效的 模拟非确定图灵机；在最后一章，给出了建立在去除操作基础上解决n p 完全 和n p 优化问题的算法，这类算法的时间复杂度一般是线性的。 关键词：d n a 计算；图灵机；模型女算欺 d n a 计算的模型与用于解决n p 类问题的算法设计 a b s t r a c t t h i st h e s i sg i v e sas u r v e yo fd n a c o m p u t i n g ，w h i c hi st h em a i ns t u a y - i n t e r e s t s o fb i o c o m p u t i n g ，a n dg i v e ss o m ep r a c t i c a la l g o r i t h r a sb yd n a c o m p u t i n g i nt h e f i r s tc h a p t e r ，s u m m a r i z e st h eb i o - t e c h n i q u e su s e di nd n a c o m p u t i n g ；i nt h es e c o n d c h a p t e r ，s h o w st h eb a s i so ft h ec h a r a c t e r i s t i co f c o m p l e t e n e s s o fc o m p u t i n gb a s e d o nd n am o l e c u l a r ；i nt h et h i r dc h a p t e r ，l i s t st h em o d e l sw h o s ea b i l i t i e sa r ee q u a lt o t u r i n gm a c h i n e ，a n dg i v e sam o d e ls i m u l a t i n gt u r i n gm a c h i n ew i t h o u tr e s t r i c t i o n e n z y m e ；i nt h el a s tc h a p t e r ，g i v e st h ea l g o r i t h m sf o rn p o a n dn p c p r o b l e m sb a s e d o nr e m o v eo p e r a t i o n w h i c hi sr e g a r d e da s “e r r o rr e s i s t a n t k e yw o r d s ：d n ac o m p u t i n g ，t u f i n gm a c h i n e ，m o d e l ，a l g o r i t h m d n a 计算的模型与用于解决n p 类问题的算法设计 1 “l 日! j 吾 摩尔定律预言单位平方英寸芯片的晶体管数目每过1 8 到2 4 个月就将增加 一倍。过去的几十年中，晶体管计算机的发展速度确实遵从了摩尔定律。但晶 体管尺寸有一个物理性质决定的极限。人们预测，到2 0 1 0 年左右，晶体管的尺 寸就将达到这个极限，任何试图继续减小晶体管尺寸的努力都将带来不可忍受 的计算错误率和能量消耗。因此人们在试图设计新型的计算模型，在计算速度 上与晶体管计算机相比，能有质的飞跃。量子计算和生物计算就是其中的代 表。 生物计算的研究还处于初始阶段，还很难预测这种计算何时能达到商业应 用水准，甚至不能保证这种计算能够完全代替传统的计算机。但生物分子具有 某些良好性质，使得以生物分子为介质的计算具有诱人的发展前景。生物计算 中，最有代表性的是d n a 计算。d n a 计算有以下优点： 每个d n a 分子都可以看作是一个处理器，可以同时进行计算，因此 d n a 计算有大规模的并行性。 d n a 分子的互补性质保证了d n a 计算是具有完备性的，即理论上， 任何图灵机可以完成的计算都可以通过d n a 计算实现。 d n a 是高密度的存储介质，因为组成d n a 分子的核苷酸的尺寸是纳 米级的，可以认为d n a 计算中存储一位信息所需的空间是纳米级 的。 但若想达到实用水平，直至有商业价值的阶段，还有许多问题需要克服。 这些问题中主要有生物操作结果的不精确性，导致的计算错误累积，使计算失 去意义；d n a 分子间的通信；找到d n a 计算特别有优势的应用领域：建立在 计算过程中不需要干预的可编程模型等。 d n a 计算的模型与用于解决n p 类问题的算法设计 第一章d n a 的结构与操作 d n a 的结构和性质是d n a 能够实现计算的基础，d n a 计算的过程就是一 系列的生化反应，可以把实现完整功能的反应定义为d n a 计算中的操作。执 行这些操作，往往需要一些人为干预，但只要满足一定条件，生化反应自动实 现。溶液中的每一个分子的改变是同时进行的，具有很高的并行性，因此这些 操作也称为集合操作，这里集合是指溶液中所有d n a 分子根据编码规则所代 表的集合。 1 1d n a 的结构 1 1 1 d n a 的组成 d n a 是脱氧核糖核酸的简称，它是存在于细胞内部的遗传物质。一条 d n a 序列是由一系列的核营酸顺序连接在一起组成的，这些核苷酸内部含有四 种不同的碱基，分别是腺嘌呤( 4 ) ，鸟嘌呤( g ) ，胞嘧啶( c ) ，胸腺嘧啶 ( r ) 。也用这四种碱基表示相应的核苷酸。 1 1 2w a t s o n c r i c k 互补 d n a 链是有极性的，因此它的两端是不同的，一条d n a 序列两端分别记 为3 端和5 端。如果两条d n a 单链满足3 端和5 端相对应，彳与r 相对应，c 与g 相对应，就称这两条单链是w a t s o n - c r i c k 互补的。w a t s o n - c r i c k 互补的两 条单链可以结合成为一条d n a 双链。用个表示从5 端到3 端，j ，表示从3 端 到5 端，用0 表示从5 端到3 端的双链，例如： ta c c t g c 表示d n a 单链5 - a c c t g c 一3 山a c c t g c 表示d n a 单链3 - t g g a c g 一5 。爿。刃u c 表示。n a 双链分子3 5 i _ - r a g c g c a t c g g c 一- 5 3 ，它是由上面w a t s 。n c r i c k 互补的两条单链结合而成的。 如果一条d n a 链所含的碱基数目较少，又可称这个链为称为寡核苷酸。 2 d n a 计算的模型与用于解决n p 类问题的算法设计 1 2d n a 计算中常用到的酶 酶是一种蛋白质结构，某些操作必须在酶的作用下才能完成。在d n a 计 算中，常用到以下几种酶。 1 限制性内切酶：它能够识别特定的碱基序列，并在相应的位置切断 d n a 序列。这个相应的位置可能是识别的碱基序列所在的位置，也 可能是与识别的碱基序列有一定距离的位置。限制性内切酶一般简称 为限制性酶。见图1 gaatt c q cttaa g b 3 5 ， j 内切酶 、 r 5 ， 3 5 3 。ic g taa i 1 aa t t 暑l b 图1 ：限制性内切酶 2 核酸外切酶：它能够从d n a 序列的端( 3 端或5 端) 开始，切除碱 基。 3 聚合酶：在一个d n a 序列的一端上添加核苷酸，使序列加长。 4 连接酶：使两条具有互补粘性末端的d n a 链连接为一条。粘性末端 是指双链的d n a 分子末端有部分是单链结构，因此能与互补的单链 结构粘和在起。有互补粘性末端的两条链形成稳定的双链，要用到 连接酶。见图2 。 d n a 计算的模型与用于解决n p 类问题的算法设计 c 【一 j c c g g g g g o c c f c l 3 jl 氢键o h s ， o 弋尸 s ， c l j ccggg gggcc n c 1 3 常用的d n a 操作 图2 ：连接酶 d n a 计算中常用到以下d n a 操作，它们当中有的是只与一种生化反应相 对应简单的操作，如熔解，切断，连接等。有的是需要多种生化反应的复合操 作，如抽取，去除，复制等，有的是人工干预的操作，如合并。这些操作用于 设计d n a 计算模型，也用于给具体问题设计d n a 算法。 熔解( m e l t i n g ) ：在一定高温条件下，d n a 双链将熔解成两条w a t s o n - c r i c k 互补的单链( 图3 ) 。 退火( a n n e a l l i n g ) ：它是熔解的逆过程，通过缓慢降温，熔解得到的单链将 再次结合为双链( 图4 ) 。 合成( s y n t h e s i s ) ：生成一个长度为多项式的链。 杂化( h y b r i d ) ：不同来源的单链互补，形成部分双链结构。例如p c r 中引 物与单链的结合。 切割( c u t ) ：限制性酶在特定位置上把一条d n a 链切割成为两条( 图1 ) 。 延长( 1 e n g t h e n ) 用聚合酶给d n a 分子一端添加核苷酸，使得d n a 链加 长。 缩短( s h o r t e n ) ：用核苷酸外切酶从d n a 链的端切除核苷酸。 分离( s e p a r a t e ) 用凝胶电泳的方法使d n a 链按长度不同分离。 4 d n a 计算的模型与用于解决n p 类问题的算法设计 图3 ：熔解 图4 ：退火 连接( p a s t e ) ：用连接酶使得两个有互补粘性末端的d n a 链连接成为一个 d n a 分子( 图2 ) 。 标记( m a r k ) ：用与d n a 链一部分互补的寡核苷酸与d n a 链结合( 杂 化) ，使至少有一次特定序列出现的d n a 链部分变为双链结构。 破坏( d e s t r o y ) ：利用限制性酶或外切酶，破坏被标记了的链。 检澳l j ( d e t e s t ) ：用凝胶电泳的方法检测一个试管中是否含有d n a 链。 抽取( e x t r a c 0 ：将含有特定子串的d n a 链提取出来。抽取操作是用亲和纯 化法实现的。 合并( u i l i o n ) ：将几个试管中的的d n a 溶液倒入一个试管，使得这个试管将 含有原来几个试管中的所有d n a 分子序列 去除( r e m o v e ) ：首先标记含有特定序列的d n a 链，然后破坏被标记的链， 使剩余的链都不包含所标记的特定的序列。这是一个可以得到很精确结果的操 作，可以认为这个操作是抗错的。 复带i j ( c o p y ) ：利用p c r 法，复制d n a 链。使用p c r 法复制，将使链的数 目成指数速度增长，因此复制的效率是非常高的。见图5 。复制反应需要个 单链d n a 作为模板，和两个寡核苷酸作为引物，在引物的一端按与模板互补 的规则，添加核苷酸，直到与模板完全互补形成完整的双链为止。复制的具体 过程如下： 过程1 ：把要复制的d n a 分子熔解成为两条单链，这两条单链都有一个与引物 互补的端 过程2 ：在熔解了的溶液中加入分别与两端互补的两种引物，通过杂化作用， 使得它们与单链结合。 d n a 计算的模型与用于解决n p 难问题的算法设计 过程3 ：在聚合酶的作用下，以单链为模版，使得没有成为双链结构的部分不 停加长，直至形成完整的双链结构后结束。 这样一个d n a 分子就变为两个，完成一步复制。 几l r t t _ r 1 n 【j j j i 【：【l l u y l j l ji二 二 l j l ji y 过程1 b 几_ r 丁厂 丌1 一几 卜- l 肛b _ ul j l 二二一 b 广t t t 几t 可 y 小化 y 一弓i 物 l b 一弓i 物 l il jl j：l jl jl y 过程2 斗 ul jl ：l jl j y 胪酶 b r 邢 【j j 1 1 j 1 【j j j j y 过程3 图5 ：d n a 分子的复制 本章首先简单的介绍了d n a 的结构【5 】，并给出d n a 计算中常用的操作 1 1 ，2 ，5 】。 6 d n a 计算的模型与用于解决n p 类问题的算法设计 第二章d n a 实现计算的基础 2 1 图灵机与r 语言 图灵机代表了人们目前所能认识的计算的最高层次，还没有发现任何计算 模型的计算能力，跟图灵机相比，有本质上的提升。c h u r c h 图灵论断就体现了 在目前人们的认知范围内，图灵机具有最高计算能力。任何其他的模型，都以 是否能够完成图灵机所能完成的计算作为是否具有完备性的判定标准。因此， 首先要明确d n a 计算模型是否具有完备性，也就是要明确，通过操纵d n a 分 子得来的计算模型，是否能够完成任意图灵机的计算功能。 能够被图灵机所接受的语言是递归可枚举( 兄d 语言，因此可以通过证明一 个模型能够产生所有r e 语言来说明这个模型具有完备性。 2 2d n a 本身具有“完备性” 以d n a 分子为介质的计算，其具有的完备性似乎是“天然”的，这种天 然的完备性根源于d n a 双链的w a t s o n c r i c k 互补性与嬲语言的相似性。 2 2 1 g s m g s m 是“g e n e r a l i z e ds e q u e n t i mm a c h i n e ”的简称，是一种顺序转换机，它可 以看作是一个有输出的有限自动机( 见图6 ) 。 图6 ：g s m 可以用g = ( k ，k ，f ，占) 表示g s m ，其中k 和分别是输入字符表和输出字 符表，占：k k 寸p r ( + k ) 。如果对任意j k ，口k ，都有 c a r d ( 8 ( s ，口) ) 1 ，那么就说 g是确定的 。如果 d n a 计算的模型与用于解决n p 类问题的算法设计 ( z ，s ) 6 ( s ，口) ，其中s ，s k ，口k ，y k ，x ，z 。那么就记( x ，j ，缈) ( 船，s ，y ) 。定义g ( w ) = z i ( 兄，w ) f ( z ，j ，旯) ，j f 。 2 2 2t s 语言与其通用性 孵语言的字符表是 o ，1 ，石，t ，w 为字符表 0 ，1 上的一个字，设万是字符 o ，l 上的串，且面与w 互补。例如w = 0 0 1 0 1 ，面= 0 0 10 1 。s h u f f i e ( w ，确表 示在不改变w 和万中的字符顺序的条件下，混合w 和筇所得到的字的集合。 嬲语言包含所有s h u f f l e ( w ，订) 中的字，其中w 是所有 o ，1 l 上的字。下面是 一个判断 o ，1 ，o ，1 上的串x ，是否是蛮语言中的一个字的方法。 1 从x 中移走所有石，t 字符。剩下的串为一 2 从x 中移走所有0 ，1 字符，并去掉剩下字符顶部的横线，得到的串为x ” 如果x = 一，那么x 就是弼语言的一个字。 定理2 1 ：对任意一个肛中的语言厶都存在一个g s mg 。，使得l = g 。( t s ) 。 这个定理中，巧是固定的，不同的语言工，有不同g ，的与之对应。g ，可 以看作是个输入输出工具。这个定理体现了擂语言的通用性，这里通用性是指 从阿语言出发，可以得到任意r e 中的语言。 2 2 3w a t s o n c r i c k 互补与t s 语言 d n a 链的w a t s o n - c r i c k 互补特性，使得以d n a 为介质的计算，具有一种 “天然的”完备性。这种完备性主要来源于w a t s o n c r i c k 互补与稻语言的相似 性。嬲语言的字符集是0 ，1 以及与0 有互补关系的石和与l 有互补关系的t 。而 d n a 分子是由四种核苷酸组成，而且他们分为互补的两组： ( 4 ，r ) ，( c jg ) 。 如果仅仅表示信息的编码，两个字符o ，l 已经足够了，而他们的互补字符西，t 是用来支持硒语言上的字的计算的。这似乎可以作为在d n a 分子中有四种核 苷酸的数学解释。如果只有三种核苷酸，那就不够形成巧语言，而如果多余四 个，就会有冗余。 d n a 的字符表是乜，g ，t ，c ，可以认为： a = 0 ，g = 1 ，r = 百，c = t 这样( 0 ，石) ，( 1 ，t ) 为两个互补关系，就和w a t s o n - c r i c k 互补关系一致了。下面 一个例子体现了嬲语言与d n a 双链的联系。 一个d n a 双链：姗a g c7 1 a 脚t c a 4 t ，可以表示船0 1 1 百0 黧0 1 0 。搠颐序 的从上下两个序列取字符，得到的串一定是巧语言里的字。上面的双链得到串 d n a 计算的模型与用于解决n p 类问题的算法设计 一0 0 0 0 1 丁t 1 0 西西0 11 0 0 0 0 。这样，从任意d n a 双链分子出发，都能够得到 属于t s 语言的串。 如果d n a 双链，一条链中仅含有嘌呤( 爿，g ) ，而另一条仅含有嘧啶 ( e r ) ，那么以d n a 为介质的计算具有完备性。在这种假设下，可以认为一条 单链上都是0 ，1 字符，而另一条单链上都是石，t 字符。这种双链中的一条仅 含有嘌呤，而另一条仅含有嘧啶的情况在自然界中并不存在，但可以用另外一 种方法达到同样的效果。当a ，t 出现在上层链中时，都把它们认为是o ，而当 它们出现在下层链中时，就认为是0 ：同样的，当c ，g 出现在上层链中时， 认为是l ，而当它们出现在下层链时，就认为是1 。这样，当读一条d n a 链时， 以完全独立的速度读上下两层链，得到的串都是属于孵的。如果考虑所有的 d n a 双链，那么就能够得到所有属于嬲的串。因此说，d n a 分子的w a t s o n c r i c k 互补特性保证d n a 双链能够与硌一样具有通用性，而以d n a 分予为介 质的计算将具有完备性。基于d n a 计算的一个很重要的任务，可能就确定适 合d n a 计算生物性质的g s m 。 2 3w a t s o n c r i c k 有限自动机模型 经典的有限自动机是与正则文法密切相关的，而输入为满足w a t s o n c r i c k 互补性质的自动机，体现了w a t s o n - c r i c k 与粥语言的关系。 2 3 1w a t s o n c r i c k 有限自动机 与传统的自动机不同，w a t s o n c r i c k 自动机的工作带是w a t s o n - c r i c k 带， w a t s o n c r i c k 带是一个双层带，其中存储集合阡w 。( 矿) 中的个元素。这里v 是一个字母表，p e y y 是一个互补关系。w k p ( v ) = e y v i ，其中 眵 。= ： h 。n 。，a ，0 。w a t s 。n - c d c k 有限自动机的如图，所示。 图7 ：w a t s o n c r i c k 自动机 9 d n a 计算的模型与用于解决n p 类问题的算法设计 w a t s o n c r i c k 自动机的工作带中存储着w k 。( y ) 中的一个元素。初始条件 下，w a t s o n c r i c k 有限自动机处在在状态s d ，两个指针头都在最左端，根据转移 规则，两个指针分别向右移，状态也发生转移，当两个指针都移到带尾并且进 入某个终止状态，自动机停止并接受带上的序列。 w a t s o n c r i c k 有限自动机可以用m = ( y ，p ，k ，s o ，f ，万) 表不，其中p v v 是一个对称关系，占：k f ；：1 斗p ( k ) 是一个转移表，表中只有有限个转移 规则，即仅对有限个元组( j ，墨y ) k y + y ，有占( j ，f 。1 ) m 。y 是输入字 符表，p 是y 上的互补关系。占( j ，f 。11 ) 的含义是：在状态s ，自动机在上 层串上读过x 。，在下层串读过x ：，然后进入状态s 。 对有限自动机来讲，m 的转移规则一8 ( s ，【x 11 ) 也可写为重写规则 工2 s 。i x x ：，l 一、f x x ：，i 在表示w a t s o n - c r i c k 有限自动机时，把字母表v 放在最前面，然后就是对 称的互补关系p ，然后才是状态集。之所以这样表示，是因为( v ，p ) 是w a t s o n - c r i c k 有限自动机和普通自动机的根本区别所在。w a t s o n - c r i c k 自动机可以是确 定的或是非确定的。 对于一个n - c 础有限自批髁( 姒圳玢( 升 麓斗吲n 镪，那么当切仅射毗吣，有如下自动机 的转移： 睁z j ( 驰 一( ： 2 3 2w a t s o n c r i c k 有限自动机的语言 被w a t s o n - c r i c k 有限自动机所识别的语言有多定义方法，第一种是根据 w k 。( y ) 上层的串定义： “耻卜, o l w ：l j 咖其峨州，卧哪y ) ) d n a 计算的模型与用于解决n p 类问题的算法设计 同样可以根据下层的串来定义。还有一种定义w a t s o n - c r i c k 自动机语言的 方法，不是用识别的串的方法，而是通过转移序列来定义。 可以把一个w a t s o n c r i c k 自动机的转移规则改写为重写规则，就得到用 m = ( y ，p ，k ，s 。，f ，p ) 表示的w a t s o n c r i c k 有限自动机( 这里p 是重写规则) ， 制定一个从p 到一个集合l a b 的映射e ：p 哼l a b 作为标签方案。l a b 是标签集 合。对于一个计算盯：s o w j + w sr ，其中w w k 。( y ) 5 ，f ，用p ( 盯) 表示盯 的控制字，也就是在盯中用到的与转移规则序列相应的标签序列。用这种标签 的方法，我们可以定义语言： l d ，( m ) = e ( c r ) l 仃：s o w j w sr ，其中sr f ，w w k p ( y ) 。 定义：三。( m ) ，口u ，c t r 是w a t s o n c r i c k 有限自动机m 所识别的语言。 2 3 3w a t s o n c r i c k 有限自动机的分类 根据限定条件，把w a t s o n c r i c k 有限自动机分为以下类： k = f = k 的，则称自动机是单状态的； k = f ，则称是全终止状态的： 对于所有s ( 乏 一( ：1 一p ，都有x 。；兄或x ：= 五，则称是简单自动 机。 对于所有s ( 乏 _ ( 主 一p ，都有k 划一，则称是z - 受限自动机。 如果自动机是单状态的，则在表示自动机时，可以省略k ，f ，转移规则 的形式也可改为f 一1 。用aw k ( 口) ，n w k ( 口) ，f w k ( a ) ，s w k ( 口) ，l w k ( a ) ， 口协，c 护 分别表示任意w a t s o n - c r i c k 有限自动机，单状态，全终止状态，简 单，1 - 受限的w a t s o n c r i c k 有限自动机所识别的语言。而且也可以表示由这几 种性质组合得到的自动机所识别的语言，例如n 1 w k ( c t r ) 表示由单状态1 受限 的w a t s o n c r i c k 有限自动机用控制字方式识别的语言。 定理2 2 ：对于任意字母表n 有t s ，n 1 w k ( c t r ) 证明：考虑1 受限单状态的w a t s o n - c r i c k 有限自动机 m = ( v ，a p ) ， 其中 p = ( 吼口，i 口y lp = ( ；) ，( ：) i 口y ) 标签方案 e c ( ； ，= 以e c ( ： ，= 万，口y 。 d n a 计算的模型与用于解决n p 类问题的算法设计 艨陆吲吼叫p 卧是吖的一个计算，那么有 e ( a ) xs h u f f l ei ，因此e ( c r ) t s ，。x 可以是v 中的任意串，每一个形如x s h u f f l e i 的串都描述了m 的一个正确的计算。因此有嬲，n l w k ( c t r ) 。 这个定理说明了w a t s o n c r i c k 带与t s 语言之间的紧密联系。 2 4 生物计算的诞生 1 9 9 4 年，a d l m a n 提出了一种用生物学的方法解决有向哈密顿路径的问题 的方法，这标志着了生物计算作为一个专门领域的诞生。虽然在这之前，人们 也意识到生物和数学的相似性，但并没有找到把两者相似性结合起来现实的方 法。 有向哈密顿路径问题如下：给定一个有向图，一个开始顶点h 和一个结束 顶点v e ，是否存在一条路径从开始顶点v s 出发，到结束顶点终止，经过且仅 经过图中的每个顶点一次。 a d l m a n 给出了解决这个问题的如下算法： l 随机的生成图中的所有的路径。 2 仅保留那些从v 。出发，到v 。结束的路径。 3 如果图的顶点个数为n ，那么仅保留长度为疗的那些路径。 4 保留那些每个顶点都出现的路径。 可以看出，如上算法可以保留且仅保留合法的哈密顿路径。算法的四个步 骤是通过如下d n a 操作实现的。 1 给每一个顶点以长度为2 0 ( 含有2 0 个核苷酸) 的d n a 分子序列的编 码。 2 对每一条有向边，用源顶点的后部分连接上目标顶点的前部分的序列 表示。这样对含有所有有向边的溶液进行连接操作，就可以随机生成 所有的路径。 3 用p c r 反应，仅以h 和k 作为引物，使得仅仅那些以开始，以 结束的链复制。因为p c r 使得链的数目以指数速度增长，所以很容易 作到没有被复制的链的密度降到足够低。 4 用凝胶电泳方法使得d n a 链按长度分离， 5 每次抽取包含某个顶点的d n a 链，直到对所有的顶点都进行完抽取 操作。 6 经过以上步骤后，如果还有剩余的d n a 链，那么就说明有向图是存在 哈顿回路的，反之，则不存在。 1 2 d n a 计算的模型与用于解决n p 难问题的算法设计 a d l e m a n 的成功，证明了生物体本身是具有计算功能的，生物体完成自身 功能时所遵从的方式可以认为是计算的一种形式，这引导人们从生物的角度考 虑计算，生物计算作为一个独立的研究领域诞生了。 小结 本章首先给出了计算模型完备性的标准【3 0 ，2 8 】，介绍了嬲语言以及d n a 结构与t s 的关系【9 ，2 4 】和一个输入为w k 。( y ) 的自动机【9 】，并简单介绍了生物 计算诞生的标志 1 】一解决哈密顿回路问题。 d n a 计算的模型与用于解决n p 类问题的算法设计 第三章d n a 计算模型 3 1d n a 删模型 3 1 1e m 机 e m ( e q u a l i t ym a c h i n e ) 如下图所示，它有一个单向的输入带，个有限控 制机制，和两条单向的只写的存储带。在工作前，存储带是空的，指向输入带 的读指针和指向输出带的写指针都指在带的最左端。工作时，读指针从左向右 的读输出带中的内容，并且根据有限控制进行状态转移，同时写指针向存储带 上写字符，使得存储带的长度增加。当输入带读完，并进入终止状态时，如果 两条存储带上的内容相同，就接受输入串；否则不接受。 图7 ：e m 机结构图 一- 单向写指针 一- 单向读指针 可以用e m = - ( k ，k ，巧，最氏，f ) 表示e m 机，其中k 是输入字符表，心是输 出字符表，艿是有限个转移规则慨口) 一( g ，d ，口k u 旯，“e ，i 1 ，2 j 的集合，一条转移规则( p ，口) 哼( g ，甜，j ) ，口k u a ，”e ，i 1 1 ，2 含义是， 当e m 处在状态p ，且读指针所指的字符为a ，那么写指针将向第i 个存储带上 写字符串“，并且进入状态g 。 e m 的格局的形式为( p ，w ( v 1 ，v 2 ) ) ，其中p k ，w k ，v 1 ，v 2 。 一条转移规则( p ，忉j ( 吼“，f ) 能使格局( p ，w w f ，( v 。v ：) ) 转移到新的格局， 如果i = 1 ，有( p ，w w t ，( v l ，1 7 2 ) ) j ( g ，w i ，v l u ，v 2 ) ， 如果f = 2 ，就有 ( ，t t w 。，( h ，v 2 ) ) = ( 仍w ，n ，v 2 u ) 。 1 4 d n a 计算的模型与用于解决n p 类问题的算法设计 鄹，接受的语言为 l ( f ) = 扣k l ( s o ，w ，( a ，旯) ) j ( g ，旯，( v ，v ”，g f ，_ v e m 用检查两条存储链是否相同来判定是否接受输入的语言，这一点与 d n a 的两条互补单链可以合成一条双链的很相似，因此可以设计用d n a 操作 实现的e m 机d n a 一励，系统。 非确定e m 机所接受的语言与r e 是等价的，也就是说，e m 机的能力与图 灵机是一样的。因此，利用生物计算模拟e m 机，就能来得到一个完备性的计 算模型。这个模型就是d n a - e m 模型。 在这个模型中，用到的生物操作如下表： 操作名称 操作结果 合并u n i o n ( t , ，疋)t = 正u 疋 左切l o u t ( t 1 ， t = 札l 口“五) 左加l a d d 暇，旬 r = 妇k 正 抽取e x t r a c t ( t l ，w )t = 正n v w v 删除d e l e t e 亿，w ) r = 如l u w v e t l 替换r e p l a c e ( 7 , ，y ，x ) t = bl 缈正 切割c u t ( r , ，口) 丁= 缸，vi 删e 正 反转r e v e r s e r = i e v e r s e ( u ) b 五 表1 ：d n a - e m 模型所用操作 除了上面的集合操作，d n a - e m 系统还用到两个判断操作： 判空( e m p t i n e s st e s t ) ：如果溶液中至少存在一条d n a 链，回答“是”， 如果不存在d n a 链，回答“否” 判双链( e q u i v a l e n c et e s t ) ：如果溶液中至少存在一条d n a 双链分子，回 答“是”，如果不存在d n a 双链分子，回答“否”。 3 1 2 双链法的d n a - e m 模型 d n a - e m 模型有双链和单链两种，双链模型更好的体现了w a t s o n - c r i c k 互 补的作用，因此以双链模型为例。 艿 中的转移规则的形式为 ( p 口) _ + ( g ，甜，f ) ， p ，g k ，口v lu a ，“如，j 1 ，2 ) 。设输入串的前k 个字符已经被读过，并且 e m 机处在格局c ，给格局c 在字符集x u ku u u 礴，$ ，1 ，2 上的编码： t ( c ) ：2 胄( 矿) p $ 群v 1 d n a 计算的模型与用于解决n p 类问题的算法设计 其中r ( 矿) 是r e v e r s e ( 可) 的简写。 模拟e m 机的基本思想就是给每个格局编码，从初始格局出发，模拟转移 规则带来的格局推进。 初始格局c ( ( q 。，w m ，a ) ) ) 的编码为( c ) 。= 2 p 。w # 1 。当给定一个输入w 时， 从初始格局( c ) 。出发，建立初始溶液t o ，瓦= 2 p 。w # 1 ) 。 设m = 例，t 是当前溶液。下一步操作如下： 1 复制m 份r 溶液。即 c o p y ( t ， 五，l ，乙) ) 假设在每个r ，l j m 中，都包含一个编码了的格局 ( c ) = 2 r ( _ ) p 铲甜# v l 。下面就是要模拟艿中的转移规则。对溶液r ，应用 转移规则r l = ( p ，a ) ( q , y ，i ) ，对这个转移规则，只需把格局 ( c ) = 2 r ( v ) p $ a x # v l 根据i 的值变为格局 ( c ) = 2 r ( v ) q $ “一# v y l ( 当i = 1 时) 或格局 ( c ) = 2 ，r ( 矿) q $ + 1 z 撑v l ( 当i = 2 时) 2 为了检查是否有格局已是终止格局( 即模拟是否结束) ，需要检查当前溶 液r 是否包含( c ) = 2 r ( 矿) g $ # v l ，其中q f ，v = v 。这个过程是通过 d n a 分子杂化实现的。把当前溶液r 复制两份，其中的一份用于可能还 要继续的计算，另外一份就用来判定是否有终止格局，把这份溶液记为 z o 。首先抽取出既含“$ 群”，又含“g $ ”的串，然后用切割切去“g ”， 并在此处切断链，然后左切去$ 群，通过切断的得到的链如果是w a t s o n - c r i c k 互补的，他们就可以组成一条双链。因此用e q u a l i t yt e s t 操作检查 溶液，如果回答“是”，就说明w 三。计算终止。否则继续( 1 ) 步 骤。 以上模拟过程需要集合操作r e p l a c e ，l a d d ，l c u t ，r e v e r s e ，e x t r a c t ，e q u a l i t y t e s t 。 3 1 3 d n a - - e m 模型的能力 e m 机的计算能力是与图灵机等价的( l n ( e m ) = r e ) ，因此概括的讲，用 来模拟e m 机的d n a - e m 模型的能力也是与图灵机等价的。具体讲，有下列定 理存在： 定理3 1 ：d n a ( u n i o n , r e p l a c e ， e m p t i n e s st e s t ) - e m = - r e 定理3 2 ：d n a ( u n i o n ，r e p l a c e ，l a d d ，l c u t , r e v e r s e ，e x t r a c t ，c u t ， e q u a l i t yt e s t ) - e m = r e 1 6 d n a 计算的模型与用于解决n p 类问题的算法设计 3 2 插删系统 插删系统是以插入和删除操作为核心的生物计算模型，可以用一个5 元组 y = ( v ，t ，a ，i ，d ) 表示。其中v 是字母表，y c v , a 是矿的有限子集，和d 是 v v v 的有限子集。字母表r 是终结字符集。4 是公理集，是插入规则， d 是删除规则。一条插入或删除规则以( 珥五v ) 的形式给出。( “，z ，v ) 。表示插 入规则，用( “，z ，v ) a a 表示删除规则。 对于x ，y v ，如果有下面两种情况之一，就有xjy 1 x = x 1 u v x 2 ，y = x l u z v x 2 ，其中x 1x 2 v ， ( mz ，v ) 是一条插入规则。 2 x = x l u g w 2 ，y = x l 价2 ，其中x 1x 2 v ， ( m 互v ) 是一条删除规则。 插删系统，= ( v ，t ，a ，i ，d ) 生成的语言定义为： l ( r ) = 仙丁i x j w ，x 4 。 插删系统，= ( v ，t ，a ，i ，d ) 的权重( mm j p ，g ) 定义为： m a x l z ii ( “，z ，v ) ij = l ， m a x l u ll ( “，z ，v ) j 目i ( v ，z ，“) 1 = m ， m a x l z ff ，z ，v ) dj = p ， m a x ml ( “，z ，v ) d 或( v ，z ，“) d = q 。 用，蚪d 聪，一，m ，p ，q 0 表示由权重为( 一，m ，p ，g ) 的插删系统生成 的语言族，其中r lv s 一，m s 州，p 墨p ，q - q 。当栉，m ，p ，q 有无界的情况时， 用o o 代替。这样，所有插删系统所产生的语言族为i n s ：d e l ：。当n = o 时， m = o ；当卿时，q = o 。 从 定 义可 以直接得出 ， 对 于 所 有的 0 n s 一，0 s m m ，0 p sp ，0 q s q ，都有j s _ = i d j e 江毒i n s d 皿。 下面定理说明了在r l ，m ，p ，q 为有限的情况下，插删系统与图灵机是等价 的。 定理3 3 ：r e = i n s ；d e l o 。 证明：设语言工量r 是由k u r o d a 形式表示的0 型文法g = ( n ，t ，s ，p ) 生成 的。p 是重写规则集，它仅包含上下文无关的重写规则x _ x ，h 2 ，和非上 下文无关的重写规则m 7 专u z ，x ，y ，u ，z n 。为0 型文法建立如下的插删系 统： y = ( n u t u k , ，k 2 ，t ， s ，j ，d ) d = ( 旯，x k 。，a ) i x n u ( 五，x y k 2 ，旯) i x ，y e ，= ( x ，k l x , aix 斗x p ， u ( x y ，k 2 u z ，a ) i 朋_ 呀p ，) 1 7 d n a 计算的模型与用于解决n f 类问题的算法设计 这里k ，k ，是用来标记删除的，蜀用来删除其左边的一个符号，k ：用来 删除其左边的两个符号。上面的系统用，模拟了规则p 。而被k ，k ，标记了的 符号就不能在用做，中规则的上下文，而是根据删除规则删除。通过以上插入和 删除规则，可以得到任何重写规则得到的字，因此有三( g ) = 三( ，) 。 与0 型文法等价的插删系统最小的权重是( 1 ，2 ，1 ，1 ) ；( 2 ，1 ，2 ， 0 ) ，( 1 ，2 ，2 ，o ) ，即r e = 胁研删= 伍两删= z n s ? d e l ：。 3 3 剪接系统 3 3 1 剪接操作 剪接系统是早期研究的生物计算得到的模型。它把d n a 的重组抽象为数 学上剪接操作。例如有下面两个d n a 双链： c c c c c t c g a c c c c c g g g g g 彳g c r g g g g g 4 4 4 彳g c g c 4 4 4 一一 丁丁r 丁r c g c g r r r 丁丁 有两种限制性酶分别能识别出片段r a g c c g t 4 和g c g c g c g c ，以上两种酶把这两个 d n a 双链切为下面四个片段： c c c c c r g g g g g g c c g a c c c c c 丁g g g g g 爿4 爿爿4 g 丁丁丁丁丁cg c c g c 4 爿彳4 4 g 丁丁丁丁丁 其中第一个片段和最后一个片段有w a t s o n - c r i c k 互补的粘性末端，第二个 与第三个也是如此。因此在聚合酶的作用下，就可能得到下面两条新的d n a 双链分子。 c c c c c r c g c a a a a aa a a a a g c g a c c c c c g g g g g 彳g c g r r r 丁r丁r r r r c g c r g g g g g 这种d n a 的重组可以抽象为数学上的剪接操作，也可以称，以上过程就 是一个生物的剪接操作。 3 3 2 简单的剪接 有字母表y 和不属于v 的两个字符$ 和# ，一个y 上的剪接规则可以用下列 字符串的形式表示： ，= “i 样“2 $ “3 撑”4 ，其中“- v ，1 s i 4 d n a 计算的模型与用于解决n p 类问题的算法设计 对以上剪接规则和串x , y , z v ，有( z ，y ) ，z z = x i i “2 x 2 ，y = y l u 3 “4 y 2 ，：= x i “l “4 y 2 ，其中x 1 ，x 2 ，y l ，y 2 v 。 z 通过剪接工和y 得到。 ，当且仅当 这个式子表示 可以用日方案