DNA计算在两类特殊应用问题上的分析

《DNA计算在两类特殊应用问题上的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、DNA计算在两类特殊戍用问题一卜的石Jf究插图索引图1。1DNA分子双链结构图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一3图2．1DAG任务图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一9图3．1独立：任务的不同的调度策略⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．18图4．1质粒DNA的剪切计算模型⋯⋯⋯⋯⋯1⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．．27图4．2质粒结构图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．28图4．3DNA编码链⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．30V1硕二}：学位论文附表索引表3

2、．1死中27个变量的DNA序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．22表3．23个任务和2个处理器独立任务调度问题的8种可能分配策略⋯⋯⋯．23湖南大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了支巾特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：物1竣日期：御严岁月胗日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论

3、文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密口，在年解密后适用本授权书。2、不保密囤。(请在以上相应方框内打“√”)作者签名：2局1诞殳导师签名：日期：泖笤翮年7年>月儿日月9171，硕}学位论文1．1研究目的与意义第1章绪论电子计算机对人类社会的发展起到了巨大的促进作用，随着社会和科学技术的发展，许多NP一完全问题广泛应用于不断出现的新工程领域的

4、复杂系统中。这些问题不仅应用广泛，而且在计算机理论科学的研究中具有十分重要的地位。随着分子生物学的发展，一个测试试管已可产生1018个DNA链【11。10”个分子链可用于表示1018位数据，基本生物学操作能同时处理1018位信息，即能使10”位数据并行执行。因此，生物计算在处理大型难解问题可提供巨大的并行性【l】。1994年，Adleman开创性的使用基于DNA分子的生化反应解决了7个顶点的有向Hamilton路径问题【2】，之后，关于DNA计算机及其计算模型与实验方法等方面的研究日益引起重视。Lipton仿效Adleman的方法成功求解了另

5、一个经典的NP完全问题一可满足性(SAT)Ih]题【3J。随后Lipton的思想在实验里用生物技术得以实现【41。此后，有诸多学者给出了不同类型的图与组合优化问题的DNA计算机算法和实验结果[5-9】。近年来，借鉴生物学原理进行科学计算研究已成为科学计算领域的典型特征之一【l们。比较著名的有模拟人的大脑学习机制而建立的人工神经网络，受达尔文进化论启发而建立的遗传算法，以及模拟人体的免疫机制而提出的免疫算法【111。生物分子计算的思想产生可追溯到电子计算机刚产生的年代。科学家希望利用生物分子来改进计算机硬件的效率，因为生物分子在化学反应中具有高

6、度的并行性，而且它们在自然界中大量存在，体积小而可编码的信息量却非常大。早期生物分子计算的工作只是尝试利用生物材料模仿传统的电子模式，直到1994年，Adleman矛0早期生物分子计算的工作只是尝试利用生物材料模仿传统的电子模式，直到1994年，Adleman矛lJ用DNA分子计算方法解决了哈密顿路径问题(Hamiltonianpathproblem，HPP)[忆j，从而在生物分子计算领域开辟了一个新纪元。在过去的几年中，不断有新的分子计算方法产生，让我们看到生物分子计算是一个崭新和充满潜力的研究领域。DNA计算以其具有的海量存储和并行运算能

7、力从理论上可克服电子计算机存储量小与运算速度慢的不足【l31。而且，只要未来关于DNA计算的生物技术走向成熟(无错码、链长适中、操作自动化等)，其超级计算的成本将远低于现有基于VLSI结构的超级计算机的成本114。151：目前为止，一个测试试管已可产生1018个DNA链，它可使l018位数据以数据并行的方式并行运行。因此，DNA计算可提供相当于1018个处理单元的并行性和0(1018)的存储空间114-15]。到2001年最快DNA计算在两类特殊应用问题上的研究的超级计算机在1000s内大约能并发处理l28×1015位的信息，而DNA计算中耗

8、时最长的“抽取”操作在1000s．内可在试管中同时处理1013位的数据单元；DNA计算的存储密度大约为磁带的1012倍【51。尽管目前科学界还没有给出DNA计算将来