“School of Biological”

Back to Papers Home
Back to Papers of School of Biological

Paper   IPM / Biological / 14586
School of Biological Sciences
  Title:   Efficient fast heuristic algorithms for minimum error correction haplotyping from SNP fragments
1.  Maryam Pourkamali Anarak
2.  Mehdi Sadeghi
3.  .
  Status:   Published
  Journal: International journal of computational biology and drug design
  No.:  4
  Vol.:  7
  Year:  2014
  Pages:   358 - 368
  Supported by:  IPM
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.

Download TeX format
back to top
scroll left or right