Research on parameterized algorithms of the individual haplotyping problem.

The individual haplotyping problem is a computing problem of reconstructing two haplotypes for an individual based on several optimal criteria from one's fragments sequencing data. This paper is based on the fact that the length of a fragment and the number of the fragments covering a SNP (single nucleotide polymorphism) site are both very small compared with the length of a sequenced region and the total number of the fragments and introduces the parameterized haplotyping problems. With m fragments whose maximum length is k(1), n SNP sites and the number of the fragments covering a SNP site no more than k(2), our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk(1)k(2) + m log m + nk(2) + mk(1)) and O(mk(2)(2) + mk(1) k(2) + m log m + nk(2) + mk(1))respectively. Since, the value of k(1) and k(2) are both small (about 10) in practice, our algorithms are more efficient and applicable compared with the algorithms of V. Bafna et al. of time complexity O(mn(2)) and O(m(2)n + m(3)), respectively.