Related Experiment Videos
On the structural complexity of a protein.
1LAMIH-ROI, UMR CNRS 8530, Université de Valenciennes et du Hainaut-Cambrésis, Le Mont Houy, BP 311, 59304 Valenciennes Cédex, France. pierre-yves.calland@univ-valenciennes.fr
Protein Engineering
|April 5, 2003
Summary
Determining protein 3D structure is challenging. This study models protein threading as an NP-hard problem and proposes a new decomposition algorithm to evaluate 3D structure complexity efficiently.
Area of Science:
- Computational Biology
- Structural Bioinformatics
- Molecular Modeling
Background:
- Determining a protein's three-dimensional (3D) structure is a critical challenge in molecular biology.
- Current methods often involve selecting a protein structure from a database that minimizes an energy function.
Purpose of the Study:
- To evaluate the intrinsic complexity of protein 3D structures.
- To identify complex components within protein structures that can inform solution methods.
Main Methods:
- Modeling the protein threading problem using dynamic programming.
- Demonstrating that determining the optimal variable order for time complexity minimization is NP-hard.
- Proposing a novel decomposition algorithm for the threading problem based on graph connectivity.
Main Results:
- The study identifies two complexity indexes: time and space.
- Complex components within a protein's 3D structure are determined in polynomial time.
- The proposed decomposition algorithm offers a potential approach to solving the protein threading problem.
Conclusions:
- The intrinsic complexity of protein 3D structures can be quantified.
- Efficient algorithms can identify complex structural elements, aiding in protein structure determination.
- This research contributes to advancing computational methods in structural bioinformatics.