PoSSuMsearch

PoSSuMsearch identifies matches of Position Specific Scoring Matrices (PSSMs) within large biological sequence databases to detect sequence motifs in nucleotide and amino acid sequences.

Key Features:

• Enhanced Suffix Array Construction: Preprocesses the search space (e.g., complete genomes or extensive protein databases) to construct an enhanced suffix array (ESA) that enables sublinear expected-time searches.
• Alphabet Reduction Technique: Operates on sequences recoded to a reduced alphabet to accelerate searches, achieving an additional speedup factor of 2 in amino acid searches relative to the 20-symbol alphabet.
• Dynamic Programming with Lazy Evaluation: Uses dynamic programming with lazy evaluation to compute matrix similarity thresholds on the fly, yielding reported speedups between factors of 3 and 330.
• Performance and Efficiency: Reports speedups for nucleotide PSSMs between factors of 17 and 275, for amino acid PSSMs up to factor 1.8, and minimum improvements of 3.8× in comparisons with widely used programs.
• Runtime Analysis: Exhibits sublinear expected runtime and worst-case linear runtime for sequences not shorter than the absolute value of A(m) + m - 1, where m is the PSSM length and A denotes a finite alphabet.

Scientific Applications:

• Genomic Research: Facilitates rapid motif discovery within complete genomes to identify regulatory elements and conserved sequences.
• Protein Analysis: Enables efficient PSSM searches in large protein databases to support protein function and interaction studies.
• Comparative Genomics: Supports fast PSSM matching for comparative analyses across species or strains.

Methodology:

Built on a non-heuristic algorithm named ESAsearch that preprocesses the search space to build an enhanced suffix array stored on file and that employs alphabet reduction and dynamic programming with lazy evaluation.