Stellar

Abstract

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 often miss significant matches. We provide here the local pairwise aligner STELLAR that has full sensitivity, i.e. guarantees to report all matches of a given minimal length and maximal error rate. The aligner is composed of two steps, filtering and verification. For filtering it applies the SWIFT algorithm, for which we have developed a new, exact verification strategy. STELLAR is very practical and fast on very long sequences which makes it a suitable new tool for finding local alignments in the edit or hamming distance model.

Links

• Download binaries
• View the source code and README on GitHub

Please Cite

• B. Kehr, D. Weese, K. Reinert, “STELLAR: fast and exact local alignments”, vol. 12, iss. S9, 2011-10-03.
  cite this publication

  @article{fu_mi_publications1092,
   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 {\ensuremath{\epsilon}}-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.},
   author = {B. Kehr and D. Weese and K. Reinert},
   journal = {BMC Bioinformatics},
   month = {October},
   number = {S9},
   pages = {S15},
   publisher = {BioMed Central},
   title = {STELLAR: fast and exact local alignments},
   url = {http://publications.imp.fu-berlin.de/1092/},
   volume = {12},
   year = {2011}
  }

Contact

For questions, comments, or suggestions please contact:

Birte Kehr birte.kehr@ukr.de