Related Experiment Video
Updated: May 15, 2026
16:41
A Protocol for Computer-Based Protein Structure and Function Prediction
Published on: November 3, 2011
The difficulty of protein structure alignment under the RMSD.
1Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong. shuaicli@cityu.edu.hk.
Algorithms for Molecular Biology : AMB
|January 5, 2013
Summary
The largest common point set (LCP) problem in protein structure alignment is complex due to unspecified point distances and input precision. Removing these factors makes LCP as hard as minimizing RMSD (MAD), solvable in polynomial time.
Area of Science:
- Computational Biology
- Structural Bioinformatics
- Algorithm Analysis
Background:
- Protein structure alignment commonly uses the largest common point set (LCP) problem, based on Root Mean Square Deviation (RMSD).
- The LCP problem seeks maximum-length common subsequences between two protein structures, represented as 3D Cαatom coordinates.
- The computational difficulty of the LCP problem is not fully understood, hindering protein structure prediction and comparison.
Purpose of the Study:
- To investigate the underlying reasons for the computational difficulty of the LCP problem.
- To introduce and analyze a variant problem, Minimum Aligned Distance (MAD), for comparative analysis.
Main Methods:
- Defined the Minimum Aligned Distance (MAD) problem, where subsequence length is fixed and RMSD is minimized.
- Analyzed the complexity of both LCP and MAD problems by establishing their reducibility to each other.
- Introduced constraints: a limit on distances between consecutive points and integral coordinate values.
Main Results:
- Demonstrated that the difficulty of LCP and MAD does not stem solely from combinatorial search or structural superposition.
- Showed that LCP and MAD are equally difficult (reducible to each other) under the introduced constraints.
- Proved that both problems can be solved exactly in polynomial time with these constraints, though complexity remains high.
Conclusions:
- Identified two key factors contributing to LCP's complexity: lack of distance limits between points and arbitrary input precision.
- Concluded that these practical concerns are minimal for protein structure alignment.
- Established that with practical constraints, LCP becomes as computationally hard as MAD and solvable in polynomial time.
Related Concept Videos
01:24Protein Organization
Proteins are polymers of amino acid residues. They are versatile and responsible for different cellular functions, including DNA replication, molecular transport, catalysis, and structural support. Proteins have a hierarchical structure comprising at least three levels of organization: primary, secondary, and tertiary structure. Some large proteins have a quaternary structure where individual protein subunits are linked together.
The primary structure of a protein is its amino acid sequence.
The primary structure of a protein is its amino acid sequence.
01:29Protein Folding Quality Check in the RER
ER is the primary site for the maturation and folding of soluble and transmembrane secretory proteins. The calnexin cycle is a specific chaperone system that folds and assesses the confirmation of N-glycosylated proteins before they can exit the ER lumen. The primary players of this quality check pipeline are the lectins, ER-resident chaperones, and a glucosyl transferase enzyme. In case the calnexin system in the lumen fails to salvage a misfolded protein, it is transported to the cytoplasm...