论文部分内容阅读
人类社会进入电子信息时代并得以快速发展得益于电子计算机的出现。摩根定律已经预测出电子计算机的芯片微处理能力不能够长期的保持增长下去。一种新的计算机结构因此产生,科学家们发现利用DNA进行计算的一种新型的计算能够解决电子计算机不能解决的如NP-完全问题,整数规划,组合数学等一些复杂类问题。在论文中,第一章主要介绍的是DNA计算产生的背景、DNA计算的基本思想、DNA计算的研究现状以及本论文所研究的主要内容。主要是强调DNA计算研究的重要性以及DNA具有极大的存储量、极高的运算速度以及DNA计算研究的重要性和必要性。第二章介绍了 DNA计算中所涉及到的基本生物操作,主要包括DNA分子的结构、DNA分子的分离与结合、DNA链的延伸、DNA分子的复制以及DNA链的连接与切割,在DNA分子的长度测量与提取方面介绍了不同的方法,最后介绍了 DNA序列的测定、点样技术以及三种DNA计算的实现方式。第三章主要介绍了可满足性问题,以及建立的SAT问题的几种不同的DNA计算模型;第四章主要针对的是全错位排列问题,对以{1,2,3}的全错位排列为例,找出问题的原子命题,将全错位排列问题转化为可满足性问题;利用分子信标模型对其进行求解,通过排除非解,找出问题的所有可行解。第五章主介绍了 DNA芯片的概念、制作流程以及在现实生活中的应用,重点介绍了 DNA芯片在DNA计算中的应用。针对可满足性问题进行研究,利用DNA芯片建立模型,对可满足性问题进行求解,通过排除不符合条件的解,最终得到问题的全部可行解。最后一章对论文进行总结,并指出下一步仍需解决的问题。