单体型组装MEC问题的参数化算法研究

• 作者: 王建新 谢民主 陈建二
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 生物信息学 单体型检测 参数化算法 单核苷酸多态性
• 年，卷（期）: 2007,（35）
• 所属期刊栏目: 学术探讨
• 页码范围: 57-60
• 页数: 4页
• 分类号: TP301
• 字数: 5105字
• 语种: 中文
• DOI: 10.3321/j.issn:1002-8331.2007.35.017

摘要

单体型组装MEC问题指如何利用个体的DNA测序片断数据,翻转最少的SNP位点值以确定该个体单体型的计算问题.根据片段数据的特点提出了一个时间复杂度为O(nk22k2+mlogm+mk1)的参数化算法,其中m为片段数,n为单体型的SNP位点数,k1为一个片断覆盖的最大SNP位点数(通常小于10),k2为覆盖同一SNP位点的片段的最大数(通常不大于10).对于实际DNA测序中的片段数据,即使m和n都相当大,该算法也可以在较短的时间得到MEC问题的精确解,具有良好的可扩展性和较高的实用价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	谢民主	湖南师范大学物理与信息科学学院	16	88	4.0	9.0