Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Lattice Centering and Coordination Number02:33

Lattice Centering and Coordination Number

The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
Protein Complexes with Interchangeable Parts01:57

Protein Complexes with Interchangeable Parts

Groups of proteins may form a complex where each protein in this complex has a different role in the overall execution of the complex’s function. Often some of the proteins in the complex can be replaced by a closely related variant to give a complex that contains many of the same components yet is functionally distinct.
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
Protein Complexes with Interchangeable Parts01:57

Protein Complexes with Interchangeable Parts

Groups of proteins may form a complex where each protein in this complex has a different role in the overall execution of the complex’s function. Often some of the proteins in the complex can be replaced by a closely related variant to give a complex that contains many of the same components yet is functionally distinct.
The SCF ubiquitin ligase is a protein complex of five individual proteins. This complex attaches ubiquitin to other target proteins to mark them for degradation. In order to...
Metallic Solids02:37

Metallic Solids

Metallic solids such as crystals of copper, aluminum, and iron are formed by metal atoms. The structure of metallic crystals is often described as a uniform distribution of atomic nuclei within a “sea” of delocalized electrons. The atoms within such a metallic solid are held together by a unique force known as metallic bonding that gives rise to many useful and varied bulk properties.
All metallic solids exhibit high thermal and electrical conductivity, metallic luster, and malleability. Many...
Network Covalent Solids02:18

Network Covalent Solids

Network covalent solids contain a three-dimensional network of covalently bonded atoms as found in the crystal structures of nonmetals like diamond, graphite, silicon, and some covalent compounds, such as silicon dioxide (sand) and silicon carbide (carborundum, the abrasive on sandpaper). Many minerals have networks of covalent bonds.
To break or to melt a covalent network solid, covalent bonds must be broken. Because covalent bonds are relatively strong, covalent network solids are typically...
Protein Complex Assembly02:41

Protein Complex Assembly

Proteins can form homomeric complexes with another unit of the same protein or heteromeric complexes with different types.  Most protein complexes self-assemble spontaneously via ordered pathways, while some proteins need assembly factors that guide their proper assembly. Despite the crowded intracellular environment, proteins usually interact with their correct partners and form functional complexes.
Many viruses self-assemble into a fully functional unit using the infected host cell to...

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Design of nucleic acid strands with long low-barrier folding pathways.

Natural computing·2017
Same author

Algorithms and Complexity Results for Genome Mapping Problems.

IEEE/ACM transactions on computational biology and bioinformatics·2016
Same author

Reachability bounds for chemical reaction networks and strand displacement systems.

Natural computing·2014
Same author

Linearization of ancestral multichromosomal genomes.

BMC bioinformatics·2013
Same author

Less haste, less waste: on recycling and its limits in strand displacement systems.

Interface focus·2012
Same author

Algorithm for haplotype inference via galled-tree networks with simple galls.

Journal of computational biology : a journal of computational molecular cell biology·2012

Related Experiment Video

Updated: Jul 6, 2026

Stable DNA Motifs, 1D and 2D Nanostructures Constructed from Small Circular DNA Molecules
09:32

Stable DNA Motifs, 1D and 2D Nanostructures Constructed from Small Circular DNA Molecules

Published on: April 12, 2019

Fitting protein chains to cubic lattice is NP-complete.

Ján Manuch1, Daya Ram Gaur

  • 1School of Computing Science, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada. jmanuch@sfu.ca

Journal of Bioinformatics and Computational Biology
|March 8, 2008
PubMed
Summary

Finding the closest lattice approximation for a protein chain fold is NP-complete. This computational challenge impacts protein structure modeling and analysis, even for simplified cubic lattice representations.

More Related Videos

Modeling Ligands into Maps Derived from Electron Cryomicroscopy
09:30

Modeling Ligands into Maps Derived from Electron Cryomicroscopy

Published on: July 19, 2024

Production, Crystallization and Structure Determination of C. difficile PPEP-1 via Microseeding and Zinc-SAD
13:34

Production, Crystallization and Structure Determination of C. difficile PPEP-1 via Microseeding and Zinc-SAD

Published on: December 30, 2016

Related Experiment Videos

Last Updated: Jul 6, 2026

Stable DNA Motifs, 1D and 2D Nanostructures Constructed from Small Circular DNA Molecules
09:32

Stable DNA Motifs, 1D and 2D Nanostructures Constructed from Small Circular DNA Molecules

Published on: April 12, 2019

Modeling Ligands into Maps Derived from Electron Cryomicroscopy
09:30

Modeling Ligands into Maps Derived from Electron Cryomicroscopy

Published on: July 19, 2024

Production, Crystallization and Structure Determination of C. difficile PPEP-1 via Microseeding and Zinc-SAD
13:34

Production, Crystallization and Structure Determination of C. difficile PPEP-1 via Microseeding and Zinc-SAD

Published on: December 30, 2016

Area of Science:

  • Computational biology
  • Structural bioinformatics
  • Protein structure analysis

Background:

  • Protein folding into a cubic lattice is a known NP-complete problem.
  • Approximating a given 3D protein fold to a lattice is a related challenge.
  • Existing studies refer to this as protein chain fitting or lattice model building.

Purpose of the Study:

  • To determine the computational complexity of finding the closest lattice approximation of a given 3D protein fold.
  • To investigate this problem specifically for cubic lattices and coordinate root mean square deviation.

Main Methods:

  • The study analyzes the computational complexity of the protein chain fitting problem.
  • It focuses on approximating protein folds within a cubic lattice structure.
  • The analysis uses coordinate root mean square deviation as a metric.

Main Results:

  • The problem of finding the closest lattice approximation of a protein chain fold is proven to be NP-complete.
  • This NP-completeness holds for cubic lattices with a side length close to 3.8 Å.
  • Coordinate root mean square deviation is used as the measure for closeness.

Conclusions:

  • The protein chain fitting problem, even when given a 3D fold, is computationally complex (NP-complete).
  • This finding has implications for the efficiency of building protein lattice models.
  • Understanding the complexity aids in developing better algorithms for protein structure approximation.