Parameterized Algorithm of the Individual Haplotyping MSR Problem with Mate-Pairs
Minzhu Xie · Journal of Software · 2007
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 k n 2 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 -1)k 2 2 2h +(k 1 +1) 2h +nk 2 +mk 1 ) with the maximum number of SNP sites that a fragment covers k 1 (no more than n), the maximum number of the fragments covering a SNP site k 2 (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 2 ).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.