title: Parameterised algorithms of the individual haplotyping problem with gaps.
abstract: The individual haplotyping problem is the computational problem of constructing two haplotypes from one's DNA fragments. We proposed parameterised algorithms for computational models Minimum SNP Removal (MSR) and Minimum Fragment Removal (MFR) of the problem. For m DNA fragments and n SNPs, our algorithms solve MSR and MFR in O(2knk1k2+m1ogm+nk2+mk1) and O(mk1k22k+23kmk22+m1ogm+nk2+mk1 time respectively, where k1 is the maximum fragment length, k2 is the maximum number of fragments covering a SNP site and k is the maximum number of holes in a fragment. Since k1 and k2 are both small in practice, our algorithms are efficient and applicable.
authors.affiliation: College of Physics and Information Science, Hunan Normal University, Changsha 410081, China.
authors.forename: Minzhu
authors.initials: M
authors.lastname: Xie
authors.forename: Jing
authors.initials: J
authors.lastname: Wang
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D006239:Haplotypes; D020641:Polymorphism, Single Nucleotide; D017422:Sequence Analysis, DNA