DNA计算模型在NP-完全问题中的应用

发布时间：2020-06-18 00:23

【摘要】：DNA计算一直以来都是很热门的一门学科,它利用分子生物技术解决计算机科学或数学中的问题,是计算机科学与生物化学之间的桥梁。在DNA的计算中,信息通过DNA分子间的相互作用进行传递,并且它的过程是通过一系列生化反应来完成的,由于生化反应中固有的大量并行性和DNA分子的高信息密度,使得DNA计算慢慢成为一个有吸引力的并且值得研究的领域。本文主要研究的是DNA计算在NP-完全问题中的应用。首先在绪论中介绍了 DNA计算的背景知识,基本的思想和意义。然后详细阐述了 DNA折纸术在可满足性问题中的应用,并列出了可满足性问题的研究现状。可满足性问题是理论计算机与人工智能等领域共同关注的NP-完全问题之一,在NP-完全问题中占有很重要的地位。与以往提出的一些DNA自组装方法相比,DNA折纸术可以看成是一种新的DNA自组装方法。利用基于DNA折纸术求解可满足性问题的计算模型,解决了一个含3个变量、3条子句的实例,以说明算法的可行性。该计算模型只需利用凝胶电泳寻找满足问题的解,这是目前已知的最可靠的生物操作,提高了模型可行性,降低了生物操作的难度。目前,利用折纸术来求解NP-完全问题的成果相对较少,我们提出的方法是利用生物DNA分子解决NP-完全问题的一种新的尝试。尽管SAT问题有很多丰硕成果,但基于SAT问题的重要性,新的方法总能引起读者重视。随着研究人员们更深入的研究以后,使得对于DNA折纸术,其结构的尺寸及其稳定性有了初步的改进,它作为一个新兴的DNA计算模型,在很多方面都起到了一定的推动作用,对DNA计算的发展提供了更大的帮助。根据列出的0-1整数规划问题的研究现状,提出巨磁电阻型DNA计算模型在0-1整数规划问题中的应用。本文将问题的变量编码成DNA链,在GMR型芯片表面固定DNA探针,然后将被生物素标记的待分析目标DNA链与探针进行充分杂交,通过芯片上的GMR传感器对芯片上纳米磁珠的检测,以电信号方式输出,得到问题的解,避免了荧光分析中的信号转换而引起的失真。该模型具有较高灵敏度,信号检测和分析较为简单,对信号检测设备要求较低。最后简单的介绍了本文的主要研究结果,比较了提出的模型与其他DNA计算模型的优点与不足,并交代了进一步的研究方向。图[29]表[2]参考文献[58]
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：Q523;O221.4
【图文】：

哈密顿路径,存在唯一,有向图

解决了一个ＮＰ－完全问题（Ｈａｍｉｌｔｏｎ路问题），具有指定顶点ｖ，＿？和，的有向图Ｇ逡逑被称为具有Ｈａｍｉｌｔｏｎｉａｎ路，当且仅当存在一系列兼容的“单向”边ｅ｜，ｅ２，．．．，ｅ？邋（即逡逑路径），以ｖ，？开始，结束，并且每一个顶点完全进入一次（图１）。逡逑图１有向图，当ｖ，？＝０，＝逦存在唯一的哈密顿路径：逡逑０邋—＞邋１，１邋—＞邋２，２邋—＞邋３，３邋—＞邋４，４邋—＞邋５，５邋—＞邋６逡逑Ｆｉｇ．邋１邋Ｄｉｒｅｃｔｅｄ邋ｇｒａｐｈ，邋ｗｈｅｎ邋ｖｉｎ邋＝邋０，邋ｖｏｕｔ邋＝邋６邋，ｔｈｅｒｅ邋ｉｓ邋ａ邋ｕｎｉｑｕｅ邋Ｈａｍｉｌｔｏｎｉａｎ邋ｐａｔｈ逡逑０邋—＞邋１，１邋—＾邋２，２邋—＞邋３，３邋—＞邋４，４邋—＞邋５，５邋—＞邋６逡逑这是分子生物学工具被直接应用在ＮＰ－完全问题上，科学发展大大促进了分逡逑子生物技术以很快的速度发展。这一问题一经提出引起了各界研究人员的重视和逡逑关注，尤其是数学，物理方面的科学家，ＤＮＡ计算由于其并行性和高可存储性可逡逑以满足各种研究的需要，因而成为热门领域。它的应用性较强，被广泛应用于实逡逑际问题。ＤＮＡ计算是通过利用分子生物学实验室技术来操纵ＤＮＡ链来解决计算逡逑问题

两位数,试管

更简单方便操作，试管的形成方式与Ａｄｌｅｍａｎ形成所有路径的试管相同，试管中逡逑的ＤＮＡ组对应于下面的简单图Ｇ？，图Ｇ具有节点ａ１，ｘ１，；￡：ｉ，ａ２，ｘ２，ｘｊ，．．．，ｆｌ？＋１，边逡逑缘从心到＼和；＾以及从心和＜到七＋１邋（图２），这是对比其他方法以后，更适合逡逑用来解决ＮＰ－完全问题的方法，与我们的计算机相比较而言，这种ＤＮＡ计算模逡逑型具有更快的速度和更大的存储容量。逡逑－１邋－逡逑

【参考文献】