Efficient Haplotype Inference with Answer Set Programming

Abstract

Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular dis-ease. However, due to technological limitations, we have ac-cess to genotype data (genetic makeup of an individual), and determining haplotypes (genetic makeup of the parents) ex-perimentally is a costly and time consuming procedure. With these biological motivations, we study a computational prob-lem, called Haplotype Inference by Pure Parsimony (HIPP), that asks for the minimal number of haplotypes that form a given set of genotypes. HIPP has been studied using inte-ger linear programming, branch and bound algorithms, SAT-based algorithms, or pseudo-boolean optimization methods. We introduce a new approach to solving HIPP, using An-swer Set Programming (ASP). According to our experiments with a large number of problem instances (some automat-ically generated and some real), our ASP-based approach solves the most number of problems compared with other approaches. Due to the expressivity of the knowledge rep-resentation language of ASP, our approach allows us to solve variations of HIPP, e.g., with additional domain specific in-formation, such as patterns/parts of haplotypes observed for some gene family, or with some missing genotype informa-tion. In this sense, the ASP-based approach is more general than the existing approaches to haplotype inference.