ISSN 1000-1239 CN 11-1777/TP

• 人工智能 •

### 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

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.