基于DNA折纸术求解可满足性问题的计算模型

计算机工程与科学 ›› 2021, Vol. 43 ›› Issue (09): 1529-1537.

基于DNA折纸术求解可满足性问题的计算模型

王欣怡1，殷志祥2，唐震1，杨静1，崔建中3,4

(1.安徽理工大学数学与大数据学院，安徽淮南 232001；2.上海工程技术大学数理与统计学院，上海 201620；

3.安徽理工大学电气与信息工程学院，安徽淮南 232001；4.淮南联合大学计算机系，安徽淮南 232001)

收稿日期:2020-03-26 修回日期:2020-09-22 接受日期:2021-09-25 出版日期:2021-09-25 发布日期:2021-09-24
基金资助:
国家自然科学基金(62072296,61672001,61702008,11801362);安徽省自然科学基金(1808085MF193); 安徽高校自然科学研究(KJ2019A0538); 军委科技委前沿创新计划(18-163-ZT-005-009-01)

A computational model for satisfiability problem based on DNA origami

WANG Xin-yi1，YIN Zhi-xiang2，TANG Zhen1，YANG Jing1，CUI Jian-zhong3,4#br#

#br#

(1.School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan 232001;

2.School of Mathematics,Physics and Statistics,Shanghai University of Engineering Science,Shanghai 201620;

3.School of Electrical and Information Engineering,Anhui University of Science and Technology,Huainan 232001;

4.Department of Computer Science,Huainan Union University,Huainan 232001,China)

Received:2020-03-26 Revised:2020-09-22 Accepted:2021-09-25 Online:2021-09-25 Published:2021-09-24

摘要/Abstract

摘要： DNA折纸术是一种全新的DNA自组装方法，具有可编程性、纳米可寻址性等优点，被广泛地应用于DNA计算中。利用DNA折纸术可折叠出特殊结构的特点，在DNA折纸基底上设计了一种求解可满足性问题的计算模型，该模型采用分子信标原理，通过观察荧光的明灭排除非解，从而找出可满足性问题的解。最后通过实例和模拟仿真表明了模型的可行性。

关键词: DNA折纸术, 分子信标, 可满足性问题, 模型仿真

Abstract: DNA origami is a new DNA self-assembly method, which has the advantages of programmability and nano-addressability, and is widely used in DNA computing. In this paper, a computational model on DNA origami substrate for solving the satisfiability problem is designed on the basis of DNA origami that can fold special structures. This model adopts the principle of molecular beacon and eliminates the non-solution by observing the luminescence, so as to find the solution of the satisfiability problem, and the feasibility of the model is proved by examples and simulation.

Key words: DNA origami, molecular beacon, satisfiability problem, model simulation

王欣怡, 殷志祥, 唐震, 杨静, 崔建中, . 基于DNA折纸术求解可满足性问题的计算模型[J]. 计算机工程与科学, 2021, 43(09): 1529-1537.

WANG Xin-yi, YIN Zhi-xiang, TANG Zhen, YANG Jing, CUI Jian-zhong, . A computational model for satisfiability problem based on DNA origami[J]. Computer Engineering & Science, 2021, 43(09): 1529-1537.