有Mate-Pairs的个体单体型MSR问题的参数化算法

王建新谢民主陈建二

中南大学;

摘要：

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2kn2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k1-1)k222h+(k1+1)2h+nk2+m…展开v

关键词：单核苷酸多态性、基因型、单体型、参数化算法、计算复杂度

所属期刊栏目：18

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

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

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

页数：共13页

页码：2070-2082