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.

Item Type:Papers in Conference Proceedings
ID Code:9623
Deposited By:Esra Erdem
Deposited On:26 Oct 2008 19:04
Last Modified:28 Oct 2008 08:57

Available Versions of this Item

Repository Staff Only: item control page