Jove
Visualize
Contact Us

Related Experiment Videos

Fast index based algorithms and software for matching position specific scoring matrices.

Michael Beckstette1, Robert Homann, Robert Giegerich

  • 1International NRW Graduate School in Bioinformatics and Genome Research, Center for Biotechnology (CeBITec), Bielefeld University, D-33594 Bielefeld, Germany. mbeckste@techfak.uni-bielefeld.de

BMC Bioinformatics
|August 26, 2006
PubMed
Summary

A new algorithm, ESAsearch, significantly speeds up the search for position-specific scoring matrices (PSSMs) in large biological databases. This method offers substantial performance improvements for nucleotide and amino acid sequences, making motif discovery more efficient.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

BiTUGA: scalable prevalence-based unitig association testing for binary traits.

G3 (Bethesda, Md.)·2026
Same author

The power and limits of predicting inter-protein exon-exon interactions using protein 3D structures.

Bioinformatics advances·2026
Same author

ActivityFinder: Toward the Fully Automatic Integration of Structural and Binding Affinity Data.

Journal of chemical information and modeling·2026
Same author

DNA methylation profiling of human CD4<sup>+</sup> T helper cells reveals the epigenetic control of SLAMF7 expression in IFN-γ producing cells.

Immunology and cell biology·2025
Same author

OmixLitMiner 2: Guided Literature Mining for Automated Categorization of Marker Candidates in Omics Studies.

Proteomics·2025
Same author

Transcription factor prediction using protein 3D secondary structures.

Bioinformatics (Oxford, England)·2025
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Sequence Analysis

Background:

  • Position-specific scoring matrices (PSSMs) are crucial for representing sequence motifs in biological data.
  • Searching large sequence databases with PSSMs is computationally intensive and time-consuming.

Purpose of the Study:

  • To develop a novel, non-heuristic algorithm for efficient PSSM searching in large biological databases.
  • To improve the speed and accuracy of motif discovery in nucleotide and amino acid sequences.

Main Methods:

  • Introduced ESAsearch, an algorithm utilizing an enhanced suffix array for preprocessing search spaces.
  • Implemented a variant for reduced alphabets to leverage benefits from smaller sequence alphabets.
  • Developed a dynamic programming method with lazy evaluation for efficient computation of PSSM similarity thresholds.

Related Experiment Videos

Main Results:

  • ESAsearch achieves sublinear expected runtime for PSSM searching, outperforming previous methods.
  • Demonstrated significant speedups: 17-275x for nucleotide PSSMs and up to 1.8x for amino acid PSSMs.
  • Alphabet reduction provided an additional 2x speedup for amino acid sequences; threshold calculation was 3-330x faster.

Conclusions:

  • ESAsearch offers superior performance, especially for DNA sequences, with sublinear expected and linear worst-case runtimes.
  • The novel threshold calculation method provides accurate, on-the-fly results, potentially replacing approximation techniques.
  • A robust, user-friendly software package implementing ESAsearch is provided for practical applications in biological sequence analysis.