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

作     者：蓝雯飞 邢志宝 黄俊 强小利 Lan Wenfei;Xing Zhibao;Huang Jun;Qiang Xiaoli

作者机构：中南民族大学计算机科学学院武汉430074 

基　　金：国家自然科学基金项目(61379059) 中央高校基本科研业务费专项基金项目(CZZ13003) 2015年中南民族大学研究生优秀学位论文培育项目 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2016年第53卷第11期

页      码：2583-2593页

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

主 题 词：完美匹配 二部图 DNA计算 自组装 瓦片 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.7544/issn1000-1239.2016.20150312

馆 藏 号：203208238...