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

Stability of structures01:14

Stability of structures

278
In mechanical engineering, the stability of systems under various forces is critical for designing durable and efficient structures. One fundamental way to explore these concepts is by analyzing systems like two rods connected at a pivot point, O, with a torsional spring of spring constant k at the pivot point. This system is similar in appearance to a scissor jack used to change tires on a car. In this case, the arms of the linkage (equivalent to the rods in this system) are entirely vertical,...
278
Woodward–Hoffmann Selection Rules and Microscopic Reversibility01:34

Woodward–Hoffmann Selection Rules and Microscopic Reversibility

3.4K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.4K
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving01:29

Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving

126
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
126
Protein-protein Interfaces02:04

Protein-protein Interfaces

14.0K
Many proteins form complexes to carry out their functions, making protein-protein interactions (PPIs) essential for an organism's survival. Most PPIs are stabilized by numerous weak noncovalent chemical forces. The physical shape of the interfaces determines the way two proteins interact. Many globular proteins have closely-matching shapes on their surfaces, which form a large number of weak bonds. Additionally, many PPIs occur between two helices or between a surface cleft and a...
14.0K
Conserved Binding Sites01:49

Conserved Binding Sites

4.7K
Many proteins’ biological role depends on their interactions with their ligands, small molecules that bind to specific locations on the protein known as ligand-binding sites. Ligand-binding sites are often conserved among homologous proteins as these sites are critical for protein function.
Binding sites are often located in large pockets, and if their location on a protein’s surface is unknown, it can be predicted using various approaches. The energetic method computationally...
4.7K
Conservation of Protein Domains Over Different Proteins02:26

Conservation of Protein Domains Over Different Proteins

13.3K
Protein domains are small structurally independent units that are part of a single amino acid chain.  Although these domains are often structurally independent, they may rely on synergistic effects to perform their functions as part of a larger protein. Protein domains may be conserved within the same organism, as well as across different organisms.
A limited set of protein domains often duplicate and recombine during evolution. These domains can be organized in different combinations to...
13.3K

You might also read

Related Articles

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

Sort by
Same author

Barriers for the performance of graph neural networks (GNN) in discrete random structures.

Proceedings of the National Academy of Sciences of the United States of America·2023
See all related articles

Related Experiment Video

Updated: Oct 18, 2025

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

7.4K

The overlap gap property: A topological barrier to optimizing over random structures.

David Gamarnik1,2

  • 1Operations Research Center, Massachusetts Institute of Technology, Cambridge, MA 02140; Gamarnik@mit.edu.

Proceedings of the National Academy of Sciences of the United States of America
|October 2, 2021
PubMed
Summary

This study introduces the Overlap Gap Property to explain algorithmic hardness in random structures. This property rigorously rules out certain algorithms, offering new insights into computational complexity.

Keywords:
algorithms and computationphase transitionrandom structuresspin glasses

More Related Videos

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules
10:58

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules

Published on: July 25, 2013

17.2K
High-throughput Identification of Synergistic Drug Combinations by the Overlap2 Method
07:51

High-throughput Identification of Synergistic Drug Combinations by the Overlap2 Method

Published on: May 21, 2018

12.1K

Related Experiment Videos

Last Updated: Oct 18, 2025

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

7.4K
Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules
10:58

Protein WISDOM: A Workbench for In silico De novo Design of BioMolecules

Published on: July 25, 2013

17.2K
High-throughput Identification of Synergistic Drug Combinations by the Overlap2 Method
07:51

High-throughput Identification of Synergistic Drug Combinations by the Overlap2 Method

Published on: May 21, 2018

12.1K

Area of Science:

  • Computational complexity
  • Statistical physics
  • Machine learning
  • Artificial intelligence

Background:

  • Optimizing over random structures is a prevalent challenge in science and engineering.
  • Formal NP-hardness proofs are often missing for these problems, despite apparent algorithmic difficulty.

Purpose of the Study:

  • To introduce a novel approach for understanding algorithmic intractability in random structures.
  • To rigorously analyze the hardness of optimization problems in random settings.

Main Methods:

  • The study focuses on the Overlap Gap Property, a topological characteristic of near-optimal solution distances.
  • This property is analyzed across various models exhibiting apparent algorithmic hardness.

Main Results:

  • The Overlap Gap Property is demonstrated to emerge in most models with apparent algorithmic hardness.
  • The property aligns with observed hardness/tractability phase transitions in analyzed models.
  • It mathematically excludes algorithms exhibiting input stability from solving these problems.

Conclusions:

  • The Overlap Gap Property provides a rigorous framework for assessing algorithmic intractability in random structures.
  • This approach offers a new perspective on the theoretical limits of algorithms in fields like AI and machine learning.