Related Experiment Video
Updated: Aug 13, 2026
16:41
A Protocol for Computer-Based Protein Structure and Function Prediction
Published on: November 3, 2011
Fast and simple character classes and bounded gaps pattern matching, with applications to protein searching
Gonzalo Navarro1, Mathieu Raffinot
1Department of Computer Science, University of Chile, Blanco Encalada 2120, Santiago, Chile. gnavarro@dcc.uchile.cl
Summary
This study introduces two novel algorithms for efficiently searching patterns with character classes and bounded gaps (CBG) in biological sequences. These methods significantly outperform traditional regular expression searches for protein pattern matching.
Area of Science:
- Bioinformatics
- Computational Biology
- Pattern Recognition
Background:
- Protein pattern matching often involves complex patterns with character classes and bounded gaps (CBG).
- Current methods rely on converting CBGs to regular expressions (REs), which are computationally intensive and slow for pattern matching.
- Existing RE search algorithms are not optimized for the specific structure of CBGs, leading to inefficiencies.
Purpose of the Study:
- To develop novel, efficient algorithms for exact and approximate searching of CBG patterns.
- To provide a simpler and faster alternative to current RE-based pattern matching techniques.
- To enable faster and more accurate protein pattern identification.
Main Methods:
- Designed two new practical algorithms for CBG pattern matching.
- Algorithm 1: Scans each text character exactly once.
- Algorithm 2: Optimizes by potentially skipping text characters, offering speed advantages but with occasional re-scans.
- Developed a criterion to select the optimal algorithm based on CBG structure.
- Incorporated methods for approximate matching with a tolerance for errors.
Main Results:
- Both new algorithms demonstrate significantly faster performance compared to RE search techniques.
- Algorithm 2 is generally faster than Algorithm 1, especially for certain CBG structures.
- Experimental results using the PROSITE database confirm the superior speed of the proposed algorithms in most cases.
- The criterion for algorithm selection effectively identifies the most efficient method a priori.
Conclusions:
- The developed CBG matching algorithms offer a substantial improvement in speed and simplicity over existing RE-based methods.
- These algorithms are highly effective for protein pattern matching and other applications involving CBG patterns.
- The ability to perform approximate matching further enhances the utility of these algorithms in biological sequence analysis.
More Related Videos
07:49Creating and Applying a Reference to Facilitate the Discussion and Classification of Proteins in a Diverse Group
Published on: August 16, 2017
05:08Application of I TASSER, trRosetta, UCSF Chimera, HADDOCK server, and HEX loria for De Novo and In Silico Design of Proteins
Published on: July 8, 2025
Related Concept Videos
02:47Protein Families
Protein families are groups of homologous proteins; that is, they have similarities in amino acid sequences and three-dimensional structures. Protein families usually occur because of gene duplication, where an additional copy of a gene is inserted into the genome of an organism. Mutations that change the amino acids but still allow the protein to be properly synthesized, will lead to new protein family members. If these new proteins contain similar amino acids in key locations, protein...
02:26Conservation of Protein Domains Over Different Proteins
Protein domains are small structurally independent units that are part of a single amino acid chain. Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
02:04Protein-protein Interfaces
Many proteins form complexes to carry out their functions, making protein-protein interactions (PPIs) essential for an organism's survival. Most PPIs are stabilized by numerous weak noncovalent chemical forces. The physical shape of the interfaces determines the way two proteins interact. Many globular proteins have closely-matching shapes on their surfaces, which form a large number of weak bonds. Additionally, many PPIs occur between two helices or between a surface cleft and a polypeptide...
01:49Conserved Binding Sites
Many proteins’ biological role depends on their interactions with their ligands, small molecules that bind to specific locations on the protein known as ligand-binding sites. Ligand-binding sites are often conserved among homologous proteins as these sites are critical for protein function.
Binding sites are often located in large pockets, and if their location on a protein’s surface is unknown, it can be predicted using various approaches. The energetic method computationally analyses the...
Binding sites are often located in large pockets, and if their location on a protein’s surface is unknown, it can be predicted using various approaches. The energetic method computationally analyses the...
01:57Protein Complexes with Interchangeable Parts
Groups of proteins may form a complex where each protein in this complex has a different role in the overall execution of the complex’s function. Often some of the proteins in the complex can be replaced by a closely related variant to give a complex that contains many of the same components yet is functionally distinct.
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
02:26Conservation of Protein Domains
Protein domains are small structurally independent units that are part of a single amino acid chain. Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to form...