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