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

Department of Computer Science, University of Sherbrooke, 2500, boulevard de l’Université, J1K 2R1, QC, Canada

^* e-mail: This email address is being protected from spambots. You need JavaScript enabled to view it.

Abstract

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 𝒪(nN²), 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.