Dataset Information

A sub-cubic time algorithm for computing the quartet distance between two general trees.

ABSTRACT:

Background

When inferring phylogenetic trees different algorithms may give different trees. To study such effects a measure for the distance between two trees is useful. Quartet distance is one such measure, and is the number of quartet topologies that differ between two trees.

Results

We have derived a new algorithm for computing the quartet distance between a pair of general trees, i.e. trees where inner nodes can have any degree ? 3. The time and space complexity of our algorithm is sub-cubic in the number of leaves and does not depend on the degree of the inner nodes. This makes it the fastest algorithm so far for computing the quartet distance between general trees independent of the degree of the inner nodes.

Conclusions

We have implemented our algorithm and two of the best competitors. Our new algorithm is significantly faster than the competition and seems to run in close to quadratic time in practice.

SUBMITTER: Nielsen J

PROVIDER: S-EPMC3141660 | biostudies-literature | 2011 Jun

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

A sub-cubic time algorithm for computing the quartet distance between two general trees.

Nielsen Jesper J Kristensen Anders K AK Mailund Thomas T Pedersen Christian Ns CN

Algorithms for molecular biology : AMB 20110603

<h4>Background</h4>When inferring phylogenetic trees different algorithms may give different trees. To study such effects a measure for the distance between two trees is useful. Quartet distance is one such measure, and is the number of quartet topologies that differ between two trees.<h4>Results</h4>We have derived a new algorithm for computing the quartet distance between a pair of general trees, i.e. trees where inner nodes can have any degree ≥ 3. The time and space complexity of our algorit ...[more]

PMID: 21639882

Similar Datasets

Project description:BackgroundA long recognized problem is the inference of the supertree S that amalgamates a given set {G(j)} of trees G(j), with leaves in each G(j) being assigned homologous elements. We ground on an approach to find the tree S by minimizing the total cost of mappings ?(j) of individual gene trees G(j) into S. Traditionally, this cost is defined basically as a sum of duplications and gaps in each ?(j). The classical problem is to minimize the total cost, where S runs over the set of all trees that contain an exhaustive non-redundant set of species from all input G(j).ResultsWe suggest a reformulation of the classical NP-hard problem of building a supertree in terms of the global minimization of the same cost functional but only over species trees S that consist of clades belonging to a fixed set P (e.g., an exhaustive set of clades in all G(j)). We developed a deterministic solving algorithm with a low degree polynomial (typically cubic) time complexity with respect to the size of input data. We define an extensive set of elementary evolutionary events and suggest an original definition of mapping ? of tree G into tree S. We introduce the cost functional c(G, S, f) and define the mapping ? as the global minimum of this functional with respect to the variable f, in which sense it is a generalization of classical mapping ?. We suggest a reformulation of the classical NP-hard mapping (reconciliation) problem by introducing time slices into the species tree S and present a cubic time solving algorithm to compute the mapping ?. We introduce two novel definitions of the evolutionary scenario based on mapping ? or a random process of gene evolution along a species tree.ConclusionsDeveloped algorithms are mathematically proved, which justifies the following statements. The supertree building algorithm finds exactly the global minimum of the total cost if only gene duplications and losses are allowed and the given sets of gene trees satisfies a certain condition. The mapping algorithm finds exactly the minimal mapping ?, the minimal total cost and the evolutionary scenario as a minimum over all possible distributions of elementary evolutionary events along the edges of tree S. The algorithms and their effective software implementations provide useful tools in many biological studies. They facilitate processing of voluminous tree data in acceptable time still largely avoiding heuristics. Performance of the tools is tested with artificial and prokaryotic tree data.ReviewersThis article was reviewed by Prof. Anthony Almudevar, Prof. Alexander Bolshoy (nominated by Prof. Peter Olofsson), and Prof. Marek Kimmel.

Dataset Information

A sub-cubic time algorithm for computing the quartet distance between two general trees.

Background

Results

Conclusions

Publications

A sub-cubic time algorithm for computing the quartet distance between two general trees.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets