Frequency() returns the frequency-difference consensus: a split is retained
when it occurs strictly more often than every split that conflicts with it.
Equivalently, among each set of mutually incompatible splits, the consensus
keeps a split only if it is strictly more frequent than all its rivals.
Value
Frequency() returns the consensus tree, an object of class phylo,
rooted as in the first entry of trees.
Details
The frequency-difference consensus is at least as resolved as the
majority-rule consensus (Majority()) – a split in more than half the
trees is necessarily more frequent than any conflicting split – and is
contained within the greedy consensus (Greedy()). The retained splits
are mutually compatible, so they define a valid tree.
This implementation ports the near-linear \(O(kn \log n)\) algorithm of Jansson et al. (2024) from their FDCT reference C++ (used with permission): cluster frequencies are computed by a divide-and-conquer labelling with radix sort, and conflicting lower-frequency clusters are filtered out using centroid-path decomposition, lowest-common-ancestor and range-minimum queries, and tree contraction, avoiding the explicit \(O(s^2)\) pairwise compatibility matrix used previously.
References
Jansson J, Sung W, Tabatabaee SA, Yang Y (2024). “A Faster Algorithm for Constructing the Frequency Difference Consensus Tree.” In Beyersdorff O, Kanté MM, Kupferman O, Lokshtanov D (eds.), 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), volume 289 of Leibniz International Proceedings in Informatics (LIPIcs), 43:1–43:17. doi:10.4230/LIPIcs.STACS.2024.43 .
See also
Closely related: Majority(), MajorityPlus(),
Greedy().
Other consensus methods:
Adams(),
Average(),
Greedy(),
Local(),
Loose(),
Majority(),
MajorityPlus(),
Quartet(),
RStar(),
Strict()
Examples
trees <- ape::as.phylo(0:5, 8)
Frequency(trees)
#>
#> Phylogenetic tree with 8 tips and 6 internal nodes.
#>
#> Tip labels:
#> t1, t2, t8, t7, t6, t3, ...
#>
#> Rooted; no branch length.