PhytClust: Efficient and Optimal Monophyletic Partitioning of Rooted Phylogenetic Trees

Phylogenetic trees play a fundamental role in elucidating evolutionary relationships among taxa. Clustering taxa remains a major challenge across diverse biological domains such as cancer genomics, microbial systematics, and phylogenomics. Several methods partition taxa in phylogenetic trees into clusters, but these approaches face key limitations. Many rely on user-defined distance thresholds, whose choice often depends on prior knowledge and may be difficult to justify consistently across datasets. More broadly, existing methods often differ in how clusters are defined and commonly rely on heuristics or user-specified criteria to make the search space tractable for large trees. Here, we present PhytClust, a threshold-free algorithm that partitions trees into monophyletic subtrees (clusters) by identifying groups of taxa with low within-cluster dispersion. For a fixed number of clusters, PhytClust finds the exact global optimum under this objective and then selects the optimal number of clusters using a cluster-validity index. The resulting partitions are reproducible and reflect both tree topology and branch lengths. In simulated datasets, PhytClust outperforms existing methods in accuracy and remains competitive in speed while scaling to trees with more than a hundred thousand taxa. We apply it to viral and bacterial phylogenies, single-cell cancer phylogenies, archaeal and avian phylogenomics, gene family evolution, and plant conservation genomics. By providing a standardized method for partitioning phylogenetic trees, PhytClust yields partitions that are reproducible, exactly optimal under a stated objective, and computable on large trees.