Quartet-based phylogeny reconstruction with answer set programming.
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.
Wu
Gang
G
Department of Computing Science, University of Alberta, Edmonton, Canada. wgang@cs.ualberta.ca
You
Jia-Huai
JH
Lin
Guohui
G
D000465:Algorithms; D000818:Animals; D019295:Computational Biology / Q000379:methods*; D019143:Evolution, Molecular; D016678:Genome / Q000235:genetics; D006801:Humans; D020407:Internet; D008957:Models, Genetic; D010802:Phylogeny