单体型装配问题及其遗传算法
单体型装配问题,即从给定的来自某人染色体的SNP片断中去除错误,重构出尽可能与原来片断一致的单体型.这个问题有几个不同的模型,我们考虑的是最少错误纠正(MEC)问题.这个问题已经被证明是NP完全问题,但其实际算法还没有.本文对MEC问题设计了一个基于遗传算法的启发式算法.数值实验表明这个算法很快,很有效.设计的这个算法在绝大多数情况下能得到全局最优解.在得不到最优解的情况下,能得到与全局最优解很接近的近似最优解.鉴于MEC问题是NP完全的,这个算法是有效的、实际的算法.
遗传算法 单体型装配 MEC问题 最少错误纠正
王瑞省 吴凌云 李珍萍 章祥荪
数学与系统科学研究院应用数学研究所,中国科学院(北京)
国内会议
青岛
中文
814-823
2004-10-01（万方平台首次上网日期，不代表论文的发表时间）