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 both speed and accuracy and scales to trees with more than a hundred thousand taxa. We apply PhytClust across cancer genomics, avian phylogenomics, bacterial and archaea phylogenetics, and plant genomics to demonstrate PhytClust's varied applicability. By providing a standardized method for taxa clustering within phylogenetic trees, PhytClust yields reproducible, optimal and computationally efficient clusters.