（计算机科学与技术专业论文）基于ic的dna计算算法的仿真与实现.pdf

摘要 1 9 9 4 年，a d l e m a n 用操纵d n a 分子的办法解决了一个经典的n p 完全问题哈密顿路径问题( 一个包含7 个顶点实例) 。自此以后，生 物计算作为生物与计算机科学的交叉学科迅速地发展起来。 虽然d n a 计算( 分子计算) 具有运算高度并行，d n a 作为载体信 息贮存量大，能量消耗低，d n a 分 子资源丰富等优点，但是从目前分 子计算发展来看，分子计算实现主要是溶液方式和表面方式，这两种 实现方式目前显示出很多缺点：计算错误率高，单步执行慢，编码复 杂，很难实现自动化。为了克服上述缺点，我们设计一种利用现有的 i c 技术解决d n a 计算的新的实现方式。 本文主要研究内容如下： 1 系统地对d n a i , j - 算方法、原理、主要实现方式和优缺点等方面 进行了探讨和总结，学习了f p g a 和单片机的原理和软硬件开发环境， 提出了一种基于大规模集成电路设计的d n a 计算实现方式。 2 结合传统计算机和d n a 计算的并行性，本文设计了一种基于 d n a 计算的计算机结构模型。传统的计算机在解决串行工作任务的时 候，其能力是无懈可击的，d n a 计算相对于传统的计算机也有自己独 特的优势，它能够同时搜索获得所有的结论。 3 根据分子计算原理设计了一种具有可扩展性的解决s a t 问题 的算法，并用4 个变量和6 个变量的问题对算法的正确性进行了验证。 并使用单片机作为控制器，f p g a ：设计实现电路解决了上述问题。 受限于目前实验条件，虽然理论上可以解决任意多个变量的问题，但 是目前仅能解决1 1 个变量也就是2 0 4 8 个分子处理单元的问题。 4 研究分析了0 1 规划问题的模型，并根据该问题的原理，提出 了一种基于d n a 计算的算法，并在所设计的机器模型上对该算法的正 确性进行了验证，结果表明算法是正确的。 5 分析了均分问题的计算模型原理，在原有模型基础上对7 个变 量的均分问题进行了仿真，验证了算法的正确性。 6 最大集团问题是图论中一个重要问题，本文尝试了一个五个变 量的最大集团问题，算法实现上目前只适合变量个数较少的问题，实 现起来步骤虽然有所减少但是实现复杂度仍旧较大，本问题旨在探求 一种用i c 电路实现的满足进化算法和分子计算问题的实现电路。 关键词：d n a 计算s a t 问题f p g a 均分问题最大集团问题线性 非线性规划问题 a b s t r a c t 1 9 9 4 a d l e m a nr e s o l v eac l a s s i cn p c o m p l e t ep r o b l e mc a l l e d h a m i l t o n i a up a t hp r o b l e m ( i n c l u d e7v e r t e x ) s i n c et h e n ，t h ed n a c o m p u t i n gt e r m sa st h ej u n c t i o no fb i o t e c h n o l o g ya n dc o m p u t e rs c i e n c e g e tr a p i dd e v e l o p m e n t a l t h o u g ht h e r ea r es o m ea d v a n t a g e so fd n ac o m p u t i n g ，s u c ha s h i g l l l yp a r a l l e l i s mc o m p u t e ，h i g hc o m p u t a t i o n a ls p e e d ，b i gs t o r a g e c a p a c i t y , l o w - e n e r g yc o n s u m p t i o na n da b u n d a n ti nn a t u r a lr e s o u r c e se t c ， t h er e a l i z a t i o no fd n a c o m p u t i n gi sm a i n l yb a s eo nt h ec h e m i c a lm e t h o d w h i c hh a v eh i g he r r o rr a t e w i t ht h e d e v e l o p m e n to fc u r r e n tv l s i t e c h n o l o g y , t h es p e e do fi ci n c r e a s i n g a n dt h e p r i c e s o f s t o r a g e e q u i p m e n tb e c o m el o w e ra n dl o w e r t a k i n gt h ea b o v ei n t oa c c o u n t ，w e d e c i d et ou s ei ct or e a l i z ed n a c o m p u t i n g t h i sp a p e rm a i n l yd i s c u s s e sf o l l o w s ： 1 d i s c u s sa n ds u m m a r i z et h em e t h o d ，t h ep r i n c i p l e ，t h em a i nr e a l i z e m e t h o d ，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so fd n ac o m p u t i n g l e a r n et h e p r i n c i p l e so ft h em c ua n df p g a ss o f t w a r ed e v e l o p m e n te n v i r o n m e n t a n dp r o p o s eam e t h o do f u s i n gi ct or e a l i z ed n a c o m p u t i n g 2 t r a d i t i o n a lc o m p u t e ri sg o o da ts o l v es e r i a lt a s k d n a c o m p u t i n g i sb e t t e rt h a nt r a d i t i o n a lc o m p u t e ri ns o m ep o i n t s ，i tc a l ls e a r c ha n dg e ta l l t h ea n s w e r sa tt h es a m et i m e c o m b i n et h et r a d i t i o n a lc o m p u t e ra n dd n a c o m p u t i n g ，w ed e s i g nc o m p u t e rm o d e lb a s e do nd n ac o m p u t i n g 3 a c c o r d i n gt ot h ep r i n c i p l eo fd n ac o m p u t i n g ，w ed e s i g na a l g o r i t h mt o s o l v es a tp r o b l e m ，a n dc h e c kt h ea n s w e rw i t ht w o e x a m p l e s ，o n ei sf o u rv a r i a b l e sp r o b l e ma n dt h eo t h e ri ss i xv a r i a b l e s p r o b l e m w ea l s ou s em c u a sc o n t r o l l e ra n df p g aa sc i r c u i tr e a l i z et h e p r o b l e ma b o v e u n d e rt h ep r e s e n te x p e r i m e n t a lc o n d i t i o n s ，a l t h o u g hw e c a ns o l v ea n yn u m b e ro fv a r i a b l e si nt h e o r y , w eo n l ys o l v e d1 1v a r i a b l e s p r o b l e m 4 a n a l y z et h e0 - 1p l a n n i n gm o d e l ，a n da c c o r d i n gt ot h ep r i n c i p l eo f t h ei s s u e ，ad n a c o m p u t i n ga l g o r i t h mi sp r o p o s e d w eu s ea ne x a m p l e v e r i f i e dt h ea l g o r i t h m 5 a n a l y z et h ep r i n c i p l ee q u a l l yd i s t r i b u t i o np r o b l e m ，b a s e o n o r i g i n a lm o d e l ，w es i m u l a t ee x a m p l eo fs e v e nv a r i a b l e s i ti n d i c a t et h e c o r r e c t n e s so ft h ea l g o r i t h ma g a i n 6 m a x i m a lc l i q u ep r o b l e mi ng r a p ht h e o r yi s a ni m p o r t a n ti s s u e t h i sp a p e ra t t e m p t st os o l v eaf i v ev a r i a b l e sm a x i m a lc l i q u ep r o b l e m t h ea l g o r i t h m sc u r r e n t l yo n l ys u i tf o rt h es m a l l e rn u m b e ro fv a r i a b l e s k e yw o r d s ：d n ac o m p u t i n g s a t i s f i a b i l i t yp r o b l e m f p g a e e q u a l l yd i s t r i b u t i o np r o b l e m l i n e a ra n dn o n l i n e a rp l a n n i n g p r o b l e m m a x i m a lc l i q u ep r o b l e m 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京 邮电大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢 意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：汤趁堑日期：五型z ! ；埠 ， 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大 学。学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容，可 以允许采用影印、缩印或其它复制手段保存、汇编学位论文。( 保密的学位 论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非 保密论文注释：本学位论文不属于保密范围，适用本授权书。 日期：型z ，n 孕一一 嗍。小卜南于_ 北京邮i u 大学硕i ：学位论文 肇于i c 的d n a 计算算法仿真弓实现 1 1 引言 第一章绪论 计算机的发展有着悠久的历史，中国古代的算盘和欧洲的计算尺可以看作是 早期的计算机。第一台冯诺伊曼模型计算机的问世，给计算机的发展带来了本质 的飞跃从过去的利用机械方法进行计算，过渡到电子方法进行计算。这种改 变极大的提高了计算机的能力，计算机能够处理问题的范围得到了极大的扩充， 而且电子计算机的发展使得计算机由单纯的计算工具变成人们只常生活的必需 品。 自从电子计算机问世以来，它的处理器运算速度的增长几乎完美的遵从摩尔 定律一以时间的指数速度增长。但这种增长并不是无限的，而是受电予设备本身 物理性质的限制。一般认为，不久的将柬，计算的速度就会达到电子设备物理性 质所能承载的极限。 在传统计算机计算速度增长空间有限的情况下，如何进一步的提高计算机的 计算能力? 人们把目光投向新的计算模式或介质，其中量子计算和生物计算受到 了众多科研工作者的关注。这两种计算模型如果能够获得成功，都将带来计算机 发展的又一次本质的飞跃。 1 9 9 4 年，a d l e m a n 用操纵d n a 分子的办法解决了一个经典的n p 完全问题一哈 密顿路径问题( 一个包含7 个顶点实例) 【1 1 自此以后，生物计算作为生物与计算机 科学的交叉学科迅速地发展起来。 本文所讨论的是结合生物计算中的d n a 计算模式和现代冯诺伊曼机的一种 新的计算机模式。冯诺伊曼每个时段进行一个操作，只有当它完成一个任务后， 才能处理新的任务，而d n a 计算的计算模式是同时处理许多的任务。因此，一 些对冯诺伊曼计算机来讲是不可能完成或是很困难的任务，用d n a 计算可能会 轻而易举的得到解决。本文提出的计算模型既可以解决传统冯诺伊曼机解决的问 题又可以解决目前d n a 计算适合的同时处理多任务的计算。 另外，d n a 存储数据的密度也远远大于电子计算机。d n a 分子上的一个碱 基大约是0 3 5 纳米，也就是说在一平方尺的面积上，d n a 分了可以存储的信息可 以高达上百万g ，而电子计算机在相同的面积上只能存储几个g 的信剧2 】。 d n a 分子既是存储介质，又是计算介质，d n a 计算可以看作是纳米计算机 的计算。 北京邮i u 人学坝l 学位论文 墙十l c 的d n a 计算算法仿真j 实现 基于d n a 计算这些“与生俱来”的特点，很多计算机或生物领域的研究者投入 到生物计算特别是d n a 计算的研究中，希望这种新的计算模式能够从理论及实 验阶段过渡到现实应用阶段，以发挥d n a 分子巨大的计算潜力。本文正是利用 了d n a 计算的计算模式和现有电子技术解决问题的。 1 2d n a 分子的结构 生物的各种生命活动都有它的物质基础，生物的遗传和变异也是这样根据现 代细胞学和遗传学的研究得知。控制生物性状遗传的主要物质是脱氧核糖核酸 d n a i ”j 。d n a 是一种高分子化合物，组成它的基本单位是脱氧核苷酸。每个脱 氧核苷酸是由一分子磷酸、一分子脱氧核糖和一分子含氮碱基组成的。含氮碱基 有四种，腺嘌呤、鸟嘌呤( g ) 、胞嘧啶( c ) 和胸腺嘧啶f r ) 。d n a 不仅具有一 定的化学组成，还具有规则的双螺旋结构。这一结构的主要特点是： ( 1 ) d n a 分子是由两条平行的脱氧核苷酸长链盘旋而成的： ( 2 ) d n a 分子中的脱氧核糖和磷酸交替连接，排列在外侧； ( 3 ) 两条链上的碱基通过氢键连接起来，形成碱基对，其排列情况如图1 - 1 所 示 一一燃呻p ， 一i 一 3 ，显然3 应当在a 1 1 到a s 之间，这 样可以缩小查找范围：再找a 1 到a 5 范围内的居中的数，即a 3 ，将要找的 数3 与a 3 比较，a 3 的值为5 ，发现a 3 3 ，显然3 应当在a 1 到a 3 范围 内再将查找范围缩小一半，与a 1 1 到a 3 范围内的居中的数a 2 比较，发现 要找的数3 等于a 2 ，查找结束，一共比较了3 次。折半查找的时间复杂度约 等于l 0 9 2 n 。 设计思想： 电路的连接如图( 以解决s a t 问题，分子处理单元是一位的为例) ： 北京邮电大学硕 ：学位论文 堆于i c 的d n a 计算算法仿真实现 3 - 1 2 结果读出电路( 部分) 所有分子处理单元通过或门连接，输出线d a t a o u t 连接到单片机的p 3 2 输入 端口。 计算步骤如下： 1 选择所有分子处理单元 2 查看d a t a o u t 是否为1 ，i = o ； 3 d a t a o u t 为1 查找低位地址0 2 州- i 1 ，如果d a t a o u t = l , j + + ，循环3 ，否则 执行4 ： 4 d a t a o u t 为0 查找高位地址尹2 n j 一1 ，如果d a t a o u t - - o ，循环4 ，否则3 ； 5 循环执行2 ，3 ，4 直到找到具体的分子运算单元，将该单元清0 ； 6 重复1 ，如d a t a o u t 为0 停止，否则继续2 ，3 ，4 ，5 ，6 。 北京邮l u 大学坝l ：学位论文基于l c 的d n a 计算算法仿真畸实现 3 6 本章小结 本章提出了一种新型的计算机体系结构模型，充分结合了现有计算机串行 运算的特点和分子计算技术并行计算特点，能够大大减少运算步骤，是对现有计 算机体系结构的一个很好的补充。 北京邮电人学硕上学位论文 基于i c 的d n a 计算算法仿真q 实现 第四章基于d n a 计算的s a t 问题研究 4 1 可满足性( s a t ) 问题概念 4 1 1 定义 可满足性问题( s a t 问题) 是一个简单的组合搜索问题，它是最先得到的n p 完全问题之一给定2 个或更多对象之间的关系的逻辑公式( 布尔公式) ，通常我 们假定公式已被转换为合取范式，一个s a t 算法能在有限的时间内，判定任意 给定的 f 形式的命题逻辑公式是否可满足，即找出所有变量的赋值，使布尔 公式的值为真。 4 1 2 布尔表达式 c n f ( 合取范式) ：设给定2 个或更多对象之问的关系的逻辑公式( 布尔公式) 的合取范式为 f _ c x c 2 a q ( 4 - 1 ) 其中c i vvv 2v vv k 称为一个分句，v j 表示一个布尔变量或他的反。 它的三种运算： 1 c i c j - 1 当且仅当g = q = 1 ， 2 、vv j - 0 当且仅当y v - 0 ， 3 v 一0 则一、= 1 ，v 。1 则一，v ；- 0 。 举个简单例子： 布尔公式 f = ( 舰v 屯v 而) a 瓴v x 2v 毛) 0 l v 屹v 屯) v x 2v x 3 ) ( 4 - 2 ) 其中墨，屯，而是布尔变量，取值范围为0 或1 ，1 为“真”。“v ”表示逻辑“或”， 八表示逻辑“与”，z 表示z 取反。 北京邮电人学硕l ：学位论文 基十i c 的d n a 计算算法仿真1 i 实现 4 23 - s a t 问题 在一个布尔表达式中，要求每个子句最多只有3 个文字，这样的问题称之为 3 - s a t 问题：若要求最多含有2 个文字则为2 - s a t 。l i p t o n 研究的问题属于2 - s a t , a d l e m a n 和q i r i g h i l au u 等人研究的问题都属于3 s a t 。l i p t o n 采用的是有向图 法, a d l e m a n 采用的是凝胶电泳法。q i n g h u al i u 则使用的表面基算法。目i i ， 对3 s a t 问题的研究己经达到相当高的水平，对它研究的方式也多种多样，各种 方法都得到了尝试，并且很多方法己经得到了试验的验证，能够得到满意的解， 这对全世界的研究者来说是最大的鼓舞。目前分子计算中已经解决的最多2 0 个 变量的可满足性问题就是3 s a t 问题p j 。 4 3 其它& 玎问题 当然3 - s a t 问题只是s a t 问题中的熏要组成部分，它还包含许多其它问题， 如：2 - s a t ，唯一可满足性问题，s a t 问题的表面基算法，k - s a t 问题，最大可 满足性f j 题( m a x s a t ) ，发夹问题，d n a 计算的搜索算法等。s a t 问题可以解 决一些历史著名的实际计算难题如：八争后问题、鸽笼问题、图着色问题、最优 购货规划、图的最短路经问题、布尔逻辑可满足性问题等。 4 4s a t 问题的分子计算方法 为了便于比较，这罩首先介绍一下，l i p t o n 的有向图法| 2 1 ： 算法设计思想： 1 ) 通过让d n a 链表示所有可能的解，在试管中产生所有的解空间； 2 1 通过d n a 链的类型匹配，在另一个试管中提取真解； 3 1 测试是否新试管中包含有d n a 链。 编码设计 对于公式：f 一( x vy ) ( x vy ) l i p t o n 解码法：构造一个简单的有向图g ，如图4 - 1 ： 北京邮电大学硬i ：学位论史基于i c 的d n a 计算算法仿真与实现 臣4 _ ll i p i t o n 实例 由图可知，对于含二个布尔变量的s a t 问题，其所对应的从始点4 和结束 点a ，的有向路共有4 条，分别为 口一a 2 y a ， 1 1 口，a 2 y a 3 1 0 a l 工a 2 y a 3 0 1 a l x a 2 y a 3 0 0 编码思想：l i p t o n 的编码方法和a d l e m a n 帽同，即顶点和边用为长度为2 0 b p 的寡聚核苷酸片段表示，对任一顶点i 将其为表示b 吼，p j 和嚷分别为顶点i 的前 1 0 b p 和后l o b p 序列，对任一有向边f j 用q i 功表示 算法步骤如下： ( 1 ) 将编码顶点和边的d n a 分子放入初始试管t o ，经过充分反应后就会生成图 g 中的各种有向路的d n a 分子。 ( 2 ) 以p a i 和q o 为引物搜索出试管t 0 中以a 1 开始a ，为结尾的有向路，于是t 0 中就 剩下代表上面四条路的d n a 分子。 ( 3 ) 从试管t o 中搜索出第一位为l ( x - 1 ) 的d n a 分子并放入试管t l 中，剩下的 放入试管t 2 中；然后再从试管t l 中搜索出第二位为1 ( y - 1 ) 的d n a 分子放入试管 t 2 中。将试管t 1 和t 2 合并t 3 得到满足第一个子句的d n a 分子。 ( 4 ) 从试管t 3 中搜索出第一位为o ( x 一0 ) 的d n a 分子并放入试管t 4 中，剩下的放 入试管t 4 中，然后再从试管“中搜索出第二位为0 ( y = o ) 的d n a j j 予放入试管t s 中i 将试管“和t 5 合并为t 6 满足第二个子句d n a 分子。 ( 5 ) 检测试管t 6 ，如果有d n a 分子存在，则其为该s a t 同题的解；否则，该 同题无解。 对比于上述算法，我们设计了一种新的算法。一方面，为了满足实例中第一 北京邮l u 人学坝i ：学位论文基于i c 的d n a 计算算法仿真与实现 个子句xvy ，需要，也只需要在t o 中删去0 0 ；另一方面，为满足第二项i v y ， 再删去1 1 然后，剩余的( 如果有的话) 就是解。新算法的程序如下 a d v a n c e d p r o g r a m s t e p 0 ：t o ； v a l u e s0 0 ，0 1 ，1 0 ，1 1 s t e p l ：t l ( 1 ，2 ，5 ，6 ) 和( 3 ，4 ，7 ) - ( 3 ，5 ，6 ) 和( 1 ，2 ，4 ，7 ) 4 5 的补码，结果同2 北京邮电大学顾i 。学位论义 堆十i c 的d n a 计算算法仿真j 实现 6 7 8 7 5 ( 1 0 0 1 0 1 1 ) 5 2 的补码，结果同4 7 6 ( 1 0 0 1 1 0 0 ) 5 1 的补码，结果同3 9 7 ( 1 1 0 0 0 0 1 ) 3 0 的补码，结果同1 6 4 最大集团问题介绍 集团是指所有节点两两之问都有边相连的节点集合。最大团问题：给定了 一个有n 个结点m 条边的图，找出其中节点最多的集团的节点数目。在图6 3 中给出了一个由五个节点血条边的问题。显然( 2 ，3 ，4 ) 这三个结点构成了最 大的集团，因此这个网络的最大集团大小是3 ，最大集团问题己被证实是一个 n p 完全问题【圳。 圈6 - 3 6 5 最大集团问题算法 圈6 - 4 对于一个n 个结点的图，用一个n 位二进制数表示一个可能的集团。在这 个二进制数中，某一位为1 表示相应的节点在集团中，为0 表示不在集团中。例 如，二进制数( 0 1 1 1 0 ) 代表图6 3 中的最大团( 2 ，3 ，4 ) 。这样，解决问题的 任务就变成了在给定图对应的二进制数字串集合中寻找含有最多的为1 的数。对 一个n 节点的图，我们可以构造它的补图。补图包括所有原节点和原图缺少的 边，如图6 - 4 所示，显然在原图中任意可能存在于一个集团中的两个节点在补图 中都是不相连的，即在补图中相邻的两个节点对对应的二进制位不能同时为1 。 如果补图是由若干强连通子图构成，可以就每个子图对应原图中的部分求解相应 的部分最大集团问题，而这些子图各自的最大集团的并集就是整个问题的最大 北京邮电人学硕 学位论文肇于i c 的d n a 计算算法仿真与实现 团。从这个意义上说，我们只需要求解补图为强连通图的最大集团问题。 计算从空网开始，对应的二进制位每一位都为o 。然后让样本群一代一代演 化。在每一代中使各个二迸制数的每一位以某一概率置l ，不论该位原来是1 是 o ，这种操作也称为变异。然后我们从样本群体中删除所有不满足条件的数。例 如，在图6 - 3 和图6 - 4 表示的问题中，形如( 1 1 ”) 、( 1 ”1 ) 、( 1 ”1 ) 、( 一1 1 ) 和( 一1 1 ) 的二进制将被从样本中删除。这里的代表0 或者l 的任意一个。 我们仿照s a t 问题，利用我们的模型解决这个问题。 6 6 最大集团问题实例分析 6 6 1 计算步骤 1 构建所有结果集合，五个节点2 5 = 3 2 ； 2 根据图a 的补图，删除所有不满足条件的解。即( 1 1 ”) 、( i ”1 ) 、( 1 ，1 ) 、 ( ”1 1 ) 和( ”+ 1 1 ) ； 3 删除所有( ，0 0 ”) 、( ”0 0 ) 、( + o ”0 ) 、p 0 0 ) 、( 0 4 0 ”) ： 4 查看剩余解。 6 6 2 仿真结果 表6 - 2 计算步骤 s t e p 输入数据 0 l 1 1 21 1 31 + 1 4 1 4 1 5$ $ 4 1 1 6* 0 0 + 7 # 8 0 0 + 80 + + 0 9o o + 0 0 1 0o + 0 4 5 1 北京邮i u 人学硕l ：学位论文 肇十i c 的d n a 计算算法仿真j 实现 图6 - 5 最大集团问题仿真结果 进行以上运算后，结果收敛到1 2 ，1 4 ，虽然不能准确计算出结果，但是已 经使结果收敛到一个很小的范围内。 6 7 本章小结 本章解决了d n a 计算中两种问题，在算法设计中两种算法的实现方式类似 于前面两章的实现方式。但是从d n a 计算的角度来讲，最大集团问题和均分问 题都是比较普遍的问题，目前都没有很好的解法，此问题的解决再次证明了我们 设计的系统的应用范围的广泛性。 北京邮屯大学顾十学位论文甚fi c 的d n a 计算算法仿真l j 实现 第七章总结与展望 自从1 9 9 4 年以来，生物计算特别是d n a 计算，得到了众多计算机及生物学 家的关注。人们期待着能够利用生物分子和生化反应的特性，再次带来计算机发 展的飞跃。生物计算的发展还处在初级阶段，但已经有了众多的理论模型，算法 和实验。尽管绝大部分的工作还只处于探索阶段，作为一门新兴的( 只有1 0 年左 右的历史) 研究领域，生物计算所取得的进展是另人瞩目的。 本文围绕i c 技术d n a 计算算法进行研究，利用现有的芯片和d n a 计算的 原理解决了目前分子计算领域的一些著名问题。并且利用单片机和f p g a 做了一 定的仿真工作，是对目前分子计算领域的算法难于实现( 化学) ，经费高，化学 计算本身容易出错的问题的一个很好补充和尝试。用i c 技术解决分子计算问题 的一个尝试，目前国内外尚没有研究成果可以借鉴。 7 1 结论 研究解决了可满足性问题，可满足性问题作为一个n p 完全问题，一直是 分子计算领域受关注程度较高的问题，目i j f 已经用化学方法解决的l j 题是2 0 个 变量3 一s a l l 问题。受限于目前的硬件条件和计算机硬件条件，目i j 功能仿真可 以可以解决1 1 个变量的s a t 问题。计算结果的j 下确性已经得到验证。 研究解决了0 - 1 规划问题，整数均分问题。进一步验证了基于i c 技术的 d n a 计算可以实现加法减法运算，即运算单元有了运算的功能和存储的功能。 尝试解决了最大集团问题。最大集团问题是目前已被证明的一种n p 完全问 题，利用现有的算法和硬件以及遗传算法的思想，结果集合能够充分收敛，且运 算的时间复杂度是n 2 级，较原来2 n 运算速度有了一定的提高。 7 2 进一步工作 在本文的基础上将会进一步研究基于l c 的分子计算技术，将会在一下方面 进一步开展工作。 一是寻求更好的读出算法，同化学方法类似，结果不容易计算出来，但是结 北京邮i 乜人学颂_ 学位论文堆十i c 的d n a 计算算法仿真o 实现 果读出问题将会是我们一个难题。 另外进一步完善现有系统，在现有的能够实现加减运算基础上，尝试实现乘 除运算，逻辑运算。 寻找算法能够解决的更多领域的问题，期待该系统能够得到实际的应用。 北京邮电大学顾十学位论文 举十i c 的d n a 计算算法仿真与实现 参考文献 【1 1l la d l e m a n , m o l e c u l a rc o m p u t a t i o no fs o l u t i o n st oc o m b i n a t o r i a lp r o b l e m sp 】，s c i e n c e ， 1 9 9 4 ，( 2 6 6 ) ，p p 1 0 2 1 1 0 2 4 【2 1r j l i p t o n ，d n as o l u t i o no fh a r dc o m p u t a t i o np r o b l e mp l ，s c i e n c e ，1 9 9 5 ，( 2 6 8 ) ， p p 5 8 3 - 5 8 5 【3 1q io u y a n g , e ta 1 ，d n as o l u t i o no ft h em a x i m a lc f i q u ep r o b l e m 【j 1 ，s c i e n c e ，1 9 9 7 ，( 2 7 8 ) , p p 4 4 白m 【4 1 t h e a d ，c t a l ，c o m p u t i n g w i t h d n a b y o p e r a t i n g o n p l a s m i d s p l ，b i o - s y s t e m s ，2 0 0 0 ，5 7 ( 2 ) ， p p 8 7 - 9 3 【5 】c u k r a s ，e ta 1 ，am o d e lf o rr n ab a s e dc o m p u t a t i o n ( 1 9 9 9 ) ，i np r o c e e d i n go ft h ef o u r t h i n t e r n a t i o n a lm e e t i n go nd n ab a s e dc o m p u t e r s , u n i v e r s i t yo fp e n n s y l v a n i a ，p h i l a d e l p h i a ，p a , u s a , 1 9 9 9 ，p p 2 7 - 3 7 【6 】6s a k a m o t o ，e ta 1 ，m o l e c u l a rc o m p u t a t m nb yd n ah a i r p i nf o r m a t i o n 【j 】，s c i e n c e ，2 0 0 0 ，( 2 8 8 ) p p 1 2 2 3 - 1 2 2 6 【7 】l i uq i n h u a ，e ta 1 ，d n ac o m p u t i n go ns u r f a c e sp 】，n a t u r e ，2 0 0 0 ，( 4 0 3 ) ，p p 1 7 5 1 7 9 i s 】h a i y a n gw u ，a ni m p r o v e ds u r f a c e - b a s e dm e t h o df o rd n ac o m p u t a t i o np i ，b i o - s y s t e m ，2 0 0 1 ， 5 9 ( 1 ) ，p p 1 - 5 【9 】j aa o n d y ，u s r m u r t y , g r a p ht h e o r yw i t ha p p l i c a t i o n s ，l o n d o n 【m 】，t h em a c m i l l a n p r e s sl t d ，1 9 7 6 ，p p 2 6 - 9 8 【1 0 jb a c he c o n d o n 气e ta 1 d n am o d e la n da l g o r i t h m sf o rn p - c o m p l e t ep r o b l e m s 【j 】j o u r n a l o f c o m p u t e r a n ds y s m ms c i e n c e s - 1 9 9 8 ，5 7 ( 2 ) ，p p 1 7 2 - 1 8 6 【1 1 1r o w e ms ，e ta 1 ，as t i c k e rb a s e dm o d e lf o rd n ac o m p u t a t i o np l ，j o u r n a lo fc o m p u t a t i o n a l b i o l o g y ，1 9 9 8 ，5 ( 4 ) ，p p 6 1 5 - - 6 2 9 【1 2 】g i f f o r dd k ，o nt h ep a t h t o c o m p u t a t i o nw i t hd n ap 】，s c i e n c e ，1 9 9 4 ，( 姗， p p 1 9 9 3 1 9 9 4 【1 3 】v o l n e ia ，p e d r o n ic i r c u i td e s i g nw i t hv h d l 【h q 电子：i = 业出版社2 0 0 5 【1 4 】a l l i s o nl e ta 1 ，s e q u e n c ec o m p l e x i t yf o rb i o l o g i c a ls e q u e n c ea n a l y s i s 【j 】，c o m p u t e ra n d c h e m i s t r y , 2 伽吐2 4 ( 1 ) ，p p 4 3 - 4 5 【1 5 1lk a r l , d n ac o m p u t i n g ：a r r i v a lo fb i o l o g i c a lm a t h e m a t i c s 【j 1 ，t h em a t h e m a t i c a l i n t e l l i g e n c e r , 1 9 9 7 ( 2 ) , p p 9 - 2 2 。 北京邮l u 大学硕i ：学位论文肇于i c 的d n a 计算算法仿真j 实现 【1 6 】p a u ng ，r o z e n b e r gg ，s a l o m a a 九，d n ac o m p u t i n g - n e wc o m p u t i n gp a r a d i g m s b e r l i n h e i d e l b e r g ：s p r i n g e r 2v e r l a g ，1 9 9 8 【1 7 1s h a p i r oe t e ，p r o g r a n u n a b l ea n da u t o n o m o u sc o m p u t i n gm a c h i n em a d eo fb i o m o l e c u l e sp l ， n a t u r e ，v 4 1 4 , u 6 8 6 2 , n o v2 2 , 2 0 0 1 ，p p 4 3 0 4 3 4 - 【1 8 1s u y a m a ，e ta 1 ，e q u i l i b r i u ma n a l y s i so ft h ee f f i d e n c yo fa na u t o n o m o u sm o l e c u l a rc o m p u t e r p h y s i c a lr e v i e we - s t a t i s t i c a l ，n o n l i n e a r , a n ds o f tm a t t e rp h y s i c s ，v 6 5 ，n 2 ，f e b m a r y ，2 0 0 2 f 1 9 j 李人厚余文关t d n a 计算的基本原理与探讨【j 1 计铎机学报，2 0 0 1 2 吖9 ) ：9 7 2 - 9 7 8 2 0 】o g i h a r am ，r a y 丸s i m u l a t i n gb o ol e a nc i r c u i t so nad n ac o m p u t e r 【j 】a l g o r i t h m i c a ，1 9 9 9 ， 2 5 ( 2 3 xp p 2 3 9 - 2 5 0 2 1 1w a s i e w i c zp ，d n ac o m p u t i n g ：i m p l e m e n t a t i o no fd a t af l o wl o g i c a lo p e r a t i o n s f u t u r e g e n e r a t i o nc o m p u t e rs y s t e m s 【j 】，2 0 0 1 ，1 7 ( 4 ) ，p p 3 6 1 3 7 8 【2 2 lo g u r ah e ta 1 ，as t u d yo fl e a r n i n gs p l i c es i t e so fd n as e q u e n c eb yn e u r a ln e t w o r k s c o m p u t a t i o nb i o l o g ym e d i c i n e 【j 】，1 9 9 7 ，2 7 ( 1 ) ，l a p 6 7 - 7 5 f 2 3 jn i s h i k a w aa h a g i y am ，y a m a m u r am ，v i r t u a ld n a s i m u l a t o r a n dp r o t o c o ld e s i g nb yg a p r o c t h eg e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c eo r l a n d o ，f lu s a j u l y l3 - 1 7 ，1 9 9 9 ， p p 1 8 1 0 - 1 8 1 6 【2 4 lm u l a w k aj j ，w a s i e w i c zp ，p i e t a kk ，v i r e s - e n h a n c e dg e n e t i ca l g o r i t h m si n s p i r e db yd n a c o m p u t i n g 1 l t hi n t e m a f i o n a ls y m p o s i u ma n dm e t h o d o l o g i e sf o ri n