A basic analysis toolkit for biological sequences
Open Access
- 18 September 2007
- journal article
- Published by Springer Nature in Algorithms for Molecular Biology
- Vol. 2 (1) , 10
Abstract
This paper presents a software library, nicknamed BATS, for some basic sequence analysis tasks. Namely, local alignments, via approximate string matching, and global alignments, via longest common subsequence and alignments with affine and concave gap cost functions. Moreover, it also supports filtering operations to select strings from a set and establish their statistical significance, via z-score computation. None of the algorithms is new, but although they are generally regarded as fundamental for sequence analysis, they have not been implemented in a single and consistent software package, as we do here. Therefore, our main contribution is to fill this gap between algorithmic theory and practice by providing an extensible and easy to use software library that includes algorithms for the mentioned string matching and alignment problems. The library consists of C/C++ library functions as well as Perl library functions. It can be interfaced with Bioperl and can also be used as a stand-alone system with a GUI. The software is available at http://www.math.unipa.it/~raffaele/BATS/ under the GNU GPL.Keywords
This publication has 32 references indexed in Scilit:
- Faster algorithms for string matching with k mismatchesJournal of Algorithms, 2004
- Sparse Dynamic Programming for Longest Common Subsequence from FragmentsJournal of Algorithms, 2002
- On-line construction of suffix treesAlgorithmica, 1995
- Sparse dynamic programming IIJournal of the ACM, 1992
- Basic local alignment search toolJournal of Molecular Biology, 1990
- Speeding up dynamic programming with applications to molecular biologyTheoretical Computer Science, 1989
- AnO(ND) difference algorithm and its variationsAlgorithmica, 1986
- Efficient sequence alignment algorithmsJournal of Theoretical Biology, 1984
- An improved algorithm for matching biological sequencesJournal of Molecular Biology, 1982
- A fast algorithm for computing longest common subsequencesCommunications of the ACM, 1977