@article{Beckstette:Homann:Giegerich:Fast_index_based:2006,
author = {Beckstette, Michael and Homann, Robert and Giegerich, 
          Robert and Kurtz, Stefan},
title = {Fast index based algorithms and software for matching 
         position specific scoring matrices},
journal = {BMC Bioinformatics},
year = {2006},
doi = {10.1186/1471-2105-7-389},
volume = {7},
user = {mbeckste},
pmid = {16930469},
pages = {389},
number = {},
abstract = {BACKGROUND: In biological sequence analysis, position 
            specific scoring matrices (PSSMs) are widely used to 
            represent sequence motifs in nucleotide as well as amino 
            acid sequences. Searching with PSSMs in complete genomes or 
            large sequence databases is a common, but computationally 
            expensive task. RESULTS: We present a new non-heuristic 
            algorithm, called ESAsearch, to efficiently find matches of 
            PSSMs in large databases. Our approach preprocesses the 
            search space, e.g., a complete genome or a set of protein 
            sequences, and builds an enhanced suffix array that is 
            stored on file. This allows the searching of a database with 
            a PSSM in sublinear expected time. Since ESAsearch benefits 
            from small alphabets, we present a variant operating on 
            sequences recoded according to a reduced alphabet. We also 
            address the problem of non-comparable PSSM-scores by 
            developing a method which allows the efficient computation 
            of a matrix similarity threshold for a PSSM, given an 
            E-value or a p-value. Our method is based on dynamic 
            programming and, in contrast to other methods, it employs 
            lazy evaluation of the dynamic programming matrix. We 
            evaluated algorithm ESAsearch with nucleotide PSSMs and with 
            amino acid PSSMs. Compared to the best previous methods, 
            ESAsearch shows speedups of a factor between 17 and 275 for 
            nucleotide PSSMs, and speedups up to factor 1.8 for amino 
            acid PSSMs. Comparisons with the most widely used programs 
            even show speedups by a factor of at least 3.8. Alphabet 
            reduction yields an additional speedup factor of 2 on amino 
            acid sequences compared to results achieved with the 20 
            symbol standard alphabet. The lazy evaluation method is also 
            much faster than previous methods, with speedups of a factor 
            between 3 and 330. CONCLUSION: Our analysis of ESAsearch 
            reveals sublinear runtime in the expected case, and linear 
            runtime in the worst case for sequences not shorter than the 
            absolute value of A(m) + m - 1, where m is the length of the 
            PSSM and A a finite alphabet. In practice, ESAsearch shows 
            superior performance over the most widely used programs, 
            especially for DNA sequences. The new algorithm for accurate 
            on-the-fly calculations of thresholds has the potential to 
            replace formerly used approximation approaches. Beyond the 
            algorithmic contributions, we provide a robust, well 
            documented, and easy to use software package, implementing 
            the ideas and algorithms presented in this manuscript.}
}