Accurate single individual haplotyping based on HuRef dataset using HapSAT algorithm

Ehsan Haghshenas, Nadia Barjaste, Sayyed Rasoul Mousavi

Research output: Contribution to journalArticlepeer-review


Studying haplotypes is an important approach for investigation of genetic variations in the human genome because they contain a lot of information related to these types of variations. The haplotype assembly problem is to reconstruct two haplotypes for an individual using a set of aligned single nucleotide polymorphism (SNP) fragments from the two haplotypes (related to a particular chromosome). This problem is recognised as an NP-hard problem due to possible sequencing errors. Therefore, in practice, heuristic algorithms are used for finding satisfactory solutions to this problem. In this paper, an optimised reimplementation of HapSAT algorithm has been used to find haplotypes for HuRef dataset. Finding more accurate haplotypes based on this dataset is of considerable importance, because HuRef haplotypes are widely used in some researches (in biology, medicine, and pharmacy). Since the HapSAT algorithm provides significantly superior results compared to previously proposed algorithms, assembled haplotypes using HapSAT algorithm will be very useful for future researches.

Original languageEnglish
Pages (from-to)274-285
Number of pages12
JournalInternational Journal of Functional Informatics and Personalised Medicine
Issue number3-4
Publication statusPublished - 22 Mar 2015
Externally publishedYes

Bibliographical note

Publisher Copyright:
Copyright © 2014 Inderscience Enterprises Ltd.


  • Haplotype assembly problem
  • Heuristic algorithm
  • HuRef dataset
  • Max-SAT
  • Minimum error correction (MEC) model
  • Single nucleotide polymorphism
  • SNP

ASJC Scopus subject areas

  • Clinical Neurology


Dive into the research topics of 'Accurate single individual haplotyping based on HuRef dataset using HapSAT algorithm'. Together they form a unique fingerprint.

Cite this