摘要
该文基于分子生物技术提出了一种求解最大加权独立集(MWIS)问题的DNA算法。MWIS是最大独立集(MIS)的母问题,而MIS是著名的NP完全问题。该算法的关键技术是基于变长的DNA序列来对所给图中的加权顶点进行合理的编码,并在建立初始完备数据链中采用并行重叠放大(POA)技术,然后应用变性、退火、聚合酶链式反应(PCR)、酶切反应和凝胶电泳等一系列的DNA生物操作和计算生成可行解和分离出所要求的最大加权独立集。最后给出了该算法的计算机模拟仿真结果,得到了所给问题的最大加权独立集,对算法的可行性进行了验证和总结。
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.
出处
《电子与信息学报》
EI
CSCD
北大核心
2007年第11期2693-2697,共5页
Journal of Electronics & Information Technology
关键词
DNA计算
独立集
NP完全问题
生物技术
DNA computing
Independent set
NP-complete problem
Biological technology
