最大加权独立集问题的DNA算法

吴雪; 赵艺

doi:10.3724/SP.J.1146.2006.00614

最大加权独立集问题的DNA算法

doi: 10.3724/SP.J.1146.2006.00614

吴雪,
赵艺

计量
- 文章访问数: 3224
- HTML全文浏览量: 123
- PDF下载量: 1841
- 被引次数: 0
出版历程
- 收稿日期: 2006-05-08
- 修回日期: 2006-11-16
- 刊出日期: 2007-11-19

DNA Solution of the Maximum Weighted Independent Set

Wu Xue,
Zhao Yi

摘要

摘要: 该文基于分子生物技术提出了一种求解最大加权独立集(MWIS)问题的DNA算法。MWIS是最大独立集(MIS)的母问题，而MIS是著名的NP完全问题。该算法的关键技术是基于变长的DNA序列来对所给图中的加权顶点进行合理的编码，并在建立初始完备数据链中采用并行重叠放大(POA)技术，然后应用变性、退火、聚合酶链式反应(PCR)、酶切反应和凝胶电泳等一系列的DNA生物操作和计算生成可行解和分离出所要求的最大加权独立集。最后给出了该算法的计算机模拟仿真结果，得到了所给问题的最大加权独立集，对算法的可行性进行了验证和总结。
- DNA计算;独立集;NP完全问题;生物技术
Abstract: The DNA solution of the Maximum Weighted Independent Set (MWIS) problem based on biological technology is primarily presented in this paper. The MWIS problem is a well-known NP complete problem. The crucial point in the algorithm is to use of direct proportional length-based DNA strands to encode the vertices in weighed graphs and POA to build complete data pool, respectively, then the result comes out by a series of biological reaction and computation such as denaturation, anneal, Polymerase Chain Reaction(PCR), gel electrophoresis. And the maximum weighted independent set of the graph is found. Finally, the computer program is given to simulate this algorithm and the MWIS of the graph is also found , and the feasibility of the algorithm is validated and summarized.

HTML全文

参考文献(1)

Adleman L. Molecular computation of solution to combinato- rial problems[J].Science.1994, 266(11):1021-1024[2]Maley C C. DNA Computation: theory, practice, and pros- pects[J].Evolutionary Computation.1998, 6(3):201-229[3]董亚非, 谭刚军, 等. 基于粘贴系统求解TSP问题. 系统仿真学报, 2005, 17(6): 1299-1306.[4]Ouyang Q, Kaplan P D, and Liu Shumao, et al.. DNA solution of maximal clique problem[J].Science.1997, 278(17):446-449[5]高琳, 许进. 最小顶点覆盖问题的DNA分子算法. 系统工程与电子技术, 2004, 26(4): 544-548.[6]杨铀, 段滋明. 求解图的最大独立集的一种算法. 电脑开发与应用, 2002, 15(6): 13-14.[7]李有梅, 徐宗本, 孙建永. 一种求解最大独立集问题的混合神经演化算法. 计算机学报, 2003, 26(11): 1538-1545.[8]Head T, et al.. Computing with DNA by operating on plas- mids[J].Biosystems.2000, 57(2):87-93[9]Kaplan P D, Ouyang Q and Thaler D S, et al.. Parallel overlap assembly for the construction of computational DNA libraries[J].Journal of Theoretical Biology.1997, 188(3):333-341[10]Ibrahim Z. Towards solving weighted graph problems by di- rectproportional length-based DNA computing. Research Re- port, IEEE Computational Intelligence Society(CIS)Walter J Karplus Summer Research Grant 2004.[11]G.Paun.[J].G. Rozenberg, et al.. (德)著. 许进. 等. 译. DNA计算．清华大学出版社.2004,:-[12]Amos M. DNA computation[PhD Thesis], The University of Warwick, UK, 1997.[13]Sambrook J, Fritsch E F and Maniatis T. Molecular Cloning. NY: Cold Spring Harbor Laboratory Press, 1987: 1-56.[14]Ferretti C, Mauri G, and Zandron C. DNA computing. Heidelberg: Springer Berlin, 2005: 215-223.

施引文献

资源附件(0)

访问统计