A sub-cubic time algorithm for computing the quartet distance between two general trees.
Bottom Line:
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.
Affiliation: Bioinformatics Research Centre (BiRC), Aarhus University, C, F, Møllers Alle 8, DK-8000 Aarhus C, Denmark. jn@birc.au.dk.
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. No MeSH data available. |
Related In:
Results -
Collection
License getmorefigures.php?uid=PMC3141660&req=5
Mentions: or the sum of for all distinct entries in I but fixed (i, j), see Figure 6(a). We divide by two since we count each quartet twice, due to symmetry between the (k, l) and (m, n) pairs. |
View Article: PubMed Central - HTML - PubMed
Affiliation: Bioinformatics Research Centre (BiRC), Aarhus University, C, F, Møllers Alle 8, DK-8000 Aarhus C, Denmark. jn@birc.au.dk.
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.
No MeSH data available.