Title: Parameterised algorithms of the individual haplotyping problem with gaps

Authors: Minzhu Xie; Jing Wang

Addresses: College of Physics and Information Science, Hunan Normal University, Changsha 410081, China; School of Information Science and Engineering, Central South University, Changsha 410083, China ' School of Information Science and Engineering, Central South University, Changsha 410083, China

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(2^knk₁k₂+mlogm+nk₂+mk₁) and O(mk₁k₂2^k+2^3kmk₂²+mlogm+nk₂+mk₁) time respectively, where k₁ is the maximum fragment length, k₂ is the maximum number of fragments covering a SNP site and k is the maximum number of holes in a fragment. Since k₁ and k₂ are both small in practice, our algorithms are efficient and applicable.

Keywords: SNPs; single-nucleotide polymorphisms; genotype; haplotypes; parameterised algorithms; individual haplotyping; gaps; DNA fragments; bioinformatics.

DOI: 10.1504/IJBRA.2013.050746

International Journal of Bioinformatics Research and Applications, 2013 Vol.9 No.1, pp.25 - 40

Published online: 06 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article