Performance, Accuracy, and Web Server for Evolutionary Placement of Short Sequence Reads under Maximum Likelihood

By Simon A. Berger, Denis Krompass, Alexandros Stamatakis. Systematic Biology, 2011

462 citations recorded by the source corpus.

Abstract We present an evolutionary placement algorithm (EPA) and a Web server for the rapid assignment of sequence fragments (short reads) to edges of a given phylogenetic tree under the maximum-likelihood model. The accuracy of the algorithm is evaluated on several real-world data sets and compared with placement by pair-wise sequence comparison, using edit distances and BLAST. We introduce a slow and accurate as well as a fast and less accurate placement algorithm. For the slow algorithm, we develop additional heuristic techniques that yield almost the same run times as the fast version with only a small loss of accuracy. When those additional heuristics are employed, the run time of the more accurate algorithm is comparable with that of a simple BLAST search for data sets with a high number of short query sequences. Moreover, the accuracy of the EPA is significantly higher, in particular when the sample of taxa in the reference topology is sparse or inadequate. Our algorithm, which has been integrated into RAxML, therefore provides an equally fast but more accurate alternative to BLAST for tree-based inference of the evolutionary origin and composition of short sequence reads. We are also actively developing a Web server that offers a freely available service for computing read placements on trees using the EPA.

Subfields: Artificial Intelligence, Genetics, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/a774e012a68e3734bbf6f9b4070007833595b577

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Genetics

In Molecular Biology

Citations in the corpus

A general species delimitation method with applications to phylogenetic placements (2013, methodology): “Phylogeny-aware methods for identifying reads were introduced independently and simultaneously with the evolutionary placement algorithm (EPA; Berger et al. , 2011) and pplacer (Matsen et al. , 2010).”
Aligning short reads to reference alignments and trees (2011, methodology): “We have already used this method for QS generation in (Berger et al., 2011) to create simulated short read sequences that emulate reads obtained from a high-throughput sequencer.”
The EMBL-EBI search and sequence analysis tools APIs in 2019 (2019, background): “Tools such as PromoterWise (19) and Wise2DBA (20) along with ScanProsite (21), MAFFT addseq (22) and RaXML-EPA (23) have been retired.”
Interactive tree of life (iTOL) v3: an online tool for the display and annotation of phylogenetic and other trees (2016, methodology): “A new, recently proposed file format for phylogenetic placements, i.e. mappings of environmental sequence data (e.g. short reads) into a phylogenetic tree (11) is also supported, making iTOL the first tool which can visualize these files generated by EPA (12) and pplacer (13).”
Accurate extension of multiple sequence alignments using a phylogeny-aware graph algorithm (2012, methodology): “On the other hand, existing read placement methods based on phylogeny-aware alignment (Berger et al., 2011) handle the query sequences separately and delete sites inferred as insertions, limiting their use to phylogenetic placement only.”
Interactive Tree Of Life (iTOL) v4: recent updates and new developments (2019, background): “Phylogenetic placements files created by EPA (11) and pplacer (12) are also supported.”
A microbial clock provides an accurate estimate of the postmortem interval in a mouse model system (2013, methodology): “A phylogenetic tree was constructed for subsequent diversity analyses by placing representative sequences into a tree of the Silva 108 eukaryotic representative set using the maximum likelihood EPA algorithm within RAxML (Berger et al., 2011).”
Metabarcoding From Microbes to Mammals: Comprehensive Bioassessment on a Global Scale (2020, methodology): “…traditionally been inaccurate (Koski and Golding, 2001), so better methods [e.g., Bayesian classifiers: (Porter and Hajibabaei, 2018a)] need to be developed that can assign some level of identification to unknowns when an exact match in the reference database is not available (Berger et al., 2011).”
Interactive Tree Of Life (iTOL) v5: an online tool for phylogenetic tree display and annotation (2021, background): “Phylogenetic placement files created by EPA (11) and pplacer (12), as well as QIIME 2 trees and annotation files (13), are also supported.”
RAxML version 8: a tool for phylogenetic analysis and post-analysis of large phylogenies (2014, methodology): “Apart from that, RAxML also implements parsimony and maximum likelihood flavors of the Evolutionary Placement Algorithm (EPA (Berger et al., 2011)) that places short reads into a given reference phylogeny obtained from full-length sequences to determine the evolutionary origin of the reads.”
Phylogenetic Placement of Exact Amplicon Sequences Improves Associations with Clinical Information (2018, methodology): “Although sequence fragment insertion methods such as EPA (7) and pplacer (8) exist, these methods have not been tested with sOTUs from high-throughput amplicon studies using insertion against a broad reference phylogeny.”
Nursing biocrusts: isolation, cultivation, and fitness test of indigenous cyanobacteria (2019, methodology): “Query cyanobacterial sequences were aligned to the reference alignment with PaPaRa (Berger & Stamatakis 2011), placed into the reference tree using the RaxML8 Evolutionary Placement Algorithm (Berger et al. 2011), and visualized on the iTOL 3 server (Letunic & Bork 2016).”
A tale of worldwide success: Behind the scenes of Carex (Cyperaceae) biogeography and diversification (2019, methodology): “…of all excluded sequences — those present in the complete multiple tips matrix, but not in the multiple tips nrDNA ‐ complete matrix — was obtained building a “ query tree ” based on the reference tree, by using the evolutionary placement algorithm (Berger et al., 2011), as implemented in RAxML.”
Freshwater biomonitoring in the Information Age (2017, methodology): “fragments and degraded DNA), reads can be inserted in the reference phylogeny using a posteriori replacement algorithms (Matsen et al. 2010; Berger et al. 2011).”
EPA-ng: Massively Parallel Evolutionary Placement of Genetic Sequences (2018, background): “The result of a QS placement is a set of placement branches on the RT, each with an associated likelihood weight ratio (LWR) (Berger et al. 2011).”