Effective haplotype assembly via maximum Boolean satisfiability

Sayyed R. Mousavi, Maryam Mirabolghasemi, Nadia Bargesteh, Majid Talebi

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


The haplotype assembly problem seeks the haplotypes of an individual from which a set of aligned SNP fragments are available. The problem is important as the haplotypes contain all the SNP information, which is essential to such studies as the analysis of the association between specific diseases and their potential genetic causes. Using Minimum Error Correction as the objective function, the problem is NP-hard, which raises the demand for effective yet affordable solutions. In this paper, we propose a new method to solve the problem by providing a novel Max-2-SAT formulation for the problem. The proposed method is compared with several well-known algorithms proposed for the problem in the literature on a recent extensive benchmark, outperforming them all by achieving solutions of higher average quality.

Original languageEnglish
Pages (from-to)593-598
Number of pages6
JournalBiochemical and Biophysical Research Communications
Issue number2
Early online date7 Dec 2010
Publication statusPublished - 14 Jan 2011
Externally publishedYes


  • Haplotype assembly
  • Heuristic algorithms
  • Max-SAT
  • Single Individual Haplotyping
  • SNP

ASJC Scopus subject areas

  • Biophysics
  • Biochemistry
  • Molecular Biology
  • Cell Biology


Dive into the research topics of 'Effective haplotype assembly via maximum Boolean satisfiability'. Together they form a unique fingerprint.

Cite this