Effective haplotype assembly via maximum Boolean satisfiability

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.

Research highlights
► A novel Max-2-SAT formulation for the haplotype assembly problem.
► Fewer variables and clauses compared to those of a recent Partial Max-SAT formulation.
► The same or smaller MEC compared to those of the Partial Max-SAT formulation.
► Novel method HapSAT based on the proposed formulation and the algorithm irots.
► Significantly improved results compared to seven distinguished algorithms.