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

• 作者: 吴雪 赵艺
• 来源期刊: 电子与信息学报
• 学科: 工学
• 关键词: DNA计算 独立集 NP完全问题 生物技术
• 年，卷（期）: 2007,（11）
• 所属期刊栏目: 论文
• 页码范围: 2693-2697
• 页数: 5页
• 分类号: TP301.6
• 字数: 4383字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴雪	华东理工大学电子与通信工程系	12	66	6.0	7.0
2	赵艺	华东理工大学电子与通信工程系	3	11	1.0	3.0