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. (Request a copy)


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.
Item Type: Papers in Conference Proceedings
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Depositing User: Esra Erdem
Date Deposited: 26 Oct 2008 19:04
Last Modified: 26 Apr 2022 08:46
URI: https://research.sabanciuniv.edu/id/eprint/9623

Available Versions of this Item

Actions (login required)

View Item
View Item