Local() returns the local consensus
(Jansson et al. 2018)
of a set of rooted trees.
Usage
Local(trees, type = c("rooted", "induced"))Details
The local consensus is the most conservative tree consistent with the rooted
triplets shared by every input tree. Two variants are offered: the minimum
rooted local consensus (MinRLC, type = "rooted") and the minimum induced
local consensus (MinILC, type = "induced"), which differ in how the
resolution of the result is scored. The tree is assembled from the Aho-graph
decomposition of the common-triplet set by dynamic programming over the
subsets of leaves.
The MinRLC and MinILC variants, and the exact exponential-time algorithm used
here to construct them, are due to (Jansson et al. 2018)
;
this is a direct port of the reference C++ from their FDCT_new toolkit, used
with permission.
Complexity note: the algorithm is exponential, so Local() is limited to
n <= 20 leaves. Running time depends not only on n but on how congruent
the input trees are: when few rooted triplets are shared (highly incongruent
trees, particularly with type = "induced"), the dynamic programming can
become intractable even within the 20-leaf limit. A long-running call can be
interrupted (e.g. with Ctrl-C).
No-valid-consensus: when the entire leaf set forms a single inseparable
Aho-graph component (no common triplets separate any pair), the algorithm has
no valid consensus; Local() then returns a star tree (all leaves attached
directly to the root, fully unresolved). The reference binary reports
"No valid consensus found." for this case.
Input trees are treated as rooted on their current root; root the trees as
you intend before calling Local().
References
Jansson J, Rajaby R, Sung W (2018). “Minimal phylogenetic supertrees and local consensus trees.” AIMS Medical Science, 5(2), 181–203. doi:10.3934/medsci.2018.2.181 .
See also
Closely related: Strict(), Majority(), Adams().
Other consensus methods:
Adams(),
Average(),
Frequency(),
Greedy(),
Loose(),
Majority(),
MajorityPlus(),
Quartet(),
RStar(),
Strict()
Examples
# Two trees that agree on one cherry but disagree on overall topology
t1 <- ape::read.tree(text = "(1,((2,3),4));")
t2 <- ape::read.tree(text = "(1,((2,4),3));")
Local(list(t1, t2), "rooted") # keeps clade {2,3,4} only
#>
#> Phylogenetic tree with 4 tips and 2 internal nodes.
#>
#> Tip labels:
#> 1, 2, 3, 4
#>
#> Rooted; no branch length.