Title: Efficient fast heuristic algorithms for minimum error correction haplotyping from SNP fragments

Authors: Maryam Pourkamali Anaraki; Mehdi Sadeghi

Addresses: Department of Computer Engineering, Science and Research Branch, Islamic Azad University, P.O. Box 14515/775, Tehran, Iran ' National Institute of Genetic Engineering and Biotechnology, P.O. Box 14965/161, Tehran, Iran; School of Biological Sciences, Institute for Research in Fundamental Sciences, Tehran, Iran

Abstract: Availability of complete human genome is a crucial factor for genetic studies to explore possible association between the genome and complex diseases. Haplotype, as a set of single nucleotide polymorphisms (SNPs) on a single chromosome, is believed to contain promising data for disease association studies, detecting natural positive selection and recombination hotspots. Various computational methods for haplotype reconstruction from aligned fragment of SNPs have already been proposed. This study presents a novel approach to obtain paternal and maternal haplotypes form the SNP fragments on minimum error correction (MEC) model. Reconstructing haplotypes in MEC model is an NP-hard problem. Therefore, our proposed methods employ two fast and accurate clustering techniques as the core of their procedure to efficiently solve this ill-defined problem. The assessment of our approaches, compared to conventional methods, on two real benchmark datasets, i.e., ACE and DALY, proves the efficiency and accuracy.

Keywords: computational biology; haplotyping; MEC model; SNP fragments; principal direction divisive partitioning; k-harmonic means; fast heuristics; minimum error correction; single nucleotide polymorphisms; disease association; paternal haplotypes; maternal haplotypes; haplotype reconstruction; clustering.

DOI: 10.1504/IJCBDD.2014.066543

International Journal of Computational Biology and Drug Design, 2014 Vol.7 No.4, pp.358 - 368

Received: 13 Jun 2013
Accepted: 31 Jan 2014
Published online: 25 Apr 2015 *

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