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 k1, n SNP sites and the number of the fragments covering a SNP site no more than k2, our algorithms can solve the gapless MSR (Minimum SNP Removal) and MFR (Minimum Fragment Removal) problems in the time complexity O(nk1k2 + m log m + nk2 + mk1) and O(mk22 + mk1k2 + m log m + nk2 + mk1) respectively. Since, the value of k1 and k2 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(mn2) and O(m2n + m3), respectively.