Performance, accuracy, and Web server for evolutionary placement of short sequence reads under maximum likelihood

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.

FIGURE 1

Local optimization of edge lengths for the insertion of a QS into the RT.

FIGURE 2

Evolutionary identification of three QSs (QS₀, QS₁, QS₂) using a 4-taxon RT.

FIGURE 3

Phylogenetic placement of three QSs (QS₀, QS₁, QS₂) onto a 4-taxon RT with insertion support score.

FIGURE 4

Illustration of the criterion for the QS selection and experimental setup. (a) Candidate QS belongs to subtree of size 2 that is connected to the tree by a well-supported edge. It has one other tip as direct neighbor. QS with this property will be referred to as outer QS. (b) Candidate QS is connected to the tree by two well-supported edges. QS with this property will be referred to as inner QS. (c) Experimental setting: reinsert shortened candidate QS in to pruned RT. We use three different ways of generating QS with desirable features: contiguous subsequences, paired-end reads, and random gaps.

FIGURE 5

Illustration of the tree-based distance measures. a) Example tree with two edges (original and insertion edge) highlighted. There are two nodes on the path, so the ND is 2. The edge distance corresponds to the length of the connecting path, where of the two end edges only half of the edge length is used. b) Tree diameter that is used to normalize the edge distance.

FIGURE 6

Placement accuracy for QS with artificially introduced random gaps. a) Average ND and b) NED (between insertion positions and real positions).

FIGURE 7

Histogram showing the placement accuracy, based on NDs, for the placement of 2 × 100 bp paired-end reads from D855, using outer a) and inner b) QS.

FIGURE 8

Average ND for different versions of the EPA (fast/slow insertions) algorithm and model types (GTR + Γ, GTR + CAT) on inner QS and outer QS from all data sets.

FIGURE 9

Accuracy of the EPA as a function of the number of edges considered for slow insertion after heuristic filtering.