单体型组装问题MEC/GI模型的参数化算法

摘要：

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

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

所属期刊栏目：18

分类号：Q5(生物化学)

资助基金：国家自然科学基金60433020;教育部跨世纪优秀人才培养计划NCET-05-0683;教育部创新团队发展基金IRT0661;湖南省教育厅科研项目06C526

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

页数：共7页

页码：422-428