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

A reduction-based exact algorithm for the contact map overlap problem.

Wei Xie1, Nikolaos V Sahinidis

  • 1Department of Chemical and Biomolecular Engineering, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801, USA.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|August 9, 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

Algorithm-Guided Experimentation for Optimization of High-Performance Perovskite Solar Cells.

ACS energy letters·2025
Same author

Stochastic analysis and modeling of pharmaceutical screw feeder mass flow rates.

International journal of pharmaceutics·2022
Same author

ExtractionScore: A Quantitative Framework for Evaluating Synthetic Routes on Predicted Liquid-Liquid Extraction Performance.

Journal of chemical information and modeling·2021
Same author

The neuronal protein Neurexin directly interacts with the Scribble-Pix complex to stimulate F-actin assembly for synaptic vesicle clustering.

The Journal of biological chemistry·2017
Same author

3D Chromatin Structures of Mature Gametes and Structural Reprogramming during Mammalian Embryogenesis.

Cell·2017
Same author

Allelic reprogramming of 3D chromatin architecture during early mammalian development.

Nature·2017
Same journal

Mosquito Species and Gender Identification System Based on Artificial Intelligence and Image Processing Methods.

Journal of computational biology : a journal of computational molecular cell biology·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
See all related articles

This study introduces an efficient exact algorithm for protein structural alignment using contact map overlap (CMO) maximization. The new method significantly speeds up computation and solves previously intractable problems, aiding protein classification and function prediction.

Area of Science:

  • Molecular Biology
  • Bioinformatics
  • Computational Biology

Background:

  • Protein structural alignment is crucial for understanding protein function, classification, and evolution.
  • Contact Map Overlap (CMO) maximization is a key method for structural alignment, aiming to maximize common residue contacts.
  • Existing methods for CMO can be computationally intensive and may not solve all complex instances.

Purpose of the Study:

  • To develop a novel, exact algorithm for solving the Contact Map Overlap (CMO) problem.
  • To improve the efficiency and scalability of protein structural alignment algorithms.
  • To provide a robust tool for protein structure classification and function prediction.

Main Methods:

  • Developed a reduction-based exact algorithm that directly addresses the CMO problem.

Related Experiment Videos

  • Implemented efficient lower bounding, upper bounding, and reduction schemes tailored to the problem's mathematical structure.
  • Avoided transforming the CMO problem into other complex combinatorial optimization problems.

    • Main Results:

    • The new algorithm demonstrates significantly faster performance compared to existing exact algorithms.
    • Successfully solved challenging CMO instances that were previously unsolvable.
    • Generated protein clusters highly consistent with the SCOP (Structural Classification of Proteins) database classification.

    Conclusions:

    • The developed algorithm offers a substantial advancement in solving the protein structural alignment problem via CMO maximization.
    • The algorithm's efficiency and accuracy provide a valuable tool for molecular biology research, including protein structure analysis and database searching.
    • An accessible online server implementation is available for broader scientific use.