个体单体型问题参数化算法研究

• 作者: 王建新 谢民主 陈建二
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 单核苷酸多态性 单体型 参数化算法 最少SNP位点删除 最少片断删除
• 年，卷（期）: 2009,（8）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1637-1650
• 页数: 14页
• 分类号: TP301
• 字数: 15875字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2009.01637

摘要

个体单体型问题指如何利用个体DNA测序片断数据,根据不同的优化准则确定该个体单体型的计算问题.因为技术上的限制,DNA测序实验中能直接测定的片断长度是有限的,一个片断所覆盖的最大SNP位点数k1通常小于10;出于时间和金钱的考虑,覆盖一个SNP位点的最大片断数k2也不是很大,通常约为10左右;与要测定的单体型SNP位点总数,n及所测序的DNA片断总数m相比,k1和k2均很小.在此基础上,文中对个体单体型问题最少SNP位点删除MSR和最少片段删除MFR模型进行了参数化,提出了时间复杂度分别为O(nk1k2+mlogm+mk1)和O(mk22+mlogm+nk2)求解无空隙MSR和MFR的精确算法.和Bafna等提出的时间复杂度为O(mn2)和O(m2n+m2)的精确算法相比,文中的算法效率提高了很多,具有较高的实用价值.

作者信息

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