摘要
针对二部图完美匹配问题,提出了一种基于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.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2016年第11期2583-2593,共11页
Journal of Computer Research and Development
基金
国家自然科学基金项目(61379059)
中央高校基本科研业务费专项基金项目(CZZ13003)
2015年中南民族大学研究生优秀学位论文培育项目~~
关键词
完美匹配
二部图
DNA计算
自组装
瓦片
perfect matching
bipartite graph
DNA computing
self-assembly
tile
