（系统工程专业论文）图与组合优化中几个DNA计算模型的研究.pdf

摘要 计算机技术被认为是2 0 世纪三大科学革命之一，电子计算机为社会的发展起到了巨 大的促进作用， 但是量子物理学己 经成功地预测出芯片微处理能力的增长不能长期地保持下去。 基于这一原因， 科学家们正在寻找其他全新的计算机结构，如人工神经网络计算机、 量子计算机、光学计算机以 及d n a 计算机模型等其中d n a 计算机在近几年倍受科学界的关注。 自 从 a d le m a n博士 1 9 9 4年成功地给出用 d n a计算方法求解有向图的h a m ilt o n 有向路问题以来，关于d n a计算与d n a计算机的研究开始飞速的发展， 无论在理论研究上， 还是实验方式的研究上都取得了很大的进展。 本文主要建立了几类图与组合优化问题的d n a计算模型，具体如下: 中国邮递员问题: 中国邮递员问 题是一个实际应用背景很强的数学模型。 本文建立了该问题d n a计算模型。对图的顶点用 一 定长度的寡聚核昔酸片断表示;每条边用两种不同寡聚核普酸片断表示; 用不同长度寡聚核昔酸片断表示边的权值。然后通过连接反应、p c r扩增、磁珠分离、d n a测序等生物方法找出中国邮递员问题的解。 文中还给出了 表示权值的三种不同的编码方式。 并且用类似十解决中国邮递员问 题的方法设计了工序问 题的d n a计算模型。 基于d n a计算的可满足性问 题:用d n a计算解决可满足性问题是d n a计算领域的研究热点。目 前关于可满足性问题的d n a计算模型己 经有很多好的结果， 采用的分子结构也不尽相同。 分子信标主要是由 分子信标的识别区、 分子信标的茎杆和连接荧光剂与荧光碎灭分子的连接臂三个部分组成的， 其中识别区是由碱基序列所组成。 在分子信标茎杆的底部常常可以连接上荧光剂与荧光碎灭分子，当茎杆被打开后会产生荧光。 根据分子信标的这一 特性， 我们给出了可满足性间题的一个新的模型。该模型的难点在于分子信标的茎杆长度的设计。 整数规划、线性与 非线性规划问题的 d n a计算模型:对于众多的组合优化问 题， 特别是n p 一 完全问题， 一 般而言， 都能够直接地， 或者间接地转什1 1 -0 1 1b规划问题。 而实际中的绝大多数问题是非线性规划问题。 这三种规划都有很广泛的用途。 关于线性规划目 前已经有很好的常规算法， 但对于规模巨大的线性规划问题，人们仍然需要更好的算法问世。利用 d n a计算的巨大并行性，在线性规划问题求解方面将会得到规划问 题的满意解。 关于这一方面的研究， 国际上仍是空白。本文在基于表面的d n a计算叶 ， 分别采用了单色和双色荧光标记策略，给出了解决简单的0 - ， 规划问 题和一般0 - 1 规划问 题的 一 种理论方案， 尝试了d n a计算在规划问题中的应用。首次给出了 特殊的和 般的0 - ， 规划问题的d n a计算模型。 但是0 - 1 规划问 题只是整数规划问题的特殊形式， 要给出整数规划， 线j性与非线性规划问题的d n a计算模型还有许多问题需要研究， 这将是很困难的，也是我们以后研究的重点。关键词:d n a计算中国邮递员问题可满足性问题工序问 题 线性与非线性规划问题ab s t r a c t t h e c o m p u t e r t e c h n i q u e i s c o n s i e d r e d a s o n e o f t h e t h r e e b i g r e v o l u t i o n s o fs c i e n c e in 2 0 c e n t u r i e s , a n d t h e c o m p u t e r i s p la y g r e a t r o l e f o r t h e d e v e lo p m e n t o fs o c i e t y . b u t q u a n t u m p h y s i c s s u c c e s s f u l l y f o r c a s t t h e i n c r e a s e o f m i c r o - p r o c e s s i n ga b i l i t y o f c h ip c a n n o t k e e p d o w n f o r a l o n g p e r i o d . s o , s c i e n t i s t s a re s e e k i n g o t h e rc o m p l e t e l y n e w c o m p u t e r s t r u c t u r e . s u c h a s a rt i f i c i a l n e u r a l n e t w o r k c o m p u t e r ,q u a n t u m c o m p u t e r , o p t i c a l c o m p u t e r a s w e l l a s d n a c o m p u t e r m o d e l . a m o n g th e m ,t h e d n a c o m p u t e r i s p a y i n g m u c h a t t e n t i o n b y s c i e n t i s t s in t h e l a t e r e r y e a r s . s in c e d o c t o r a d l e m a n s u c c e s s f u l l y g a v e t h e s o lu t i o n o f d i r e c t e d h a m i l t o n p a t ha b o u t d i r e c t e d g r a p h w i t h d n a c o m p u t i n g i n 1 9 9 4 , t h e r e h a v e b e e n s i g n i f i c a n tr e s e a r c h e ff o r t s o n t h e d n a c o m p u t i n g a n d t h e d n a c o m p u t e r . p r o d i g io u s p r o g r e s sh a s b e e n g a i n e d o n b o t h t h e o r y a n d e x p e r i m e n t . i n t h i s d i s s e rt a t i o n , s o m e r e s u l t s h a v eb e e n m a d e o n d n a c o m p u t i n g a n d d n a c o m p u t e r b y w a y o f b u i l d i n g d n ac o m p u t i n g m o d e l o f s o m e p r o b l e m s a b o u t t h e g r a p h t h e o r y a n d c o m b i n a t o r i a lo p t i m i z a t i o n . i n t h e d i s s e r ta t i o n , t h e m a i n w o k i s s u m m a r i z e d a s f o l l o w s : c h i n e s e p o s t m a n p r o b l e m : c h i n e s e p o s t m a n p r o b l e m i s a m a t h e m a t i c a l m o d e lw i t h p r o f o u n d a p p l i c a t io n b a c k g r o u n d . d n a c o m p u t i n g m o d e l f o r t h i s p r o b l e m w a sg i v e n o u t i n t h e d i s s e r t a t i o n . f o r e a c h v e rt e x in a g r a p h w a s a s s o c i a t e d w i t h a c e r t a i nl o n g o l i g o n c l e o t i d e ; f o r e a c h e d g e i n t h e gr a p h , t w o d i ff e r e n t o l i g o n c l e o t i d e s w e r ec r e a t e d a n d o l i g o n c l e o t i d e w i th d i ff e r e n t l e n g t h w a s c o n s t r u c t e d f o r t h e w e i g h t f o r t h ee d g e . t h e n t h e s o l u t i o n f o r c h i n e s e p o s t m a n p r o b le m c a n b e f o u n d b y l i g a t i o nr e a c t i o n , p o l y m e r a s e c h a i n r e a c t i o n , s e p a r a t i n g o f m a g n e t i c b e a d s a n d d n as e q u e n c in g . i n a d d i t i o n , t h r e e k i n d s o f d i ff e r e n t e n c o d i n g m e t h o d s w e re g i v e n o u t i nt h e d i s s e rt a t i o n . d n a c o m p u t i n g m o d e l f o r w o r k in g o p e r a t i o n p r o b l e m w a s a l s od e s i g n e d w i t h t h e s i m i l a r m e t h o d t h e s a t i s f i a b i l i t y p r o b l e m b a s e d o n d n a c o m p u t i n g : t h e s a t i s f i a b i l i t y p r o b l e m i st h e r e s e a r c h in t e r e s t i n d n a c o m p u t i n g d o m a i n . t h e r e h a v e b e e n a l o t o f g o o d r e s u lt sa b o u t d n a c o m p u t i n g m o d e l o f t h e s a t i s f i a b i l i t v p r o b l e m a t p r e s e n t . a n d d i ff e r e n tm o l e c u l a r s t r u c t u r e s w e r e a d o p t e d . mo l e c u l a r b e a c o n s c o n s i s t o f r e c o g n i t i o n s e c t i o n ,s t e m , l i n k a r m o f c o n n e c t i n g fl u o r e s c e n c e a n d fl u o r e s c e n c e q u e n c h i n g m o l e c u l a r .r e c o g n i t i o n s e c t i o n i s m a d e o f b a s e s e q u e n c e . f l u o r e s c e n c e a n d fl u o r e s c e n c eq u e n c h i n g m o l e c u l a r a r e u s u a l l y c o n n e c t e d a t t h e b o t t o m o f m o l e c u la r b e a c o n s . l i g h tfl u o r e s c e n c e w i l l b r e a k o u t t h e n t h e s t e m i s o p e n e d . i n t h e d i s s e rt a t i o n , a n e w d n ac o m p u t in g m o d e l f o r t h e s a t i s f i a b i l i t y p r o b l e m w a s p r o p o s e d b y m e a n s o f t h e c h a r a c t e ro f m o l e c u l a r b e a c o n . t h e d i ff i c u l t o f t h e m o d e l i s d e s i g n i n g o f m o l e c u l e b e a c o n s t e m sle n g t h d n a c o m p u t i n g m o d e l f o r i n t e g e r p r o g r a m m i n g a n d l i n e a r a n d n o n l i n e a rp r o g r a m m i n g p r o b l e m: t h e t h r e e k i n d s o f p r o g r a m m i n g p r o b l e m s a l l h a v e v e r ye x t e n s iv e a p p l i c a t i o n . g e n e r a l l y s p e a k i n g , t h e m u lt i t u d i n o u s p r o b le m s o fc o m b i n a t o r i a l o p t i m i z a t i o n , e s p e c i a l l y n p - c o m p l e t e p r o b l e m , c a n a l l b e d ir e c t ly o rin d i r e c t l y t r a n s f o r m e d in t o t h e i n t e g e r p r o g r a m m i n g p r o b l e m . a n d m o s t p r o b l e m s a r en o n - l i n e a r p r o g r a m m in g p r o b l e m s i n p r a c t i c a l s i t u a t i o n . t h e r e a r e s o m e v e r y g o o dc o n v e n t i o n a l a l g o r i t h m s a b o u t t h e l i n e a r p r o g r a m m i n g a t p r e s e n t , b u t a s f o r t h es w e e p i n g l i n e a r p r o g r a m m i n g p r o b l e m , t h e b e t t e r a l g o r i t h m i s s t i l l e x p e c t e d t o c o m eo u t . i t i s a b r a n d - n e w r e s e a r c h s u b j e c t t o s o l v e l in e a r p r o g r a m m i n g p r o b l e m w it h h u g ep a r a l l e l is m o f d n a c o m p u t i n g , a n d i t i s s t i l l a b l a n k t o s u c h p r o b l e m i n t h e w o r l d .d n a c o m p u t i n g m o d e l s f o r t h e g e n e r a l 0 - 1 p r o g r a m m i n g p r o b l e m a n d t h e s p e c i a l 0 - 1p r o g r a m m i n g p r o b l e m a r e f i r s t l y p u t f o r w a r d b y a d o p t i n g s i g n a l c o l o r a n d d o u b l ec o l o r fl u o r e s c e n c e l a b e l i n g in t h e d i s s e rt a t i o n . i t i s a t t e m p t e d t o a p p l y d n ac o m p u t i n g t o s o l v e 0 - 1 p r o g r a m m i n g . b u t 0 - 1 p r o g r a m m i n g p r o b l e m i s o n l y t h es p e c i a l f o r m o f i n t e g e r p r o g r a m m i n g p r o b l e m . m a n y p r o b l e m s s h o u l d b e s t u d i e d f o rt h e d n a c o m p u t i n g m o d e l o f t h e i n t r g e r p r o g r a m m in g , l i n e a r a n d n o l i n e a rp r o g r a m m in g p r o b le m . m a y b e i t w i l l b e v e ry d i ff i c u l t , a n d i t i s a l s o t h e f o c a l p o i n tt h a t w e s h o u ld s t u d y .k e y w o r d : d n a c o m p u t i n g c h i n e s e p o s t m a n p r o b l e m s a t i s f i a b i l i t y p r o b l e m w o r k i n g o p e r a t i o n p r o b l e m l i n e a r a n d n o n l in e a r p r o g r a m m i n g p r o b l e m独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除文， ， 己 经标明引用的内容外，本论文不包含仟何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文 卜 以明确方式标明。 本人完全意识到本声明的法律结果由本人承担。学位论文作者攘名:日期:年月日学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使i ll 学位论文的规定，即:学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华， i ， 科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密口，在年解密后适川本授权书。本论文属于不保密口。( 请在以上方框内打 “ j )学位论文作者签名:日期:年月日指导教师竿名:日期:年月日1 绪论跳要: 本幸1.1简要地介w . d n a针算产生的针景、 d n a针算伪巷本思想、 h . /4 d n a针算的研 究犯k z ,介14了本之6 5 主要思路和创jo i 之处，以及本克钓 主要负献关桩钾:d n a针算，田论与g 0 合优化间题，d n a针耳机。1 . 1 d n a 计算产生的背景 计算机技术被认为是 2 0世纪三大科学革命之一，电子计算机为社会的发展起到了巨大的促进作用，但是量子物理学已经成功地预测出芯片微处理能力的增长不能一长 期地保持下去。 基于这 原 因， 科学家们正在寻找其他全新的计算机结构， 如人工神经网 络计算 机、 量子计算机、 光学 计算 机等 1 - 9 1 1 9 9 4年， 美国 加利福尼亚大学的a d le m a n 博士提出利用 d n a( 脱氧核糖核酸) 对 一 个图论中的n p 一 完全问题一 有向图的h a mi lt o n 路问题进行编码， 借助连接、 变性、 复性、 p c r扩增、电 泳等生物操作可以 求解出 这一问 题 1 0 。 他的 方法的 主要思 想是: 首 先生成所有的有向路， 然后找出 所有开始于起点，结束于终点的有向路，最后寻找经过图的每个顶点且每个顶点只经过 次的有向h a m i l t o n 路。 对应于生物实现步骤是首先用寡聚核普酸片断编码图的顶点和边， 然后将这些寡聚核普酸片断放入溶液中，利用连接酶将它们连接起来，从而产生对应于所有有向路的不同的 d n a链，最后利用 尸 c r扩增， 探针，电泳等生物手段寻找对应于只经过图的顶点 -次的有向h a m ilt o n 路的d n a链， 如果有这样的路， 则说明该图存在有向h a m ilt o n路，否则说明该图不存在有向h a m ilt o n 路。 a d le m a n对一个7 个顶点6 条边的图 进行编码， 先 将图中 各个顶点v ， 用一 个任意的2 。 个碱基单链d n a 片断 来代替，v ,v i 弧 分 别 用v ; 顶 点 的 后1 0 个 碱 基 的 互 补 碱 基 和v ， 的 前1 0 个 碱 基 的 互 补 碱 基 构成的d n a片断来代替。 然后将足量的上述d n a片断放入溶液中， 通过连接反应随机生成若干条有向路径再利用引物通过 p c r技术对上一步的产物进行扩增就可以有选择的扩增那些自 起点到终点的 d n a链。接下来，利用琼脂糖浆凝胶电泳得到的长度为， 4 0 的碱基对的谱带就是恰恰经过7 个顶点的路径的d n a 链割下这条谱带浸入双蒸水中提取 d n a链 ( 凝胶分离) 。p c r扩增及凝胶分离多次重复， 可有效提高纯度。 然后利用探针挑选出经过每个顶点仅次的d n a链，最后用凝胶电泳检测它的存在性。 这一研究成果引起了数学、物理、化学以及生物界科学家们的广泛关注，也开辟了d n a 计算这一崭新的研究领域。随后，来自 各国的2 0 0 多位有关专家探讨了d n a 计算乃至d n a 计算机的可行性， 认为基因工程的发展， 为d n a 计算及d n a计算机提供了技术上的保证， 人们将有能力按照实际需要， 组装成各种d n a 计算机in -2 t q 。 一h . d n a 计 算机研制成功， 其 运算能 力是传统计算机望尘莫及的。 这无疑是一个极具开发价值的研究领域。 d n a 计算机 ( 脱氧核糖核酸计 算机)是近几年来最有独创性和出乎意料的发现之 一 ，是生命科学与计算机科学相结合的产物。 d n a 计算 机具有以 下 几个方面的 突出 优点 s , 2 2 1 ( 1 ) 具有高度的并行性， 运算速度快， 在一周的 运算量相当 于所有电 子计算机从问世以来的总运算量。 ( 2 ) d n a作为 信息的载体其贮存的 容量非常之大，l m ， 的 d n a溶液可存储1万亿亿的二进制数据，远远超过当前全球所有电子计算机的总存储量。 ( 3 ) d n a计算机所消耗的能量只占一 台电子计算机完成同样计算所消耗的能量的十亿分之一。 ( 4 ) d n a分子的 资 源丰富。 总之， d n a 计算机的出现将会给人类文明带来 个质的飞跃， 给整个世界带来巨大的变化。 d n a 计算机的上述优点及应用情景吸引了不同学科、 不同领域的众多科学家， 特别是计算机科学、生物学、化学、数学、 物理和工程等领域的科学家。1 . 2 d n 计算的基本思想. ， d n a计算是一种以d n a与相关的某些生物酶等作为最基本材料的、基于某些生化反应原理的一种新型的分子生物计算方法。d n a计算的基本思想是; 利用d n a特殊的双螺旋结构和碱基互补配对规律进行信息编码，把要运算的对象映射成d n a分 子链， 在生 物酶的 作用下， 生 成各种数据池( d a t a p o o l) ， 然后按照 定的规则将原始问题的数据运算高度并行地映射成 d n a分子链的可控的生化过程最后， 利用分子生物技术如聚合链反应p c r 、 超声波降解、 亲和层析、克隆、诱变、分子纯化、电泳、磁珠分离等，检测所需要的运算结果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计算机。1 . 3 d n a 计算的研究现状 a d le m a n 的 工作表明了 采用d n a进行特定目 的 计算的 可行性。 它的 新颖性不仅仅在于算法，也不仅仅在于速度， 而在于采用迄今为止还没有作为计算机硬件的生物工业技术来实现，并且开发了生物酶自 身潜在的“ 运算. 能力。最近也有学者开始将 d n a计算与遗传算法、神经网络、模糊系统和混沌系统等智能计算方法相结合 2 3 -2 5 目 前， 关于d n a 计算与d n a 计算 机的 研究发展 速度非常 惊人，无论在理论研究上，还是实验方式的研究上都取得了很大的进展。下面对国内外研究的现状作 一 个简要的介绍。 1 9 9 5 年p r in c e t o n 大学的l ip t o n 在a d le m a n 思想的启发下， 通过构造一个接触网络图g，将 s a t问题的的解空间映射为通过接触网络图g的始点a . 和终点a。 的 所有哈密尔顿路 (2 2 1然后对有向图中的 顶点 和边进行编码，其力法与a d le m a n 的方法基本相同。 l ip t o n 给出 下面一个 简单 的s a t问 题: ( x , v x 2 ) 八 ( 瓦v x 2 )其中瓦 和瓦分别为 布尔 变量x , 和x : 的 补， 即x , = 1 g瓦= 。 首先将该问 题对应于一个接触网络图， 然后对图的顶点及有向边采用和a d le m a n 相同的方法进行编码: 即 顶点 和 边 均 用 长 度为2 0 核 昔 酸 片断 表 示， 对 任 一 顶点i 用p ,9 表示， p ;和 9 .分别为顶点i 的前 1 0个碱基和后 1 0个碱基构成的核营酸片断;对任 一 有向边i -j 用 4 r元表 示 。 将 编 码 顶 点 和 边 的 核 普 酸 片 断 放 入 初 始 试 管to ， 经 过 充 分 反 应后 就 会 形 成 代 表 图 中 的 各 种 有向 路 的 核 着 酸 片 断 。 然 后以 p o ， 和9 a 为 引 物 搜 索出 试管t o 中以a . 开始以a ， 结 尾的 有向 路。 再 从 试管to 中 搜索出 第 4位为1 ( x , = 1 )的核普酸片断并放入试管t l 中，剩下的放入试管t l 中;然后再从试管t t 中搜索出 第 二 位为1 ( x 2 = 1 ) 的d n a分 子 放 入 试 管t : 中 : 将 试管t ， 和t 2 合 并为t 3 ， 得 到满足第一 个子 句的 核 昔酸片断。 从 试管t 3 中 搜索出 第一 位为0 ( x , = 0 ) 的 核 普酸片断，并放入试管t o 中，剩下的放入试管t 4 中;然后再从试管t 1 4 中搜索出第二位为0 ( y = 0 ) 的d n a分子 放入试管t 5 中; 将试管t 4 和t 5 合并为t 6 ， 得到 满足第二个子句的核昔酸片断。最后检查试管t6 ，如果有核昔酸片断，说明该问题是可满足的;否则，该问题是不可满足的。 1 9 9 7 年， o u y a n g 等利用d n a计算 解决了 另一 个n p 一 完全问 题， 图的 最大 团 问 题 2 6 1 。 设g 是 一个 图 ， v ( g ) , e ( g ) 分 别 表 示图 g 的 顶 点 集 和 边 集 ，s 是g 的 一 个 顶 点 子 集 ， 如 果 s 的 导 出 子 图 g s 约 s l . 我 们 称 g s 是 g 的 一 个 团 。令h 是g 的 团 ， 若 对 于 任 意 g 的 团 h ， 有 v ( h ) i ? iv ( h ) i , 则 称h 是g 的 最 大团。 o u y a n g利用一种巧妙的编码方法给出了 利用d n a计算求解图的 最大团 . 他们的主要思想是: 首先把n个顶点的图， 每一个可能的团用 一 个 n位二进制数来表示。某一位的取值为 1 ，表示该顶点在所求的团中，如果一位的取值为 0 ,表示相应的顶点不在团中。 这样， 把n个顶点的图中所有可能的团的集合映射成了所有可能的n位二进制数的集合， 称它为完全数据池。 然后找出图中没有被边连接的点对，利用图中的团在其图的补图中对应的是空图这一简单的结论可知补图中相邻的两顶点在原图中是不相邻的， 因此，它们不可能是同一团中的顶点。这意味着相应的两个数位上的数字不可能都是 1 。于是从完全数据池中剔除所有在补图中有一条边相连的顶点对应的数字。最后将剩余的数据池分类，以找出含数字 1 最多的数据，这些数据中的每个 ， 代表相应团中的一顶点因此，i r 素 1的个数最多的就是图的最大团，并且儿素 ，的个数就是最大团所含的顶点数 从这三位学者的工作之后，已有许多作者给出了不同类型的图与组合优化问题的d n a计算方法与结果， 如l ip t o n 给出了 连接网 络、电 路及最大电 路以 及正规电 路等的可 满足性问 题2 2 , 2 7 -3 0 : 质粒 d n a分子是一种环状的 超螺旋结构，h e a d 提出了 用质粒d n a 分子来解决可满足性问 题3 1 ; 高 琳， 马 润年， 许进利用质粒d n a分子结构给出 了图的 最大匹配问 题的d n a计算 模型 3 2 ;张连珍， 许进给出了一种基于环状质粒 d n a计算的新方法，这种计算质粒包含一个特殊的插入 d n a序列片断，每个片断定位在匹配的限制性内切位点，通过剪切和粘贴实 现计算过程， 并 讨论了0 - ， 背 包问 题 ( z k p ) 的 质粒d n a计算模型算 法 3 3 c u k r a s 等人用r n a代替d n a给出了可满足性问 题的 1种实验性的 计算模型，并 讨论国 际 象棋问 题的r n a计算模型3 a ; 2 0 0 0 年， l iu 等人对的 可满足性问 题进行了 基于表面实验的d n a计算 【3 5 -3 7 ; 2 0 0 1 年， wu 对表面计算 进行了 改进，使得表面计算的 操作更具 有可行性3 8 。 虽然d n a计算 模型的 产生仅有9 年的时问， 但关于基于 d n a计算乃至一般的分子生物计算的图论与 组合优化模型的研究已 经有不少的结果。 2 0 0 0 年，日 本的5 a k a m o t o等人用 d n a分子二级结构进行计算 【3 9 ， 他们用生 物技 术求解了 个由6 个 变量1 0 个子句组成的 逻辑公 式。他们的算法不仅提高了计算效率( 减少了计算所需的生物操作步数) ， 而且使 d n a计算朝自 动化方向前进了一步。d n a计算机的研制是d n a计算研究中最具有挑战性的问 题，目 前这方面研究也己 经有几个非常好的结果， wis c o n s in - m a d is o n大学的l iu 等人所做的 表面计算 ( s u r fa c e c o m p u t in g ) ， 他们的实验使得d n a计算可在固体表面进行，而不在溶液中进行。这项成果大大降低了 d n a计算的出错率。d n a计算机研究具有突破性的 进展应是2 0 0 1 年以 色列we iz m a n n科学院 的b e n e n s o n 关 于 基 于 分 子生 物的 可 编程 与自 治 计 算 机 器的 研究 14 0 1 。 我 们 称它为是一种“ 半自 动化试管型d n a计算机” 。 当然， 此运算器日 前还没有什么实用性，但它的科技意义是开拓性的! 该机器是一种可编程的、可自 治地解决组合优化问题的有限自 动机， 这种有限自 动机由d n a和操作d n a的生物酶构成。 该自 动操作的硬件由限制核酸酶和连接酶构成， 软件和输出由 双螺旋输出编码，且编程相当于选择适当的软件分子。对这些成份的混合溶液，该自 动操作处理由限制、杂交和连接循环的阶式蒸发器的输入分子，产生出可检测的输出分子，这种输出分子对于自 动操作的最终状态进行了编码， 这也就是计算的结果。同年， b r a ic h 等给出了半自 动化自 组装 d n a计算模型，并利用该模型解决了含有 2 0个变元的3 一 可 满足 性问 题 4 1 1 。 他 们 给出 了 形 如: ( x 3 v x i b v x ,e ) a ( x 5 v x 2 v x 9 ) a ( x ,3 v 7 2 v x 2 , ) 八 ( 7 1 v 7 1 v x 1 2 ) a ( 瓦v x 6 v x ) 八 ( x 5 v x 17 v x g ) 人 ( 瓦v x 4 v 不 1 ) 八 ( 瓦 ; v 瓦v x 13 ) a ( x 5 v x v x 9 ) 八 ( x , 5 v x g v 不 , ) a ( 瓦v 瓦v 瓦 2 ) a ( x 6 v x ， v x 4 ) 八 ( 瓦 5 v 不 : v x , ) 八 ( 瓦v x 19 v x ,3 ) 八 ( 瓦 : v 瓦v x 5 ) 入 ( x i2 v x , v x ,4 ) 八 ( x 3 v x 2 0 v x 2 ) 八 ( x ,o v 瓦v 瓦 ) 。 ( 瓦v x , v 不 2 ) 八 ( x 18 v 又 。 v x 3 ) 八 ( 瓦 。 v 不 6 v x . ) a ( x , v 瓦 , v 不 ; ) 八 ( x 8 v 瓦v 瓦 5 ) 八 ( 瓦v x 16 v 瓦 。 )的2 0 个变元的可满足性问 题的d n a解法， 利用所有解的组合构造s t ic k e r 模板，通 过杂交对解进行检测。 他们的思 想与l ip t o n 的 思 想基本相同， 但是他们将解的捕获和电泳这两步生物操作进行了合成，从而使得他们所采用的生物方法具有自动化的特点。 另外， 这个模型解决了具有2 0 个变元2 2 0 种解的组合的可满足问题，是到现在为止最好结果，也为d n a计算的高度并行性提供了更有力的证据。 在d n 计 算 模 型 的 研 究 中 ， 剪 接 系 统 模 型( s p lic in g s y s t e m m o d e l 4 2 -4 3 ,5 4 ,1 5 8 - 1 8 0 1 和 粘贴 模型4 0 , 4 1 , 4 5 -4 8 是 最近几 年内 主 要的 两个模型。 剪 接系 统模型是基于剪接操作 ( 分子生物操作的抽象，每个操作是切割双链 d n a分子和再重新连接切割部分以获得新的 d n a分子) ，剪接系统是计算完备的，即每个 p a s c a l程序可通过一个适当的剪接系统来模拟，反之亦然。粘贴计算模型在 d n a计算的研究中倍受学者们的关注，其主要原因不仅是此模型与剪接系统模型有一 样的计算能力，而且与 有限自 动机理论有较为密切的联系，并且是 d n a计算机更进 步研究的理论基础。粘贴模型是由r o w e i s 等人于 1 9 9 6年第二届d i m a c s专题讨论 会上提出的 4 4 ， 它是 一 种基于 分子 操作 和随 机访问内 存的 一种d n a计 算模型，是 一 种通用计算机系统。在 !般的 d n a计算中对于问 题的编码要么采用单链，要么采用双链，而粘贴模型采用单链与 双链的混合形式进行编码:将一条长链划分为若干段，其中有些是单链，有些是双链，单、双链随机分布。若用单链表示数据 0 1用双链表示数据 1 i则一条这样的一个长链可用来表示一个2 - 进制数据。由十单链和双链根据不同的生物操作可发生变化，因而 d n a链相当于个随机数据存储器。 粘贴模型的优点是在运算过程中不需要 d n a链的延伸，也不需要酶的作用，并且d n a链可重复使用。 文献 4 4 是粘贴模型建立的首篇开创性的文章， 在文献 4 4 中， 除了引 入土述基本模型之外，作者作出了如下的主要贡献:给出了 用粘贴模型求解集合覆盖问题的计算方法， 特别对粘贴模型中几种逻辑操作进行了 较为详细地解释:又诸如提出了 粘贴机器、粘贴提炼等概念。 在粘贴 模型的 基础上， k a r i 等首先提出了 粘贴系统的 概念4 2 ， 粘贴系统是-种将wa t s o n -c r ic k 互补原理应用于d n a计算的一种抽象的计算模型x 1 9 9 8 年，p a u n与g r z e g o rz 在 文 献 4 3 的 基 础 上 将 粘 贴 系 统 的 概 念 推 广 到 一 个 更 为 普 遍的形 式 上。 2 0 0 2年， 关于 粘贴 模 型的 应 用开 始了 研 究， 文 献 4 5 1给出 了 基于 粘贴 模型的图的顶点 覆盖问 题; 文献 4 6 中 提出了 粘贴 模型的一种扩展型的 新模型，即所谓的k 一 进制粘贴 模型。 文献4 i 用粘贴 模型给出了 诸如图的 子图 求 解、 图的 所有k 一 团、 k 一 独立集、 h a m i l t o n 路与圈等问题、 以及关于给定边或者顶点集的s t e i n e r树等问 题的d n a计算模型。 这些算法不仅确定了解的存在而且产生了所有的解，且对具有。 个顶点二 条边的无向图g ， 这些算法的运行时间是在。 十 m 线性时问内。在 d n a计算中， 所谓试管实际上是d n a分子构成的一个集合， 更确切地讲， 试管由编码了 输入数据的d n a分子构成。d n a计算一般由两个步骤构成:在第 -步里，建立一个大的可行解集合的数据库;在第二步里，将哪些不满足所给定问题的解的数据逐一删除。在这两个步骤里，所有的 d n a分子被并行处理。d n a计 算 效率 在很 大 程 度上依 赖 于 适 宜的 小 输 入 试 管。 在 文 献 4 8 】 中 对 粘 贴d n a计 算机模型给予较为详细地讨论，诸如基本模型、在粘贴模型的基础上建立起来的粘贴系统、k 一 进制粘贴模型理论及其应用、粘贴模型在图与组合优化上的应用等，并建立了图的顶点着色问 题k 一 进制粘贴模型。 日 前，关于d n a计算及d n a计算机的研究，主要集中在以下几个方面 ( 1 ) 研究可 用于d n a计算的 不同 分子结构。 如 单链的d n a分子( 主要以 此为平台) ，双链的d n a分子( 大部分d n a计算模型的建立都离不开双链d n a分子) 、 单双链混合d n a分 子 ( 如粘贴 模型 、 环状的d n a分子 ( 如质粒分子) 以及 半 环 状 的。 n a 分 子( 如 发 夹 结 构 分 子) 、 k - 臂。 n a 分 子 结 构 等 (4 9 -5 9 , 1 3 3 - 1 3 5 1 ( 2 ) 建 立不同问 题的d n a计算 模型。 如组合 优化中的n p 一 完全问 题及困 难的计算问 题、密码破译、 矩阵 乘法、 加法运算等问 题6 0 -7 4 ( 3 ) 研究d n a计算有关的 形式语言 及d n a计算的 复杂度 7 5 -8 5 , 1 4 9 - 1 5 0 1 尽管d n a计算的研究已取得了一些进展， 但是在 d n a计算的研究中还有许多实际问 题和理 论问 题有待 解决 【8 6 - 9 5 , 1 5 1 -1 5 4 1 ， 可以 简单的 归纳为以 下几点: ， ) 在d n a计算实验中， 如何选择实际操作的参数数目、 个体操作的速度、个体操作和序列操作的可靠性、信息载体的稳定性及一个实验中连续操作的次数 2 ) 编码的复杂性。较多的单链寡聚核昔酸片断中可能有些会形成发夹结构， 这就需要在编码时， 尽可能的使所选择的寡聚核昔酸片断有比较明显的差异。关于d n a编码的研究也是d n a计算研究中的一个热点。 3 )在杂交过程中的错误杂交。当杂交过程中产生错误杂交时，容易产生丢失解 ( 对于有些问题来说，会产生伪解) 。这一问题是生物技术上日 前很难控制的，也是 d n a计算的主要难点之 一 。 随着生物技术的不断发展， d n a计算将会被用来解决更多的实际问 题， 特别是对一些复杂巨系统中的问