DNA-纳米颗粒共聚体在最大匹配问题中的应用  

Application of DNA Nanoparticle Conjugation on the Maximum Matching Problem

作　　者：麻晶晶 许进[2] MA Jingjing;XU Jin(School of Statistics,Shanxi University of Finance and Economy,Taiyuan 030000,China;School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China)

机构地区：[1]山西财经大学统计学院,太原030000 [2]北京大学信息科学技术学院,北京100871

出　　处：《电子与信息学报》2021年第10期2952-2957,共6页Journal of Electronics & Information Technology

基　　金：国家自然科学基金(61801279)。

摘　　要：该文提出一种DNA计算模型,利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题。根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体,然后利用一系列的实验方法来获得最终的解。这种生物化学算法可以极大地降低求解最大匹配问题的复杂度,这将为DNA自组装计算模型提供一种切实可行的方法。A DNA computing algorithm is proposed in this paper which uses the assembly process of DNA/Au nanoparticle conjugation to solve an NP-complete problem in the Graph theory,the Maximum Matching Problem.According to the algorithm,the special DNA/Au nanoparticle conjugation is designed,which assembled based on a specific graph.Then,a series of experimental techniques are utilized to get the final result.This biochemical algorithm can reduce the complexity of the maximum matching problem greatly,which will provide a practical way to the best use of DNA self-assembly model.

关 键 词：DNA计算 DNA-纳米金颗粒共聚体 最大匹配问题 DNA链置换反应 

分 类 号：O157.6[理学—数学]