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 parameterized algorithm for protein structure alignment.

Jinbo Xu1, Feng Jiao, Bonnie Berger

  • 1Toyota Technological Institute at Chicago, Chicago, Illinois 60637, USA. j3xu@tti-c.org

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

Promera: a unified model for biomolecular structure prediction, filtering, and design.

bioRxiv : the preprint server for biology·2026
Same author

Thousandfold Expansion Microscopy.

bioRxiv : the preprint server for biology·2026
Same author

SwitchCraft: A Programmatic Framework for Designing State-Switching Proteins.

ArXiv·2026
Same author

Multi-resolution modeling of a discrete stochastic process identifies causes of cancer.

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

AI-based methods for simulating, sampling, and predicting protein ensembles.

Current opinion in structural biology·2026
Same author

Constrained Diffusion as a Paradigm for Evolution.

bioRxiv : the preprint server for biology·2026
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 presents a parameterized polynomial time approximation scheme (PTAS) for protein structure alignment using contact maps. Computational hardness depends on parameters, not protein size, enabling efficient alignment.

Area of Science:

  • Computational Biology
  • Structural Bioinformatics
  • Algorithm Design

Background:

  • Protein structure alignment is crucial for understanding protein function and evolution.
  • Existing methods often struggle with computational complexity for large protein datasets.
  • Contact map representations offer a simplified yet informative view of protein structures.

Purpose of the Study:

  • To develop an efficient algorithm for aligning protein structures represented by contact maps.
  • To analyze the computational complexity of protein structure alignment based on contact maps.
  • To provide a parameterized polynomial time approximation scheme (PTAS) for this problem.

Main Methods:

  • Utilized tree decomposition to break down protein structures into smaller, manageable components.

Related Experiment Videos

  • Discretized the rigid-body transformation space to explore possible structural alignments.
  • Developed a parameterized polynomial time approximation scheme (PTAS) for alignment without sequential order constraints.

    • Main Results:

    • The proposed PTAS achieves a time complexity polynomial in protein size but exponential in specific parameters (D(u)/D(l), D(c)/D(l)).
    • Demonstrated that the computational hardness is primarily influenced by these modeling parameters, not solely protein size.
    • Preliminary experiments show alignment of ~100-residue proteins in 10 minutes to 1 hour on a standard PC.

    Conclusions:

    • The developed PTAS offers an efficient approach for protein structure alignment using contact maps.
    • The findings highlight the importance of specific distance parameters in determining the computational complexity.
    • This work provides a valuable tool for structural bioinformatics and computational biology research.