【摘要】 DNA计算求解NP完全问题,可编程性、自主、高并行性,是十分重要的追求。文中主要借助可编程的DNA分子系统求解最大团问题。DNA自组装是通过起始双链体的诱发,由化学发夹和指令发夹杂交反应交错排列构成线性双链体,它的两条链一条由化学发夹组成,一条由指令发夹组成。通过DNA链置换反应,发生链的迁移,将可增长的低聚物转移到每个发夹上,组装顺序是通过成对的互补脚趾之间相互作用进行编程。最终检测线性双链体上低聚物的个数来读取图的最大团及其顶点。更多还原

【Abstract】 By DNA computing to solve NP complete problems, programmability, autonomous, and high parallelism are very important goals. Maximum Clique Problem is solved mainly by means of a programmable DNA molecular system in this study. The product of DNA assembly is a linear duplex formed by the initiating duplex, and ′Chemistry′ hairpins and ′Instruction′ hairpins a staggered pattern, the duplex: one strand consists of instruction hairpins and the other of chemistry hairpins. By the DNA strand displacement reaction, strand migration occurs, and a growing oligomer is transferred to each hairpin. The sequence of assembly is programmed through interactions between pairs of complementary toeholds. Finally, the number of oligomers on the linear duplex is detected to read Maximum Clique of the graph and its vertices.更多还原