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

计算机科学 ›› 2013, Vol. 40 ›› Issue (12): 127-132.

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

吴雪,宋晨阳,张楠,朱煜,陈志华

华东理工大学信息科学与工程学院上海200237;上海通用识别技术研究所上海201112;华东理工大学信息科学与工程学院上海200237;华东理工大学信息科学与工程学院上海200237;华东理工大学信息科学与工程学院上海200237

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
本文受国家自然科学基金(61370174),中央高校基本科研业务费专项资金(WH1114030)资助

DNA Algorithm for Maximum Matching Problem Based on Sticker Computation Model

WU Xue,SONG Chen-yang,ZHANG Nan,ZHU Yu and CHEN Zhi-hua

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 最大匹配问题(MMP)是图论中经典的组合优化问题。针对此问题提出了基于DNA粘贴计算模型的求解算法,阐述了该算法如何利用DNA链构建最大匹配问题的初始编码,说明了应用粘贴计算模型寻求最终解的生物操作过程,同时分析了此DNA并行算法的计算复杂度,最后给出了该算法的计算机模拟仿真结果和应用实例,得到了所给问题的最大匹配解,并对算法的可行性进行了验证和总结。

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

Abstract: 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.

Key words: DNA computing,Maximum matching,Sticker model

吴雪,宋晨阳,张楠,朱煜,陈志华. 最大匹配问题的粘贴DNA算法[J]. 计算机科学, 2013, 40(12): 127-132. https://doi.org/

WU Xue,SONG Chen-yang,ZHANG Nan,ZHU Yu and CHEN Zhi-hua. DNA Algorithm for Maximum Matching Problem Based on Sticker Computation Model[J]. Computer Science, 2013, 40(12): 127-132. https://doi.org/

参考文献

[1] Adleman L.Molecular computation of solutions to combinatorial problems[J].Science,1994,6(11):1021-1024
[2] Lipton R J.DNA solution of computation problems[J].Scien-ce,1995,268(4):542-545
[3] Quyang Q,Kaplan P D,Liu Shu-mo,et al.DNA solution ofmaximal clique problem[J].Science,1997,8(17):446-449
[4] Head T,Rozenberg G,Bladergroen R R,et al.Computing with DNA by operating on plasmids[J].Biosystem,2000,7:87-93
[5] Liu Q H,Wang L,Anthony G F,et al.DNA computing on surface[J].Nature,2000,3(13):175-179
[6] 高琳,马润年,许进.基于质粒DNA匹配问题的分子算法[J].生物化学与生物物理进展,2002,9(5):820-823
[7] 刘文斌,高琳,王淑栋,等.最大匹配问题的DNA 表面计算模型[J].电子学报,2003,1(10):1496-1499
[8] 谢飞舟,汤建钢.最大匹配问题的DNA试管计算模型[J].甘肃联合大学学报,2012,26(6):65-68
[9] Dong Ya-fei,Zheng Xue-dong.Molecule Algorithm for PerfectMatching Problem Based on Sticker Models[C]∥Proceeding of International Conference on Intelligent Mechatronics and Automation.China,2004:249-253
[10] 周旭,李肯立,乐光学,等.一种最大匹配问题DNA计算算法[J].计算机研究与发展,2011,8(11):2147-2154
[11] Roweis S,Winfee E,Burgoyne R,et al.A sticker-based model for DNA computation[J].Comput Biol,1998,5(4):615-629
[12] 许进,董亚非.粘贴DNA计算机模型(I):理论[J].计算机学报,2004,9(3):205-212
[13] 许进,董亚非.粘贴DNA计算机模型(II):理论[J].计算机学报,2004,9(4):299-307
[14] Bondy J A,Mum U S R.Graph Theory with Applications[M].The Macmillan Press,LTD,1976
[15] Braich R S,Johnson C,Rothemund P W K,et al．Solution of a satisfiability problem on a gel-based DNA computer,2000[C]∥Proceedings of the 6th International Conference on DNA Computation in the Springer-Verlag Lecture Notes in Computer Science series．2000,2054:27-42

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed