PhyDBSCAN2: Phylogenetic Tree Density-Based Spatial Clustering of Applications With Noise and Automatically Estimated Hyperparameters

Phylogenetic analyses often generate numerous tree topologies, creating conflicts that require resolution through consensus strategies. Conventional single-tree consensus methods have inherent limitations, as they do not capture topological diversity and are sensitive to outliers. This study presents a novel approach, PhyDBSCAN, that applies the density-based spatial clustering of applications with noise (DBSCAN) algorithm to ensembles of phylogenetic trees. The refined DBSCAN method includes an optimized, data-driven procedure for estimating the hyperparameters epsilon and MinPts, developed specifically for the Robinson-Foulds (RF) distance. This approach clusters trees, partitioning them into a single cluster for homogeneous data and multiple clusters for heterogeneous data, preserving topological diversity and enhancing consensus construction. PhyDBSCAN has a time complexity of 𝒪(nN2), where n is the number of leaves and N is the number of phylogenetic trees. The efficiency of the new method was assessed using real data comprising 35 genes from 43 methanogen species.