DNA计算机模型解决图顶点着色问题

本文主要探讨了一种创新的图顶点着色DNA计算机模型，由许进、强小利、方刚和周康四位作者在华中科技大学分子生物计算机研究所和大连大学生物工程学院共同开发。DNA计算机作为一种新兴的计算模型，自Adleman首次提出以来，其理论研究和生物操作技术取得了显著进展。这种计算机的设计灵感来源于DNA分子的特性和生物操作，特别是凝胶电泳和温度控制技术。 该计算机的核心结构是一个可变温度的聚丙烯酰胺凝胶电泳系统，它被划分为三个区域：解链区（对应温度Tm1）、非解链区（对应温度Tm2）和解链区（对应温度Tm3）。这种设计允许在不同温度下进行精确的操作，以实现图顶点着色问题的求解。解链区可以促使DNA链打开，而非解链区则保持链稳定，而解链区则用于执行特定的计算步骤。 文章详细介绍了DNA计算机的基本原理，包括如何利用DNA分子作为信息载体和生物反应来进行逻辑运算。存储库的构建是关键，文中提出了一种有效的方法来编码和存储图的信息，以便在DNA分子上实现颜色分配的决策过程。此外，编码问题在这个模型中扮演了重要角色，它涉及到如何将图的顶点及其相互关系转化为可读的DNA序列。 值得一提的是，本文针对5个顶点的图进行了系统的生物操作和生化实验验证，这证明了该模型在实际问题中的可行性。尽管图着色问题属于NP-完全问题，但通过DNA计算机的特性，它提供了一种潜在的生物层面解决复杂优化问题的新途径。 与其他DNA计算模型相比，如利用DNA发夹结构的SAT问题解决模型、POA技术的图最大团问题模型、表面DNA计算模型以及结合疾病诊断与治疗的DNA计算机，这种图顶点着色DNA计算机模型的独特之处在于它将生物学特性与图论问题解决结合起来，展现了DNA计算在解决实际问题上的潜力和多样性。 总结来说，这篇论文不仅介绍了图顶点着色DNA计算机的物理实现和操作原理，还展示了其在复杂问题求解中的实用价值，为DNA计算领域的发展提供了新的视角和可能的应用场景。