title: Efficient fast heuristic algorithms for minimum error correction haplotyping from SNP fragments.
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.
authors.affiliation: Department of Computer Engineering, Science and Research Branch, Islamic Azad University, P.O. Box 14515/775, Tehran, Iran.
authors.forename: Maryam Pourkamali
authors.initials: MP
authors.lastname: Anaraki
authors.affiliation: 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.
authors.forename: Mehdi
authors.initials: M
authors.lastname: Sadeghi
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D004247:DNA / Q000235:genetics*; D053938:DNA Fragmentation; D004252:DNA Mutational Analysis / Q000379:methods*; D015894:Genome, Human / Q000235:genetics*; D006239:Haplotypes / Q000235:genetics*; D006801:Humans; D008969:Molecular Sequence Data; D010363:Pattern Recognition, Automated; D020641:Polymorphism, Single Nucleotide / Q000235:genetics*; D015203:Reproducibility of Results; D012680:Sensitivity and Specificity
chemical_list: D004247:DNA