| DNA-纳米颗粒共聚体在最大匹配问题中的应用 |
| |
| 引用本文： | 麻晶晶, 许进. DNA-纳米颗粒共聚体在最大匹配问题中的应用[J]. 电子与信息学报, 2021, 43(10): 2952-2957. doi: 10.11999/JEIT200764 |
| |
| 作者姓名： | 麻晶晶 许进 |
| |
| 作者单位： | 1.山西财经大学统计学院 太原 030000;;2.北京大学信息科学技术学院 北京 100871 |
| |
| 基金项目： | 国家自然科学基金(61801279) |
| |
| 摘 要： | 该文提出一种DNA计算模型，利用DNA-纳米金颗粒共聚体的自组装来解决图论中的一个NP完全问题——最大匹配问题。根据模型该文设计了能够基于一个具体的图进行自组装的特殊的DNA-纳米金颗粒共聚体，然后利用一系列的实验方法来获得最终的解。这种生物化学算法可以极大地降低求解最大匹配问题的复杂度，这将为DNA自组装计算模型提供一种切实可行的方法。
|
| 关 键 词： | DNA计算 DNA-纳米金颗粒共聚体 最大匹配问题 DNA链置换反应 |
| 收稿时间： | 2020-08-27 |
| 修稿时间： | 2020-12-20 |
Application of DNA Nanoparticle Conjugation on the Maximum Matching Problem |
| |
| Jingjing MA, Jin XU. Application of DNA Nanoparticle Conjugation on the Maximum Matching Problem[J]. Journal of Electronics & Information Technology, 2021, 43(10): 2952-2957. doi: 10.11999/JEIT200764 |
| |
| Authors: | Jingjing MA Jin XU |
| |
| Affiliation: | 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 |
| |
| 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. |
| |
| Keywords: | DNA computing DNA Au nanoparticle conjugation Maximum matching problem DNA strand displacement reaction |
|
| 点击此处可从《电子与信息学报》浏览原始摘要信息 |
|
点击此处可从《电子与信息学报》下载全文 |
