DREAM-Stellar: Parallel and space efficient exact local alignment

Background: Searching large genomic data sets for local alignments poses a computational challenge. A particular obstacle is the handling of repetitive sequences that appear in various contexts and incur a high runtime cost. For practical homology search, it is important to develop a specific but sensitive filter. Good filters reduce the search space before alignment without missing significant matches. Results: We introduce DREAM-Stellar, a parallelized, updated version of the pairwise local aligner Stellar. The new aligner, DREAM-Stellar, is composed of four steps: preprocessing the queries and references, building a data structure for distributing the queries, computing in parallel the results and finally combining them. For distributing the queries we use the IBF data structure and a new prefilter for local alignments. We present our comparison of five local aligners on simulated and real genomic data and conclude that heuristic tools like BLAST miss a large percentage of significant local alignments or "drown" them in millions of less significant matches. The new version of Stellar is up to $900$ times faster than its predecessor and can find all alignments between a pair of genomes in minutes. With that, the runtime of DREAM-Stellar is on par with tools like BLAST etc. Conclusions: DREAM-Stellar is very practical and fast on very long sequences which makes it a suitable new tool for finding local alignments between genomic sequences under the edit distance model. The software is freely available for Linux and Mac OS X at https://github.com/seqan/dream-stellar