Optimizing Phylogenetic Supertrees Using Answer Set Programming
The supertree construction problem is about combining several phylogenetic trees with possibly conflicting information into a single tree that has all the leaves of the source trees as its leaves and the relationships between the leaves are as consistent with the source trees as possible. This leads to an optimization problem that is computationally challenging and typically heuristic methods, such as matrix representation with parsimony (MRP), are used. In this paper we consider the use of answer set programming to solve the supertree construction problem in terms of two alternative encodings. The first is based on an existing encoding of trees using substructures known as quartets, while the other novel encoding captures the relationships present in trees through direct projections. We use these encodings to compute a genus-level supertree for the family of cats (Felidae). Furthermore, we compare our results to recent supertrees obtained by the MRP method.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Ultrametric Constraint and its Application to Phylogenetics
A phylogenetic tree shows the evolutionary relationships among species. Internal nodes of the tree represent speciation events and leaf nodes correspond to species. A goal of phylogenetics is to combine such trees into l…
Inferring multiple consensus trees and supertrees using clustering: a review
Phylogenetic trees (i.e. evolutionary trees, additive trees or X-trees) play a key role in the processes of modeling and representing species evolution. Genome evolution of a given group of species is usually modeled by …
ClusteringVariational Bayesian Supertrees
Given overlapping subsets of a set of taxa (e.g. species), and posterior distributions on phylogenetic tree topologies for each of these taxon sets, how can we infer a posterior distribution on phylogenetic tree topologi…
Building alternative consensus trees and supertrees using k-means and Robinson and Foulds distance
Each gene has its own evolutionary history which can substantially differ from the evolutionary histories of other genes. For example, some individual genes or operons can be affected by specific horizontal gene transfer…
ClusteringGeometric comparison of phylogenetic trees with different leaf sets
The metric space of phylogenetic trees defined by Billera, Holmes, and Vogtmann, which we refer to as BHV space, provides a natural geometric setting for describing collections of trees on the same set of taxa. However, …