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 Experiment Videos

Spatial codes and the hardness of string folding problems.

A Nayak1, A Sinclair, U Zwick

  • 1Computer Science Division, University of California at Berkeley, 94720, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|May 1, 1999
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

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

Sort by
Same author

Search for Light Pseudoscalar Bosons, Pair-Produced in Higgs Boson Decays in the Four-Electron Final State in Proton-Proton Collisions at sqrt[s]=13  TeV.

Physical review letters·2026
Same author

First Evidence for Mixing-Induced CP Violation in B_{s}^{0}→J/ψϕ(1020) Decays in pp Collisions at sqrt[s]=13  TeV.

Physical review letters·2026
Same author

Observation of Suppressed Charged-Particle Production in Ultrarelativistic Oxygen-Oxygen Collisions.

Physical review letters·2026
Same author

Measurement of D^{0} Meson Photoproduction in Ultraperipheral Heavy Ion Collisions.

Physical review letters·2026
Same author

Observation of tWZ Production at the CMS Experiment.

Physical review letters·2026
Same author

First Exclusive Reconstruction of the B^{*+}, B^{*0}, and B_{s}^{*0} Mesons and Precise Measurement of Their Masses.

Physical review letters·2026
Same journal

GMSA: A Graph Matching and Point Cloud Registration-Based Method for Spatial Transcriptomics Data Alignment.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Investigations on Multiple Protein Scaffold Filling.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Cell Type Prediction for Single-Cell RNA Sequencing Utilizing Unsupervised Domain Adaptation and Semi-Supervised Learning.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

PPIGAN: Prediction of Protein-Protein Interactions Using Generative Adversarial Networks.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Deep Structure-Enhanced Cell Clustering Model for Single-Cell RNA Sequencing Data.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Asymmetric Drug-Drug Interaction Prediction Based on Generative Adversarial Networks and Knowledge Graph.

Journal of computational biology : a journal of computational molecular cell biology·2026
See all related articles

We developed a new method to prove NP-hardness for string folding problems, crucial for understanding protein folding complexity. This technique shows approximate protein folding solutions are also NP-hard, even with limited monomer types.

Area of Science:

  • Computational Biology
  • Theoretical Computer Science
  • Bioinformatics

Background:

  • Protein folding is a fundamental problem in biology.
  • Computational models like the Hydrophobic-Hydrophilic (HP) model simplify protein folding.
  • Previous studies on protein folding complexity often required unbounded alphabet sizes.

Purpose of the Study:

  • To present a general technique for proving NP-hardness of string folding problems over a finite alphabet.
  • To establish MAX SNP-hardness for these problems using randomized polynomial time reductions.
  • To address the intractability of protein folding variants with a fixed number of monomer types.

Main Methods:

  • Developed a novel reduction technique from existing NP-hard problems.
  • Replaced symbols from an unbounded alphabet with code-words over a fixed alphabet.

Related Experiment Videos

  • Introduced and utilized the concept of spatial codes, a variant of error-correcting codes for 3D spatial arrangements.

    • Main Results:

    • Established NP-hardness for string folding problems with finite alphabets under randomized polynomial time reductions.
    • Proved MAX SNP-hardness for these problems, implying approximation is also NP-hard.
    • Demonstrated the applicability of the technique to protein folding problems in HP models with fixed monomer types.

    Conclusions:

    • The new technique provides a general method for proving hardness of string folding problems.
    • Obtaining even approximate solutions for protein folding remains computationally challenging.
    • The use of spatial codes offers a novel approach for encoding information in 3D space for computational problems.