Adams consensus tree

Adams() returns the Adams consensus (Adams 1972) , a summary of a set of rooted trees.

Usage

Adams(trees)

Arguments

trees: A list of trees, or a multiPhylo object; all entries must share the same leaf labels.

Value

Adams() returns the consensus tree, an object of class phylo, rooted by construction. (A tree whose root is multifurcating reports ape::is.rooted() == FALSE, which tests only for a two-child root; the Adams tree is rooted regardless.)

Details

The Adams consensus is defined recursively. At the top level, the leaves are partitioned into the coarsest grouping that every input tree refines: two leaves fall in the same block if and only if, in every input tree, they sit below the same child of the most recent common ancestor of the full leaf set. Each block becomes a child of the consensus root, and the construction repeats within each block.

Unlike the split-based methods (Strict(), Majority(), Loose(), Greedy(), MajorityPlus(), Frequency()), the Adams consensus can contain a cluster that appears in no individual input tree, and it depends on how the input trees are rooted: it is a statement about nesting, not about unrooted bipartitions. Input trees are treated as rooted on their current root; root the trees as you intend before calling Adams().

This implementation employs the asymptotically efficient \(O(kn \log n)\) algorithm of (Jansson et al. 2017) (their New_Adams_consensus_k, from the FACT toolkit of Jansson and colleagues, used with permission), realised in C++. Rather than recomputing Adams' partition from scratch at every recursion level, it follows a centroid path through each input tree in unison, expanding the shared "spine" of the consensus iteratively and recursing only on the off-spine blocks (each at most half the leaves). The Adams consensus tree is unique, so the result is identical to the classical recursive definition; only the running time differs.

References

Adams EN (1972). “Consensus techniques and the comparison of taxonomic trees.” Systematic Zoology, 21(4), 390–397. doi:10.2307/2412432 .

Jansson J, Li Z, Sung W (2017). “On finding the Adams consensus tree.” Information and Computation, 256, 334–347. doi:10.1016/j.ic.2017.08.002 .

Examples

# Two rooted trees that disagree only on the position of one leaf
trees <- c(ape::read.tree(text = "(((a, b), c), d);"),
           ape::read.tree(text = "(((a, b), d), c);"))
Adams(trees) # keeps the clade (a, b); leaves c, d unresolved at the root
#> 
#> Phylogenetic tree with 4 tips and 2 internal nodes.
#> 
#> Tip labels:
#>   d, c, b, a
#> 
#> Unrooted; no branch length.