200501网友练习《DNA计算研究》

lilycang

各位，我的兴趣是新兴的DNA计算研究，有同路的没有

lilycang

lilycang@163.com

韩冰

我的是shumo2004@163.com

韩冰

可以详细的说一下吗？

在这里应该会找到志同道合的！

lilycang

很高兴看到帖子，希望这是一个好开端，能聚起一大批人，DNA计算在国内才刚刚兴起，但在国外最早八十年代就有文献，但标志是1994年的一篇解决哈米尔顿问题的文章，DNA计算最早是从讨论NP问题开始的，使期望用分子生物学的方法来解决计算问题，目前就我的个人阅读（还谈不上研究）的方向是基于形式语言和自动机理论讨论DNA计算模型，第二个是DNA编码，DNA计算领域目前发展很快，希望有更多的人感兴趣，能简单介绍一下你吗[em01]

lilycang

学习DNA计算懂得一些形式语言和自动机理论的知识,有对理论计算机科学感兴趣的朋友可以一起交流

韩冰

能留下你的qq吗?或者你加63770212!

我们可以详细谈论!

lilycang

我的QQ是398447063，但我不太聊天的，我一般都发邮件，另外关于DNA计算，目前我一直在DNA计算的编码理论方面做一些工作，这里介绍几个DNA计算研究比较集中的地方：荷兰的莱顿大学，芬兰的土尔库大学，加拿大的西安大略大学以及美国的加州理工等

韩冰

把你的E-MAIL留下!

lilycang

DNA计算理论的诞生标志是由美国南加州大学的Adleman博士于1994年完成的一个用以解决哈密尔顿路径问题的分子生物学实验[]。通过这个实验，Adleman博士为古老的计算概念赋予了全新的理念，即计算问题可以通过生化实验来完成，这无疑是具有开创性的。1995年，普林斯顿大学的Lipton等又设计了一个针对可满足性问题（SAT）的计算实验[]，这些早期的工作提出了DNA分子计算的基本思想，可以归纳为下述三个步骤[]：

1.用DNA分子链的四个碱基，在特定的互补配对规则作用下，构造不同组合来生成问题的编码

2.通过设计一组可控的分子生物学实验完成问题的求解计算

3.对所获结果进行检测和解码，以找出代表问题解的DNA序列

遵循这一基本思想，目前DNA计算的研究内容不断丰富，概括来说，DNA计算理论的研究主要划分为两类：理论DNA计算研究和DNA计算的实验研究。理论DNA计算研究是期望建立起严格的理论基础，在现有的计算理论中，图灵可计算性成为现代计算机的理论基础，因此对于DNA计算的理论研究很自然的也纳入到这个理论框架下来。另外，现代电子计算机是以二进制序列来表达信息的，研究符号序列的信息表达能力运用了形式语言和自动机理论，DNA序列是以四个碱基按照互补配对规则来建立的，因此研究DNA序列的计算能力也同样运用了形式语言和自动机的理论。目前的理论模型已从单纯的对DNA分子的计算能力研究发展到细胞计算的层面上来，其代表模型就是P系统理论[]。DNA计算的实验研究在于构建具有实现可能性的DNA计算系统，在Adleman-Lipton实验成功之后，由威斯康星大学的一个小组进行了基于表面化学技术解决四变量SAT问题的实验[]，它的意义在于将DNA链固定在硅或者玻璃等表面上，而不是漂浮在溶液中，这使对DNA链的操作得以简化，从而减少DNA链的丢失，提高了DNA计算的可靠性，使DNA计算朝自动化和实用化方向进一步发展。另一项重要的试验成果是由Winfree等进行的DNA分子自装配实验[]，该实验通过构建不同形状的DNA分子片，并将它们按照一定的规则进行组合从而完成了特定的组合计算，并且不同形状的DNA分子片的组合计算能力被证明能够类比于乔姆斯基的文法体系，其意义在于将线性DNA计算拓展到了平面DNA计算，将DNA计算研究纳入到纳米技术领域中。