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

Fast molecular shape matching using contact maps.

Pankaj K Agarwal1, Nabil H Mustafa, Yusu Wang

  • 1Dept. of Computer Science, Duke University, Durham, North Carolina, USA. pankaj@cs.duke.edu

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|April 26, 2007
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

Topology-Aware Segmentation Using Discrete Morse Theory.

... International Conference on Learning Representations·2026
Same author

Correction: Wang et al. Decellularized Antler Cancellous Bone Matrix Material Can Serve as Potential Bone Tissue Scaffold. <i>Biomolecules</i> 2024, <i>14</i>, 907.

Biomolecules·2026
Same author

A Nasal Taxifolin Hydrogel Targets the TLR4/NF-κB/HIF-1α Axis to Suppress Ferroptosis in Alzheimer's Disease.

Antioxidants (Basel, Switzerland)·2026
Same author

A Nose-to-Brain Delivery System for Taxifolin Ameliorates Alzheimer's Disease via Synergistic Attenuation of Oxidative Stress and Mitochondrial Dysfunction.

Antioxidants (Basel, Switzerland)·2026
Same author

Association Between Intraoperative Hyperlactatemia and Infection After Cardiac Surgery With Cardiopulmonary Bypass: A Multicenter Retrospective Study.

World journal of surgery·2026
Same author

Phylogenomic analysis of Cervidae provides insights into antler origin and evolution.

Zoological research·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

This study introduces a new polynomial time algorithm for comparing protein structures using contact-map overlap. The algorithm provides an approximation ratio for 3D structures and improves efficiency in 2D, advancing computational biology.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Structural Biology

Background:

  • Protein structure similarity is crucial for understanding function and evolution.
  • Contact-map overlap provides a graph-theoretic approach to structural comparison.
  • Existing algorithms for contact-map overlap have limitations in efficiency and approximation guarantees.

Purpose of the Study:

  • To develop an efficient algorithm for computing protein structure similarity via contact-map overlap.
  • To establish approximation guarantees for 3D protein structure comparison.
  • To improve the computational performance of 2D contact-map overlap algorithms.

Main Methods:

  • Developed a novel polynomial time algorithm for 3D contact-map overlap.
  • Analyzed the algorithm's approximation ratio based on a decomposition parameter sigma.

Related Experiment Videos

  • Optimized the running time for 2D contact-map overlap from O(n^6) to O(n^3 log n).

    • Main Results:

    • The first polynomial time algorithm with approximation guarantees for 3D contact-map overlap is presented.
    • Achieved an approximation ratio of sigma <= O(n^1/2) for 3D structures.
    • Significantly improved the running time for 2D comparisons while halving the approximation ratio.

    Conclusions:

    • The new algorithms advance the field of computational protein structure comparison.
    • The study provides theoretical hardness results for 3D contact-map overlap approximation.
    • This work offers more efficient and reliable tools for analyzing protein structural similarities.