Repository: Freie Universität Berlin, Math Department

STELLAR: fast and exact local alignments

Kehr, B. and Weese, D. and Reinert, K. (2011) STELLAR: fast and exact local alignments. BMC Bioinformatics, 12 (S9). S15. ISSN 1471-2105

Full text not available from this repository.

Official URL:


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 The source code is freely distributed with the SeqAn C++ library version 1.3 and later at

Item Type:Article
Subjects:Biological Sciences > Genetics
Mathematical and Computer Sciences > Computer Science
Divisions:Department of Mathematics and Computer Science > Institute of Computer Science > Algorithmic Bioinformatics Group
ID Code:1092
Deposited By: AG Alg BioInf
Deposited On:08 Oct 2011 13:20
Last Modified:08 Oct 2011 13:20

Repository Staff Only: item control page