Scaling DEPP phylogenetic placement to ultra-large reference trees: a tree-aware ensemble approach

Area of Science:

• Bioinformatics
• Computational Biology
• Machine Learning

Background:

• Phylogenetic placement of DNA sequences is vital for sample identification in biomedical sciences.
• Current methods struggle to scale with the increasing size of reference trees, limiting analysis of large datasets.
• The DEPP method, using metric learning, faces computational challenges with large-scale phylogenetic trees due to quadratic distance matrix computation.

Purpose of the Study:

• To develop a scalable method for phylogenetic placement on very large species trees.
• To overcome the computational limitations of existing metric learning approaches like DEPP.
• To enable accurate analysis of millions of sequences on extensive reference phylogenies.

Main Methods:

• Exploration of divide-and-conquer strategies for training ensembles of DEPP models.
• Development of the C-DEPP (Chunked DEPP) method incorporating specialized techniques for quasi-linear scaling.
• Application of C-DEPP to large-scale phylogenetic datasets, including the Greengenes2 reference tree.

Main Results:

• C-DEPP achieves quasi-linear scaling, overcoming the quadratic complexity of traditional metric learning.
• The method successfully scales to reference trees with hundreds of thousands of species.
• C-DEPP enabled the placement of 20 million 16S fragments onto the Greengenes2 tree in 41 hours.

Conclusions:

• C-DEPP offers a computationally efficient and accurate solution for large-scale phylogenetic placement.
• The developed method significantly advances the scalability of marker-gene and genome-wide data analyses.
• Freely available software and datasets facilitate broader adoption and further research.