An Algorithm in Self-Assembly of Dna Tiles for the Minimum Vertex Cover Problem

摘要

大自然中自组装的过程是无处不在的。它是由子结构的选择性亲和力驱动的由子结构向超结构的自发的自身组装。近年来，DNA自组装在DNA计算和纳米技术等领域有了广泛的发展。截至目前，DNA自组装结构已应用于解决一些计算问题。通过DNA自组装进行计算是一种有效的执行DNA并行计算的方法，此时信息是通过DNA序列进行编码的，并且大量的序列可通过粘端协作自组装在一起。有证据显示它有分子计算的能力来执行复杂的数学运算操作。
　　 研究如何运用序列的基本思想来解决最有名的子集和问题，它是NP完全问题之一。序列的DNA自组装作为一个分子计算的工具已被证明能进行可编程操作。这主要是基于这样的性质是自发的自身下部结构由有序到Watson-Crick碱基配对的DNA序列退火推动上层建筑。注意到序列的DNA自组装的优势，充分利用构建分子计算系统，实现了对NP完全问题，最小顶点覆盖(MVC)的问题的解决。