Related Experiment Video
Updated: Oct 11, 2025

A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
A simpler linear-time algorithm for the common refinement of rooted phylogenetic trees on a common leaf set
David Schaller1, Marc Hellmuth2, Peter F Stadler3,4,5,6,7,8
1Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universität Leipzig, Härtelstraße 16-18, 04107, Leipzig, Germany.
Background:
The supertree problem, i.e., the task of finding a common refinement of a set of rooted trees is an important topic in mathematical phylogenetics. The special case of a common leaf set L is known to be solvable in linear time. Existing approaches refine one input tree using information of the others and then test whether the results are isomorphic.
Results:
An O(k|L|) algorithm, LinCR, for constructing the common refinement T of k input trees with a common leaf set L is proposed that explicitly computes the parent function of T in a bottom-up approach.
Conclusion:
LinCR is simpler to implement than other asymptotically optimal algorithms for the problem and outperforms the alternatives in empirical comparisons.
Availability:
An implementation of LinCR in Python is freely available at https://github.com/david-schaller/tralda .
Related Concept Videos
Phylogenetic Trees
Evolutionary Relationships through Genome Comparisons
Phylogeny
Gene Evolution - Fast or Slow?
In contrast, regions which code...
Survival Tree
Building a Survival Tree
Constructing a...
The Tree of Life - Bacteria, Archaea, Eukaryotes

