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

个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2^kn²m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)的新算法,其中,k₁为一个片断覆盖的最大SNP位点数(不大于n),k₂为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k₂).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值.

Parameterized Algorithm of the Individual Haplotyping MSR Problem with Mate-Pairs

The individual haplotyping MSR(minimum SNP removal)problem is the computational problem of inducing an individual's haplotypes from one's DNA fragments sequencing data by dropping minimum SNPs (single-nucleotide polymorphisms).To solve the problem,Bafna,et al.had provided an algorithm of time complexity O(2^kn²m)with the number of fragments m,the SNP sites n,the maximum number of holes k in a fragment.In the case that there are some Mate-Pairs,since the number of holes in a Mate-Pair can reach 100, Bafna's algorithm is impracticable.Based on the characters of DNA fragments,this paper presents a new algorithm of time complexity O((n-1)(k₁-1)k₂2^2h+(k₁+1)^2h+nk₂+mk₁)with the maximum number of SNP sites that a fragment covers k₁(no more than n),the maximum number of the fragments covering a SNP site k₂(usually no more than 19) and the maximum number of fragments covering a SNP site whose value is unknown at the SNP site h(no more than k₂).Since the time complexity is not directly related with k,the algorithm can deal with the MSR problem with Mate-Pairs efficiently,and is more scalable and applicable in practice.