麻晶晶^1,,,
许进²
1.山西财经大学统计学院 太原 030000
2.北京大学信息科学技术学院 北京 100871
基金项目:国家自然科学基金(61801279)

详细信息

作者简介:麻晶晶：女，1983年生，讲师，研究方向为生物计算等
许进：男，1959年生，教授，研究方向为生物计算等

通讯作者:麻晶晶　casy@pku.edu.cn

中图分类号:O157.6

计量

文章访问数:323
HTML全文浏览量:123
PDF下载量:30
被引次数:0

出版历程

收稿日期:2020-08-27
修回日期:2020-12-20
网络出版日期:2021-02-24
刊出日期:2021-10-18

Application of DNA Nanoparticle Conjugation on the Maximum Matching Problem

Jingjing MA^1,,,
Jin XU²
1. School of Statistics, Shanxi University of Finance and Economy, Taiyuan 030000, China
2. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
Funds:The National Natural Science Foundation of China (61801279)


摘要
摘要:该文提出一种DNA计算模型，利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题。根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体，然后利用一系列的实验方法来获得最终的解。这种生物化学算法可以极大地降低求解最大匹配问题的复杂度，这将为DNA自组装计算模型提供一种切实可行的方法。
关键词:DNA计算/
DNA-纳米金颗粒共聚体/
最大匹配问题/
DNA链置换反应
Abstract: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.
Key words:DNA computing/
DNA/Au nanoparticle conjugation/
Maximum matching problem/
DNA strand displacement reaction



PDF全文下载地址:

https://jeit.ac.cn/article/exportPdf?id=57be48a5-f8a5-42db-82d9-7e150dcd447c