论文部分内容阅读
1994年,美国南加州大学的Adleman教授利用操作DNA分子技术成功地解决了有向Hamilton路径问题,开创了生物计算的新时代。1995年,Winfree提出了利用DNA分子瓦片自组装做计算的重要思想,为DNA计算领域的发展奠定了坚实的理论和实验基础。元胞自动机是上个世纪50年代乌尔姆和冯·诺伊曼提出的一种离散型动力系统,它是研究复杂系统行为的最初理论框架,也是人工智能的雏形。一维分子元胞自动机的DNA自组装实现已有多种方法被提出,而二维分子元胞自动机的DNA自组装实现至今还没有理想的模型被提出,本文将在这方面进行一些探索性的研究,并给出两个利用DNA自组装方法实现的二维分子元胞自动机的理论模型。本文首先在回顾Rothemund及其合作者和Yin Peng及其合作者利用DNA分子自组装实现一维分子元胞自动机的工作的基础上,分析了用四个臂的DNA瓦片分子的自组装实现二维分子元胞自动机的可能性及其复杂程度,得出虽然用四个臂的DNA瓦片分子可以实现二维分子元胞自动机但是自组装过程比较复杂的结论。其次,本文分别介绍了用八个臂的串形DNA瓦片分子自组装和用在四个臂上带有剪切酶识别位点的六个臂的TX瓦片自组装实现二维分子元胞自动机的两种方法。在后一种二维分子元胞自动机的实现方法中,本文创造性地解决了DNA计算中一个较为困难的问题——信息传递的问题。在实现二维分子元胞自动机的研究中信息传递的问题也就是在元胞状态更新过程中邻居的信息怎样传递给当前元胞和当前时刻元胞的状态信息怎样传递给下一时刻的元胞等,在本文中引入了一种用分子自动机检测和用转换分子修改信息的方法将这一问题解决了。最后,本文讨论了二维分子元胞自动机在模拟复杂系统中的应用,包括对“能自我复制的元胞自动机”和“生命游戏”的模拟,这两种元胞自动机的计算都是等价于图灵通用计算机的计算的,从计算机模拟的结果可以看出二维分子元胞自动机是完全可以实现这些计算的。基于自动机与乔姆斯基语言层次之间的关系的理论,本文实际上通过两种途径构建了一种新的分子计算机模型——二维分子元胞自动机,它是可以进行图灵通用计算的。二维元胞自动机现在已在很多领域中得到了广泛的应用,尤其是复杂系统的模拟与研究当中,再考虑到生化技术的发展和人类解决越来越复杂计算问题的需要,可以相信,在不远的未来,由DNA自组装实现的二维分子元胞自动机必将会为我们带来巨大的社会和经济价值。