DREAM-Stellar

Abstract

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.

Links

Please Cite

  • Evelin Aasna, Simon G Gottlieb, Marcel Ehrhardt, Knut Reinert, “Dream-stellar: parallel and space efficient exact local alignment”, 2026-02-18.
    cite this publication 
    @article{fu_mi_publications3311,
 abstract = {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. This new version of Stellar is up to 900 times faster on 32
  parallel threads than its single-threaded 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},
 author = {Evelin Aasna and Simon G Gottlieb and Marcel Ehrhardt and Knut Reinert},
 journal = {BMC Bioinformatics},
 month = {February},
 publisher = {Springer Nature},
 title = {Dream-stellar: parallel and space efficient exact local alignment},
 url = {http://publications.imp.fu-berlin.de/3311/},
 year = {2026}
}

Contact

For questions, comments, or suggestions please contact:

Evelin Aasna