单体型装配问题及其算法

• 作者: 吴凌云 张继红 王瑞省 章祥荪
• 来源期刊: 高校应用数学学报A辑
• 学科: 数学
• 关键词: 分支定界 动态聚类 单体型装配 SNP MEC问题
• 年，卷（期）: 2004,（z1）
• 页码范围: 515-528
• 页数: 14页
• 分类号: O221.3|Q811.4
• 字数: 2255字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-4424.2004.z1.003

摘要

单核苷酸多态性(SNP)单体型装配问题就是从给定的来自某人染色体的SNP片段中去除错误,重构出尽可能与原来片段一致的单体型.这个问题有几个不同的模型:最少片段去除(MFR)问题,最少SNP去除(MSR)问题以及最少错误纠正(MEC)问题.前两个问题的复杂性与算法已有一些学者研究过.第三个问题已被证明是NP完全问题,但这个问题的实际算法还没有.该文对MEC问题给出了一个分支定界算法,这个算法能得到问题的全局最优解.通过这个算法对实际数据的计算说明了MEC模型的合理性,即在一定条件下,通过修正最少的错误重构出的单体型确实是真实的单体型.由于分支定界算法对这样一个NP完全问题不能在可接受的时间内解规模较大的问题,文中又给出了求解MEC问题的两个基于动态聚类的算法,以便对规模较大的问题在可接受的时间内得到近似最优解.数值实际表明这两个算法很快,很有效.这两个算法总能得到与分支定界找到的全局最优解很接近的近似最优解.鉴于MEC问题是NP完全的,这两个算法是有效的、实际的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	章祥荪	中国科学院数学与系统科学研究院应用数学研究所	38	852	9.0	29.0
2	张继红	中国科学院数学与系统科学研究院应用数学研究所	15	326	8.0	15.0
3	王瑞省	中国科学院数学与系统科学研究院应用数学研究所	3	10	1.0	3.0
4	吴凌云	中国科学院数学与系统科学研究院应用数学研究所	11	129	3.0	11.0