STELLAR: fast and exact local alignments
Related Experiment Video
Updated: May 26, 2026

Highly Multiplexed, Super-resolution Imaging of T Cells Using madSTORM
Published on: June 24, 2017
Birte Kehr1, David Weese, Knut Reinert
1Department of Computer Science, Free University Berlin, Takustr. 9, 14195 Berlin, Germany. birte.kehr@fu-berlin.de
Background:
Large-scale comparison of genomic sequences requires reliable tools for the search of local alignments. Practical local aligners are in general fast, but heuristic, and hence sometimes miss significant matches.
Results:
We present here the local pairwise aligner STELLAR that has full sensitivity for ε-alignments, i.e. guarantees to report all local alignments of a given minimal length and maximal error rate. The aligner is composed of two steps, filtering and verification. We apply the SWIFT algorithm for lossless filtering, and have developed a new verification strategy that we prove to be exact. Our results on simulated and real genomic data confirm and quantify the conjecture that heuristic tools like BLAST or BLAT miss a large percentage of significant local alignments.
Conclusions:
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. Binaries are freely available for Linux, Windows, and Mac OS X at http://www.seqan.de/projects/stellar. The source code is freely distributed with the SeqAn C++ library version 1.3 and later at http://www.seqan.de.
Related Concept Videos
Reduced Mass Coordinates: Isolated Two-body Problem
Distribution of Molecular Speeds
Improving Translational Accuracy
Improving Translational Accuracy
Gene Evolution - Fast or Slow?
In contrast, regions which code...
Gene Evolution - Fast or Slow?
In contrast, regions which code...

