最大团问题的可编程的DNA分子系统计算模型  

Programmable DNA Molecular System Model of Maximum Clique Problem

作　　者：严洋洋 殷志祥 YAN Yang-yang;YIN Zhi-xiang(College of Mathematics and Big Data, Anhui University of Science and Technology, Huainan Anhui 232001,China)

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232001

出　　处：《佳木斯大学学报（自然科学版）》2020年第2期33-36,共4页Journal of Jiamusi University：Natural Science Edition

基　　金：国家自然科学基金项目(61672001,61702008);安徽自然科学基金项目(1808085MF193)资助。

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

关 键 词：最大团 DNA链置换 线性双链体 发夹 低聚物 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]