Testing the agreement of trees with internal labels

A semi-labeled tree is a tree where all leaves as well as, possibly, some internal nodes are labeled with taxa. Semi-labeled trees encompass ordinary phylogenetic trees and taxonomies. Suppose we are given a collection [Formula: see text] of semi-labeled trees, called input trees, over partially overlapping sets of taxa. The agreement problem asks whether there exists a tree [Formula: see text], called an agreement tree, whose taxon set is the union of the taxon sets of the input trees such that the restriction of [Formula: see text] to the taxon set of [Formula: see text] is isomorphic to [Formula: see text], for each [Formula: see text]. The agreement problems is a special case of the supertree problem, the problem of synthesizing a collection of phylogenetic trees with partially overlapping taxon sets into a single supertree that represents the information in the input trees. An obstacle to building large phylogenetic supertrees is the limited amount of taxonomic overlap among the phylogenetic studies from which the input trees are obtained. Incorporating taxonomies into supertree analyses can alleviate this issue.

We give a [Formula: see text] algorithm for the agreement problem, where n is the total number of distinct taxa in [Formula: see text], k is the number of trees in [Formula: see text], and [Formula: see text] is the maximum number of children of a node in [Formula: see text].

Our algorithm can aid in integrating taxonomies into supertree analyses. Our computational experience with the algorithm suggests that its performance in practice is much better than its worst-case bound indicates.