Phylogenetic placement of short reads without sequence alignment

Abstract

Phylogenetic placement is the task of placing a query sequence of unknown taxonomic origin into a given phylogenetic tree of a set of reference sequences. Several approaches to phylogenetic placement have been proposed in recent years. The most accurate of them need a multiple alignment of the reference sequences as input. Most of them also need alignments of the query sequences to the multiple alignment of the reference sequences. A major field of application of phylogenetic placement is taxonomic read assignment in metagenomics. Herein, we propose App-SpaM, an efficient alignment-free algorithm for phylogenetic placement of short sequencing reads on a tree of a set of reference genomes. App-SpaM is based on the Filtered Spaced Word Matches approach that we previously developed. Unlike other methods, our approach neither requires a multiple alignment of the reference genomes, nor alignments of the queries to the reference sequences. Moreover, App-SpaM works not only on assembled reference genomes, but can also take reference taxa as input for which only unassembled read sequences are available. The quality of the results achieved with App-SpaM is comparable to the best available approaches to phylogenetic placement. However, since App-SpaM is not based on sequence alignment, it is between one and two orders of magnitude faster than those existing methods.