| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | 个体单体型问题参数化算法研究 |
| 作者 | 谢民主1),2) 陈建二1) 王建新1) |
| 作者单位 | 1)(中南大学信息科学与工程学院 长沙 410083) 2)(湖南师范大学物理与信息科学学院 长沙 410081) |
| 发表年份 | 2009 |
| 发表月份 | 8期(1637—1650) |
| 文章摘要 | 摘要 个体单体型问题指如何利用个体DNA测序片断数据，根据不同的优化准则确定该个体单体型的计算问题.因为技术上的限制，DNA测序实验中能直接测定的片断长度是有限的，一个片断所覆盖的最大SNP位点数k1通常小于10；出于时间和金钱的考虑，覆盖一个SNP位点的最大片断数k2也不是很大，通常约为10左右；与要测定的单体型SNP位点总数n及所测序的DNA片断总数m相比，k1和k2均很小.在此基础上，文中对个体单体型问题最少SNP位点删除MSR和最少片段删除MFR模型进行了参数化，提出了时间复杂度分别为O(nk1k2+mlogm+mk1)和O(mk22+mk1k2+mlogm+nk2)求解无空隙MSR和MFR的精确算法.和Bafna等提出的时间复杂度为O(mn2)和O(m2n+m3)的精确算法相比，文中的算法效率提高了很多，具有较高的实用价值. 关键词：单核苷酸多态性；单体型；参数化算法；最少SNP位点删除；最少片断删除 中图法分类号：TP301 DOI号: 10.3724/SP.J.1016.2009.01637 |