Title :
Quartet-Based Phylogeny Reconstruction with Answer Set Programming
Author :
Wu, Gang ; You, Jia-Huai ; Lin, Guohui
Author_Institution :
Univ. of Alberta, Edmonton
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;
Journal_Title :
Computational Biology and Bioinformatics, IEEE/ACM Transactions on
DOI :
10.1109/TCBB.2007.1008