Efficient Haplotype Inference with Answer Set Programming. Türe, F. & Erdem, E. In Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08), pages 1834-1835, 2008. Student abstractN abstract bibtex 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 prob- lem, 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). Ac- cording 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 al- gorithms, or pseudo-boolean optimization methods.
@inproceedings{DBLP:conf/aaai/TureE08,
author = {Ferhan T{\"u}re and
Esra Erdem},
title = {Efficient Haplotype Inference with Answer Set Programming},
booktitle = {Proc. of the 23rd AAAI Conference on Artificial
Intelligence (AAAI'08)},
year = {2008},
pages = {1834-1835},
bibsource = {DBLP, http://dblp.uni-trier.de},
abstract = {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 prob-
lem, 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). Ac-
cording 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 al-
gorithms, or pseudo-boolean optimization methods.},
urlN = {sa08.pdf},
note = {Student abstract},
}
Downloads: 0
{"_id":{"_str":"53424e050e946d920a000668"},"__v":1,"authorIDs":["5456f0758b01c81930000081","5df0b7a08367c8de010000ce","5df87bbedb7d9ddf01000044","5e4957a916841dde01000031","u493trvfaXuB4g9PZ"],"author_short":["Türe, F.","Erdem, E."],"bibbaseid":"tre-erdem-efficienthaplotypeinferencewithanswersetprogramming-2008","bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Ferhan"],"propositions":[],"lastnames":["Türe"],"suffixes":[]},{"firstnames":["Esra"],"propositions":[],"lastnames":["Erdem"],"suffixes":[]}],"title":"Efficient Haplotype Inference with Answer Set Programming","booktitle":"Proc. of the 23rd AAAI Conference on Artificial Intelligence (AAAI'08)","year":"2008","pages":"1834-1835","bibsource":"DBLP, http://dblp.uni-trier.de","abstract":"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 prob- lem, 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). Ac- cording 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 al- gorithms, or pseudo-boolean optimization methods.","urln":"sa08.pdf","note":"Student abstract","bibtex":"@inproceedings{DBLP:conf/aaai/TureE08,\n author = {Ferhan T{\\\"u}re and\n Esra Erdem},\n title = {Efficient Haplotype Inference with Answer Set Programming},\n booktitle = {Proc. of the 23rd AAAI Conference on Artificial\n Intelligence (AAAI'08)},\n year = {2008},\n pages = {1834-1835},\n bibsource = {DBLP, http://dblp.uni-trier.de},\n abstract = {Identifying maternal and paternal inheritance is essential to\nbe able to find the set of genes responsible for a particular\ndisease. Although we have access to genotype data (genetic\nmakeup of an individual), determining haplotypes (genetic\nmakeup of the parents) experimentally is a costly and time\nconsuming procedure due to technological limitations. With\nthese biological motivations, we study a computational prob-\nlem, called Haplotype Inference with Pure Parsimony (HIPP),\nthat asks for the minimal number of haplotypes that form a\ngiven set of genotypes. We introduce a novel approach to\nsolving HIPP, using Answer Set Programming (ASP). Ac-\ncording to our experiments with a large number of problem\ninstances (some automatically generated and some real), our\nASP-based approach solves the most number of problems\ncompared to other approaches based on, e.g., integer linear\nprogramming, branch and bound algorithms, SAT-based al-\ngorithms, or pseudo-boolean optimization methods.},\n urlN = {sa08.pdf},\n note = {Student abstract},\n}\n\n","author_short":["Türe, F.","Erdem, E."],"key":"DBLP:conf/aaai/TureE08","id":"DBLP:conf/aaai/TureE08","bibbaseid":"tre-erdem-efficienthaplotypeinferencewithanswersetprogramming-2008","role":"author","urls":{"N":"http://193.255.135.175/papers/sa08.pdf"},"downloads":0,"html":""},"bibtype":"inproceedings","biburl":"http://193.255.135.175/papers/krrpublications.bib","downloads":0,"keywords":[],"search_terms":["efficient","haplotype","inference","answer","set","programming","türe","erdem"],"title":"Efficient Haplotype Inference with Answer Set Programming","year":2008,"dataSources":["WeBGfagwiP89ve7hM"]}