YAKUSA

YAKUSA identifies the longest common substructures (Structural High-Scoring Pairs, SHSPs) between a query protein structure and entries in structural databases by representing protein backbone internal coordinates (alpha angles) as sequences of symbols for pattern matching.

Key Features:

• Backbone representation: Protein structures are encoded using protein backbone internal coordinates, specifically alpha angles, represented as sequences of symbols for pattern matching.
• SHSP identification: Detects longest common substructures termed Structural High-Scoring Pairs (SHSPs) between query and database structures.
• Deterministic finite automaton (DFA): Constructs a DFA that encapsulates all query patterns that are identical or similar to patterns in the database.
• Pattern search: Searches the DFA-defined patterns across every structure in the database.
• Substructure extension: Extends identified patterns into longer matching substructures (SHSPs).
• Compatibility selection: Selects compatible SHSPs for each query–database structure pair to ensure relevance.
• Ranking scores: Ranks structure pairs using three scores: SHSP similarity, probabilities associated with structural fragments, and spatial compatibility.
• Probability model: Estimates structural fragment probabilities using a mixture transition distribution model as an approximation to a high-order Markov chain.
• Sensitivity and selectivity: Achieves sensitivity and selectivity comparable to other leading structural comparison programs.
• Performance: Performs rapid database scans (approximately 40 seconds for a typical scan on a standard desktop personal computer).

Scientific Applications:

• Structural database scanning: Identification of conserved or similar substructures across protein structure databases.
• Comparative structural analysis: Comparative detection and ranking of structural similarities between query proteins and database entries.
• Structural bioinformatics research: Exploration of protein structure relationships and structural fragment probability analysis.

Methodology:

Constructs a deterministic finite automaton (DFA) describing query patterns; searches these patterns across database structures; extends matches into SHSPs; selects compatible SHSPs per query–database pair; ranks pairs by SHSP similarity, fragment probabilities, and spatial compatibility; estimates fragment probabilities via a mixture transition distribution model approximating a high-order Markov chain.