Finding All Longest Common Segments in Protein Structures Efficiently.

Area of Science:

• Computational Biology
• Structural Bioinformatics
• Algorithm Analysis

Background:

• Protein structure comparison is vital for understanding function and evolution.
• The Local/Global Alignment (LGA) method relies on identifying common structural segments.
• Existing methods for finding these segments can be computationally intensive.

Purpose of the Study:

• To develop and analyze efficient algorithms for computing longest common contiguous segments between protein structures.
• To address two similarity criteria: root mean squared deviation (RMSD) and superposition-based distance thresholds.
• To provide optimized algorithms with improved time complexities for practical applications in structural bioinformatics.

Main Methods:

• Algorithm development for identifying longest common segments under RMSD and superposition criteria.
• Introduction of Fully Polynomial Time Approximation Schemes (FPTAS) for approximate solutions.
• Analysis of time complexity, including O(n log n + nl) and O(n log(2) n/ϵ(5)).
• Verification through C++ implementations.

Main Results:

• An O(n log n + nl) algorithm for the RMSD criterion.
• An FPTAS achieving RMSD within (1 + ϵ)t in O(n log n + n/ϵ) time.
• An FPTAS for the superposition criterion with complexity O(n log(2) n/ϵ(5)) for protein structures.
• Open-source C++ implementations are available.

Conclusions:

• The developed algorithms significantly enhance the efficiency of protein structure comparison.
• Approximation schemes offer practical solutions for large-scale structural analyses.
• The work provides valuable tools for the bioinformatics community.