Efficient haplotype inference with answer set programming
Türe, Ferhan and Erdem, Esra (2008) Efficient haplotype inference with answer set programming. In: The Twenty-Third AAAI Conference on Artificial Intelligence (AAAI'08), Chicago, USA
This is the latest version of this item.
Full text not available from this repository.
Official URL: http://www.aaai.org/Library/AAAI/2008/aaai08-307.php
Identifying maternal and paternal inheritance is essential to be able to find the set of genes responsible for a particular disease. Although we have access to genotype data (genetic makeup of an individual), determining haplotypes (genetic makeup of the parents) experimentally is a costly and time consuming procedure due to technological limitations. With these biological motivations, we study a computational problem, called Haplotype Inference with Pure Parsimony (HIPP), that asks for the minimal number of haplotypes that form a given set of genotypes. We introduce a novel approach to solving HIPP, using Answer Set Programming (ASP). According to our experiments with a large number of problem instances (some automatically generated and some real), our ASP-based approach solves the most number of problems compared to other approaches based on, e.g., integer linear programming, branch and bound algorithms, SAT-based algorithms, or pseudo-boolean optimization methods.
Available Versions of this Item
Repository Staff Only: item control page