Computer Science ›› 2013, Vol. 40 ›› Issue (12): 127-132.

Previous Articles     Next Articles

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

[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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!