pplacer: linear time maximum-likelihood and Bayesian phylogenetic placement of sequences onto a fixed reference tree

Area of Science:

• Bioinformatics
• Computational Biology
• Phylogenetics

Background:

• Likelihood-based phylogenetic inference is a reliable method for classifying unknown sequences.
• Traditional methods struggle with large volumes of short reads from next-generation sequencing due to computational complexity.
• Phylogenetic placement offers a solution by placing query sequences onto a fixed reference tree.

Purpose of the Study:

• Introduce pplacer, a software package for efficient phylogenetic placement and visualization.
• Address the computational challenges of applying likelihood-based phylogenetics to large sequencing datasets.

Main Methods:

• Develop an algorithm for phylogenetic placement with linear time and memory complexity.
• Implement calculation of posterior probabilities for placement uncertainty on a per-edge basis.
• Incorporate calculation of expected distance between placement locations to quantify positional uncertainty.

Main Results:

• Pplacer can place 20,000 short reads on a 1,000-taxon tree per hour per processor.
• The software demonstrates high accuracy across diverse alignment data.
• Edge uncertainty estimates effectively measure placement confidence.

Conclusions:

• Pplacer enables efficient phylogenetic placement and visualization for large read collections.
• Likelihood-based phylogenetics is now practical for large datasets using this tool.
• Pplacer is freely available as source code, binaries, and a web service.