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

Area of Science:

• Bioinformatics
• Computational Biology
• Phylogenetics

Background:

• Accurate placement of short DNA sequences (reads) onto phylogenetic trees is crucial for understanding evolutionary relationships.
• Existing methods like BLAST can be slow and less accurate, particularly with limited reference data.

Purpose of the Study:

• To introduce a novel evolutionary placement algorithm (EPA) for rapid and accurate assignment of sequence fragments to phylogenetic trees.
• To compare the EPA's performance against established methods such as BLAST and pairwise sequence comparison.

Main Methods:

• Development of a maximum-likelihood-based evolutionary placement algorithm (EPA).
• Implementation of both slow/accurate and fast/less accurate versions, with heuristic optimizations for the slow version.
• Evaluation using real-world datasets and comparison with edit distances and BLAST.

Main Results:

• The EPA achieves significantly higher accuracy than BLAST, especially when reference phylogenetic trees have sparse or inadequate taxon sampling.
• Optimized EPA versions demonstrate run times comparable to BLAST for large numbers of short sequences.
• The algorithm, integrated into RAxML, offers a faster and more accurate alternative for tree-based inference of sequence origins.

Conclusions:

• The EPA provides a robust and efficient solution for placing short sequence reads onto phylogenetic trees.
• It represents a significant advancement over BLAST for evolutionary inference, offering improved accuracy and speed.
• A freely available web server is under development to provide EPA services to the research community.