最大匹配问题的粘贴DNA算法  

DNA Algorithm for Maximum Matching Problem Based on Sticker Computation Model

作　　者：吴雪[1] 宋晨阳 张楠[1] 朱煜[1] 陈志华[1] 

机构地区：[1]华东理工大学信息科学与工程学院,上海200237 [2]上海通用识别技术研究所,上海201112

出　　处：《计算机科学》2013年第12期127-132,140,共7页Computer Science

基　　金：国家自然科学基金(61370174);中央高校基本科研业务费专项资金(WH1114030)资助

摘　　要：最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。This paper the DNA solution of the maximum matching problem（MMP） based on sticker computation model was presented,showed how to use DNA strands to construct solution space of mole-cules for the maximum matching problem and how to apply the biological operations of sticker model to solve the problem from the solution space of mole- cules,at the same time analysed of the computational complexity for DNA parallel algorithms. Finally, the computer program was given to simulate this algorithm and the solutions of MMP for all examples were also found, and the feasibili-ty of the algorithm was validated and summarized.

关 键 词：DNA计算 最大匹配 粘贴模型 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]