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.
2007, Vol. 29 
