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

摘要：

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

关键词：生物信息学、单体型检测、参数化算法、单核苷酸多态性

所属期刊栏目：43

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金60433020;湖南省教育厅科研项目06C526

在线出版日期：2008-03-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：57-60