Efficient Haplotype Inference with Boolean Satisfiability

Inês Lynce, João Marques-SilvaAAAI 2006

Introduction

Haplotype inference is a fundamental challenge in modern genomics, essential for identifying genetic variants associated with complex diseases. While humans are diploid organisms with two sets of chromosomes, standard genotyping technologies often produce conflated data that lacks phase information—the specific sequence of nucleotides on a single chromosome, known as a haplotype. The Haplotype Inference by Pure Parsimony (HIPP) problem seeks to resolve this by finding the minimum number of distinct haplotypes required to explain a given set of genotypes. Although HIPP follows the principle of parsimony, it is computationally NP-hard, posing significant hurdles for traditional Integer Linear Programming (ILP) and branch-and-bound solvers.

The SHIPs Methodology

To address these computational bottlenecks, researchers developed SHIPs (SAT-based Haplotype Inference by Pure Parsimony), a tool that reformulates HIPP as a Boolean Satisfiability (SAT) problem. SHIPs shifts the focus from traditional optimization to a series of logic-based decision problems.

SAT Encoding and Optimization

The core of SHIPs is a Conjunctive Normal Form (CNF) model. It utilizes "selector variables" to assign haplotypes to genotypes and "bit variables" to define the haplotypes themselves. To manage the vast search space, SHIPs incorporates several critical optimizations:

  1. Symmetry Breaking: To prevent the solver from exploring redundant permutations of the same haplotype set, SHIPs enforces a strict lexicographic ordering ($h_1 < h_2 < \dots < h_r$).
  2. Lower Bound Computation: SHIPs constructs an "incompatibility graph" where nodes represent genotypes and edges connect those that cannot share haplotypes. By identifying a maximal clique in this graph, the tool establishes a high-quality lower bound for the number of haplotypes, significantly narrowing the search range.
  3. Structural Simplification: Before the SAT solver is invoked, SHIPs prunes the dataset by removing duplicate genotypes, duplicate sites, and complemented sites, resulting in a more compact and efficient model.

Experimental Evaluation

The performance of SHIPs was benchmarked against 229 problem instances categorized into three groups: Uniform (randomly picked haplotypes), Non-uniform (biased selection simulating realistic populations), and Hapmap (real-world data from the International HapMap Project).

Robustness and Success Rate

SHIPs demonstrated remarkable robustness across all datasets. As shown in the comparative analysis, SHIPs successfully solved 228 out of 229 instances, significantly outperforming previous state-of-the-art tools like Hapar, which solved 190, and older ILP-based methods like RTIP and Poly.

Table 1: Success rates of SHIPs compared to other haplotype inference tools across various benchmarks.

Computational Efficiency

Beyond its success rate, SHIPs offers a transformative improvement in speed. On non-trivial instances, SHIPs was consistently one to four orders of magnitude faster than Hapar. This efficiency is visualized in the scatter plot below, where the majority of data points reside well above the diagonal, indicating that SHIPs completes tasks in a fraction of the time required by its competitors.

Figure 1: Execution time comparison (in seconds) between Hapar and SHIPs on a log-log scale.

Conclusion

SHIPs represents a significant advancement in haplotype inference, proving that SAT-based approaches can vastly outperform traditional ILP methods for parsimony-based problems. By integrating graph-theoretic lower bounds and symmetry breaking, SHIPs provides a scalable solution for complex genomic datasets. Future research will focus on further optimizing CNF encodings and extending the model to handle the noisy or missing data common in experimental laboratory results.

Summary updated

BibTeX
@inproceedings{lynce2006efficient,
  author = {Inês Lynce and João Marques-Silva},
  title = {{Efficient Haplotype Inference with Boolean Satisfiability}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure