分子信标、DNA芯片在DNA计算中的应用

摘要

人类社会进入电子信息时代并得以快速发展得益于电子计算机的出现。摩根定律已经预测出电子计算机的芯片微处理能力不能够长期的保持增长下去。一种新的计算机结构因此产生，科学家们发现利用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芯片建立模型，对可满足性问题进行求解，通过排除不符合条件的解，最终得到问题的全部可行解。
　　最后一章对论文进行总结，并指出下一步仍需解决的问题。

目录

声明

摘要

插图清单

引言

1 绪论

1．1 DNA计算产生的背景

1．2 DNA计算的基本思想

1．3 DNA计算的研究现状

1．4 本文主要研究内容

2．1 DNA的分子结构

2．2 DNA分子的操作

2．2．1 DNA分子的分离与结合

2．2．2 DNA链的延伸

2．2．3 DNA分子的复制

2．2．4 DNA链的内切和外切

2．2．5 DNA分子的连接

2．2．6 DNA分子的提取与长度测量

2．2．7 测定DNA序列

2．2．8 微量点样技术

2．2．9 DNA计算的实现方式

3 可满足性问题的几种常见模型

3．1 Lipton模型

3．2 发夹模型

3．3 RNA模型

3．4 表面计算模型

4 全错位排列问题的分子信标模型

4．1 全错位排列问题

4．1．1 全错位排列问题的几种模型

4．1．2 全错位排列问题转化为可满足性问题

4．2 全错位排列问题的分子信标模型

4．2．1 基本算法

4．2．2 生物算法

4．2．3 小结

5 可满足性问题的DNA芯片模型

5．1 DNA芯片的概念

5．2 DNA芯片的制作过程

5．3 DNA芯片的应用

5．4 DNA芯片在DNA计算中的应用

5．5 可满足性问题的DNA芯片模型

5．6 小结

结论

参考文献

致谢

作者简介及读研期间主要科研成果