ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2016, Vol. 53 ›› Issue (11): 2583-2593.doi: 10.7544/issn1000-1239.2016.20150312

• 人工智能 • 上一篇    下一篇

DNA自组装计算模型求解二部图完美匹配问题

蓝雯飞,邢志宝,黄俊,强小利   

  1. (中南民族大学计算机科学学院 武汉 430074) (lanwenfei1@163.com)
  • 出版日期: 2016-11-01
  • 基金资助: 
    国家自然科学基金项目(61379059);中央高校基本科研业务费专项基金项目(CZZ13003);2015年中南民族大学研究生优秀学位论文培育项目 This work was supported by the National Natural Science Foundation of China (61379059), the Fundamental Research Funds for the Central Universities (CZZ13003), and the Master Candidate Excellent Thesis Cultivation Project of South-Central University for Nationalities in 2015.

The DNA Self-Assembly Computing Model for Solving Perfect Matching Problem of Bipartite Graph

Lan Wenfei, Xing Zhibao, Huang Jun, Qiang Xiaoli   

  1. (College of Computer Science, South-Central University for Nationalities, Wuhan 430074)
  • Online: 2016-11-01

摘要: 针对二部图完美匹配问题,提出了一种基于DNA计算自组装模型的算法.首先,通过该算法求解了一个具有10个顶点的二部图完美匹配问题的实例,实例中给出DNA计算自组装模型算法所涉及到的DNA Tile的编码设计方案、自组装计算步骤及结果分析;然后,给出了任意二部图完美匹配问题的求解方案;最后,针对DNA计算自组装模型算法解决任意二部图完美匹配问题的时间和空间消耗进行了讨论.结果表明:对任意二部图只需14种Tile类型就能够得到完美匹配.

关键词: 完美匹配, 二部图, DNA计算, 自组装, 瓦片

Abstract: Biological systems are far more complex and robust than systems we can engineer today, and Because of its advantages of stability and specificity, DNA molecules have been used for the construction of nano-scale structures. With the development of DNA molecule self-assembly strategy, lots of programmable DNA tiles are constructed and used for solving NP problems. The tile assembly model, a formal model of crystal growth, is a highly distributed parallel model of natures self-assembly with the traits of highly distributed parallel, massive storage density and low power consumption. In the system, a function can be computed by deterministic assembly and identified two important quantities: the number of tile types and the assembly speed of the computation. Here a DNA self-assembly model for perfect matching problem of bipartite graph is demonstrated, and a 10-vertices bipartite graph is used as an example to illustrate this model. The computation is nondeterministic and each parallel assembly is executed in time linear in the input. The result shows that the successful solutions can be found among the many parallel assemblies, and it requires only a constant number of different tile types: 14.

Key words: perfect matching, bipartite graph, DNA computing, self-assembly, tile

中图分类号: