title: STELLAR: fast and exact local alignments.
abstract: 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.
authors.affiliation: Department of Computer Science, Free University Berlin, Takustr. 9, 14195 Berlin, Germany. birte.kehr@fu-berlin.de
authors.forename: Birte
authors.initials: B
authors.lastname: Kehr
authors.forename: David
authors.initials: D
authors.lastname: Weese
authors.forename: Knut
authors.initials: K
authors.lastname: Reinert
mesh_terms: D000465:Algorithms; D000818:Animals; D004330:Drosophila / Q000235:genetics; D023281:Genomics / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D012984:Software