DocumentCode :
1151724
Title :
Quartet-Based Phylogeny Reconstruction with Answer Set Programming
Author :
Wu, Gang ; You, Jia-Huai ; Lin, Guohui
Author_Institution :
Univ. of Alberta, Edmonton
Volume :
4
Issue :
1
fYear :
2007
Firstpage :
139
Lastpage :
152
Abstract :
In this paper, a new representation is presented for the maximum quartet consistency (MQC) problem, where solving the MQC problem becomes searching for an ultrametric matrix that satisfies a maximum number of given quartet topologies. A number of structural properties of the MQC problem in this new representation are characterized through formulating into answer set programming, a recent powerful logic programming tool for modeling and solving search problems. Using these properties, a number of optimization techniques are proposed to speed up the search process. The experimental results on a number of simulated data sets suggest that the new representation, combined with answer set programming, presents a unique perspective to the MQC problem.
Keywords :
biology computing; evolution (biological); search problems; answer set programming; maximum quartet consistency problem; quartet based phylogeny reconstruction; search problems; ultrametric matrix; Application specific processors; DNA; Evolution (biology); Genomics; History; Logic programming; Phylogeny; Protein sequence; Search problems; Topology; Answer Set Programming (ASP); Maximum Quartet Consistency (MQC); Phylogeny; quartet; ultrametric matrix.; Algorithms; Animals; Computational Biology; Evolution, Molecular; Genome; Humans; Internet; Models, Genetic; Phylogeny;
fLanguage :
English
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
Publisher :
ieee
ISSN :
1545-5963
Type :
jour
DOI :
10.1109/TCBB.2007.1008
Filename :
4104467
Link To Document :
بازگشت