DNA计算中若干理论的研究

论文摘要

1994年,Adleman首次提出利用DNA分子解决有向哈密尔顿路问题。随后,关于DNA计算无论在理论还是实验方式研究上都取得了很大的进展。本文主要建立了布尔矩阵乘法以及图论中两类NP完全问题的DNA计算模型,运用统计学中的主成分分析法对DNA序列约束变量的优化进行了探讨。主要工作如下:布尔矩阵及其幂可以作为表达和解决多种问题的数学模型,如:自动机状态,开关问题等,基于布尔矩阵乘法可以用有向图来表示。本文给出了一种新的布尔矩阵乘法的DNA算法。本算法所用到的寡聚核苷酸片段等于有向图的规模,不需要聚合酶链式反应（PCR）扩增。粘贴模型是基于Waston-Crick碱基互补配对原则的DNA计算模型,该模型的优点是:理论上不需要扩展DNA链,反应时不需要生物酶的参与,DNA链可以重复利用等。2005年,Chia-Ning Yang给出了一种改进的DNA粘贴模型,该模型在解决SAT问题时所需的寡聚核苷酸片段数量有显著降低。本文对上述粘贴模型作了进一步的改进,建立了求解图最大独立集的DNA计算模型。首先将图的独立集问题转化为可满足性问题,然后利用改进的粘贴模型给出了图的最大独立集的DNA算法。最后通过一个实例给出算法实现并求出了图的最大独立集。图顶点着色问题是图论中一个著名的NP完全问题,它在现实生活中有着非常重要的应用,如:排序问题,时间表问题,交通状态,车队保养,电路安排,任务的分配等问题都与图顶点着色问题密切相关。本文利用上述改进的粘贴模型,给出了求解图顶点着色问题一种新的DNA粘贴算法。生化反应中只需生成一种DNA单链模板分子,并且这些DNA单链可以在极短时间内生成表示图所有可能顶点着色方案的DNA存储复合物,然后再运用所设计的分离操作来检测图是否可以正常着色。最后通过6个顶点8条边的图对所建模型进行了验证。本算法所用的寡聚核苷酸片段数等于图的规模。DNA计算中,序列约束变量不但具有相关性,而且带有重复的信息,这给序列的分析带来了不便。本文运用统计学中的主成分分析来减少DNA序列约束变量,得到新的约束变量（主成分）。主成分不仅彼此不相关而且能比较全面地反映原来那些约束变量包含的信息。最后对10条DNA序列的5个约束变量对应值进行了主成分分析。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 DNA计算产生的背景
• 1.2 DNA计算的研究现状
• 1.3 本文内容
• 1.4 本文创新之处
• 2 DNA计算的基本生物操作
• 2.1 DNA分子结构
• 2.2 DNA分子的基本生物操作
• 3 布尔矩阵乘法的一种DNA算法
• 3.1 基本概念
• 3.2 布尔矩阵乘法的DNA算法设计
• 3.3 算法分析
• 4 图最大独立集问题的一种改进的DNA粘贴算法
• 4.1 基本知识
• 4.2 图最大独立集问题一种改进的DNA粘贴算法的设计
• 4.3 算法分析
• 5 图顶点着色问题的一种新DNA粘贴算法
• 5.1 基本概念
• 5.2 图顶点着色问题一种新的DNA粘贴模型的设计
• 5.3 实例分析
• 5.4 算法分析
• 6 DNA序列约束变量的一种优化方法
• 6.1 引言
• 6.2 DNA序列约束变量
• 6.3 DNA序列约束变量相应值的主成分分析
• 6.4 实例分析
• 7 结束语
• 致谢
• 参考文献