DREAM-Stellar: parallel and space efficient exact local alignment

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Searching large genomic datasets for local alignments presents significant computational challenges.
• Repetitive sequences in genomic data increase runtime costs and complicate homology searches.
• Effective filters are crucial for reducing search space without missing significant matches.

Purpose of the Study:

• To introduce DREAM-Stellar, an updated, parallelized version of the Stellar local aligner.
• To develop a sensitive and specific filter for practical homology searches in genomic data.
• To compare DREAM-Stellar's performance against existing local alignment tools.

Main Methods:

• DREAM-Stellar employs a four-step process: query/reference preprocessing, data structure building for query distribution, parallel computation, and result combination.
• Utilizes the IBF data structure and a novel prefilter for efficient local alignment query distribution.
• Performance evaluated on simulated and real genomic data against five other local aligners.

Main Results:

• DREAM-Stellar demonstrates significant speed improvements, up to 900x faster than its predecessor on 32 threads.
• It can identify all pairwise genome alignments within minutes, comparable in runtime to tools like BLAST.
• Heuristic tools like BLAST may miss significant local alignments or be overwhelmed by less significant matches.

Conclusions:

• DREAM-Stellar is a practical and fast tool for identifying local alignments in very long genomic sequences.
• It is suitable for homology searches under the edit distance model.
• The software is freely available for Linux and Mac OS X.