Linear-time protein 3-D structure searching with insertions and deletions.

Area of Science:

• Structural Biology
• Computational Biology
• Bioinformatics

Background:

• Biomolecular 3D structure similarity is defined by root mean square deviation (RMSD) below a threshold.
• Databases of 3D structures are crucial for post-genomic structural biology research.
• Efficiently searching these databases for similar structures is an ongoing challenge.

Purpose of the Study:

• To determine the computational complexity of finding similar substructures in 3D structure databases, considering insertions and deletions (indels).
• To develop an efficient algorithm for this search problem in 3D when the number of indels is bounded.

Main Methods:

• Proved the NP-hard nature of the substructure similarity search problem in unbounded dimensions.
• Developed a novel algorithm to improve average-case time complexity for 3D structure searches with a bounded number of indels.
• Analyzed the algorithm's performance against existing methods.

Main Results:

• The problem of finding similar 3D biomolecular substructures with indels is NP-hard in unbounded dimensions.
• The proposed algorithm achieves an average-case time complexity of O(N) for a query against a database of size N, significantly outperforming the previous O(Nm(k+1)) complexity.
• This improvement is achieved when the number of indels (k) is bounded by a constant.

Conclusions:

• Despite the NP-hard nature of the problem in general, efficient solutions exist for practical scenarios.
• The developed algorithm provides a practical and efficient method for searching 3D biomolecular structure databases with indels when the indel count is limited.
• This advancement facilitates faster and more effective structural biology research.