Fast and accurate distance-based phylogenetic placement using divide and conquer

Metin Balaban, Yueyu Jiang, Daniel Roush, Qiyun Zhu, Siavash Mirarab

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


Phylogenetic placement of query samples on an existing phylogeny is increasingly used in molecular ecology, including sample identification and microbiome environmental sampling. As the size of available reference trees used in these analyses continues to grow, there is a growing need for methods that place sequences on ultra-large trees with high accuracy. Distance-based placement methods have recently emerged as a path to provide such scalability while allowing flexibility to analyse both assembled and unassembled environmental samples. In this study, we introduce a distance-based phylogenetic placement method, APPLES-2, that is more accurate and scalable than existing distance-based methods and even some of the leading maximum-likelihood methods. This scalability is owed to a divide-and-conquer technique that limits distance calculation and phylogenetic placement to parts of the tree most relevant to each query. The increased scalability and accuracy enables us to study the effectiveness of APPLES-2 for placing microbial genomes on a data set of 10,575 microbial species using subsets of 381 marker genes. APPLES-2 has very high accuracy in this setting, placing 97% of query genomes within three branches of the optimal position in the species tree using 50 marker genes. Our proof-of-concept results show that APPLES-2 can quickly place metagenomic scaffolds on ultra-large backbone trees with high accuracy as long as a scaffold includes tens of marker genes. These results pave the path for a more scalable and widespread use of distance-based placement in various areas of molecular ecology.

Original languageEnglish (US)
Pages (from-to)1213-1227
Number of pages15
JournalMolecular Ecology Resources
Issue number3
StatePublished - Apr 2022


  • distance-based methods
  • metagenomics
  • microbiome
  • phylogenetic placement

ASJC Scopus subject areas

  • Biotechnology
  • Ecology, Evolution, Behavior and Systematics
  • Genetics


Dive into the research topics of 'Fast and accurate distance-based phylogenetic placement using divide and conquer'. Together they form a unique fingerprint.

Cite this