中文摘要：

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

英文摘要：

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 selfassembly 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.