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

该文基于分子生物技术提出了一种求解最大加权独立集(MWIS)问题的DNA算法。MWIS是最大独立集(MIS)的母问题，而MIS是著名的NP完全问题。该算法的关键技术是基于变长的DNA序列来对所给图中的加权顶点进行合理的编码，并在建立初始完备数据链中采用并行重叠放大(POA)技术，然后应用变性、退火、 聚合酶链式反应(PCR)、酶切反应和凝胶电泳等一系列的DNA生物操作和计算生成可行解和分离出所要求的最大加权独立集。最后给出了该算法的计算机模拟仿真结果，得到了所给问题的最大加权独立集，对算法的可行性进行了验证和总结。

DNA Solution of the Maximum Weighted Independent Set

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.