论文部分内容阅读
近年来,量子计算机、生物计算机、DNA计算等领域的创新工作引起了世人的广泛关注。其中,以DNA计算(DNAcomputing)为主的生物计算因具有超大规模并行计算能力和潜在的巨大数据存储能力等优势,使其成为发展非传统高性能计算的重要途径之一,备受科学界的关注。DNA计算是一种模拟生物分子结构并借助于分子生物技术进行计算的新方法,开创了以生化反应作为计算工具的先例,它是解决一类难以计算问题的一种新方法,特别是它在解决NP难问题时显示出其巨大的潜力。
DNA分子自组装是DNA计算领域的一个重要研究分支,指在一定的温度,浓度,酸碱度以及特定酶的作用下,一些带有输入信息的DNA分子,根据Watson-Crick互补配对原则,自组装生成新的带有输出信息的DNA分子的过程。自组装DNA计算模型组合了DNA计算、Tiling理论和DNA纳米技术,成为目前备受关注的模型之一。本文的创新点如下:
首先,将DNATile自组装计算模型应用于求解NP-完全问题。对一个只含3个变量的3-可满足性问题进行讨论,把它分为“非”运算子系统和“或”运算子系统。同时分别给出“非”操作和“或”操作的DNATile自组装计算实例。通过组合这两个操作,根据DNATile自组装的运算规则,对于任一给定的一组解,能自动的判断它是否满足该范式。由于DNA计算具有高度的并行性,所以对于可满足性问题的所有解能同时进行判断。
其次,在实际的计算科学中,对一个可满足性问题,它的范式中的每个子句,变量的个数往往是随机的。因此,在上述思想的基础上,先列出该范式中所包含的全部变量,然后在每个子句中加入该子句所没有的变量,使之成为含有n个变量的k-可满足性问题。对于加入的变量进行特殊的标记,它们在运算的过程中不影响该范式的真值解。
第三,讨论应用DNATile自组装计算模型求解矩阵的加法。对于矩阵的加法,主要是对两个数加法运算的延拓。先通过一个实例来说明两个数加法的运算过程,然后以一个矩阵中的所有数作为初始行,另一个矩阵中的所有数作为初始列,进行加法运算。
在本文的最后部分,应用DNA的分子自组装来解决可满足性问题。其原理主要是在碱基互补配对的基础上,通过相应DNA链发夹结构的不断形成与展开,利用凝胶电泳操作将各种不同长度的DNA链分离出来,最终得到所求问题的解。