有mate-pairs的个体单体型msr问题的参数化算法

个体单体型msr(minimumsnpremoval)问题是指如何利用个体的基因测序片断数据去掉最少的snp(single-nucleotidepolymorphisms)位点,以确定该个体单体型的计算问题.对此问题,bafna等人提出了时间复杂度为o(2kn2m)的算法,其中,m为dna片断总数,n为snp位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个mate-pair片段中洞的个数可以达到100,因此,在片段数据中有mate-pair的情况下,bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为o((n-1)(k1-1)k222h+(k1+1)2h+nk2+mk1)的新算法,其中,k1为一个片断覆盖的最大snp位点数(不大于n),k2为覆盖同一snp位点的片段的最大数(通常不大于19),h为覆盖同一snp位点且在该位点取空值的片断的最大数(不大于k2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有mate-pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.