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

Approximate protein structural alignment in polynomial time.

Rachel Kolodny1, Nathan Linial

  • 1Departments of Computer Science and Structural Biology, Stanford University, Stanford, CA 94305, USA. trachel@cs.stanford.edu

Proceedings of the National Academy of Sciences of the United States of America
|August 12, 2004
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

Modeling the Language of Codons with Artificial Intelligence.

Annual review of biomedical data science·2026
Same author

Systematic structure-based analysis of RET variants in MEN2A and Hirschsprung's disease, and the paradoxical co-occurrence of both conditions.

Disease models & mechanisms·2026
Same author

Interpretable prediction of zinc ion location in proteins with ZincSight.

Protein science : a publication of the Protein Society·2025
Same author

From Binding to Catalysis: Emergence of a Rudimentary Enzyme Conferring Intrinsic Antibiotic Resistance.

Molecular biology and evolution·2025
Same author

Editorial overview: Sequences and topology (2025).

Current opinion in structural biology·2025
Same author

A building blocks perspective on protein emergence and evolution.

Current opinion in structural biology·2025
Same journal

Tau protein as a regulator of mitochondrial function and dynamics.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

A scalable, dividing cell model for the robust propagation and quantification of human sporadic Creutzfeldt-Jakob disease prions.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Epigenetic regulation of mesenchymal BMP signaling directs postnatal organ innervation.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Single-shot wide-field biochemical imaging at 1 kHz frame rate.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Morphogenesis and topological evolution of a frustrated nematic liquid crystal under confinement.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

B cell-intrinsic CXCR3 drives efficient generation of ectopic pulmonary germinal center responses to influenza A virus infection.

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

We developed an approximate algorithm for protein structural alignment, proving its computational feasibility. This method offers valuable insights into evolutionary relationships despite its current limitations for everyday use.

Area of Science:

  • Computational molecular biology
  • Bioinformatics
  • Structural biology

Background:

  • Protein structure alignment is crucial for identifying evolutionary relationships beyond sequence analysis.
  • Existing methods face challenges in accurately detecting distant evolutionary connections.
  • Computational feasibility of optimal structural alignment remains an open question.

Purpose of the Study:

  • To investigate protein structural alignment as a family of optimization problems.
  • To develop an approximate polynomial-time algorithm for solving these problems.
  • To analyze the computational complexity and practical implications of structural alignment algorithms.

Main Methods:

  • Formulated protein structural alignment as a set of optimization problems.

Related Experiment Videos

  • Developed an approximate polynomial-time algorithm using Euclidean distance for structural comparison.
  • Analyzed the algorithm's runtime complexity and approximation error (O(n^10)/ε^6).
  • Investigated alternative approaches using internal distance matrices.

    • Main Results:

    • Proved the computational feasibility of approximate protein structural alignment.
    • The algorithm achieves an additive error of ε from optimal alignments.
    • Demonstrated that approximate solutions are valuable due to noisy experimental data.
    • Provided insights into the computational complexity of various scoring functions.

    Conclusions:

    • Approximate algorithms offer a feasible approach to protein structural alignment.
    • Euclidean distance-based methods are effective for structural comparison.
    • Findings inform the design of efficient scoring functions and multiple alignment algorithms.