Jove
Visualize
Contact Us

Related Experiment Videos

Clique-detection algorithms for matching three-dimensional molecular structures

E J Gardiner1, P J Artymiuk, P Willett

  • 1Krebs Institute for Biomolecular Research, University of Sheffield, UK.

Journal of Molecular Graphics & Modelling
|August 1, 1997
PubMed
Summary

A new study compares clique-detection algorithms for finding maximum common subgraphs (MCS) in molecules. The Carraghan and Pardalos algorithm is faster for identifying structural relationships, while Bron-Kerbosch finds all common substructures.

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

A Case of Iritis Serosa.

The Chicago medical journal and examiner·2023
Same author

Quarterly Report of Ophthalmological and Otological Literature.

The Chicago medical journal and examiner·2023
Same author

Quarterly Abstract of Ophthalmological and Otological Literature.

The Chicago medical journal and examiner·2023
Same author

A Case of Malarial Keratitis.

The Chicago medical journal and examiner·2023
Same author

Quickest Detection of COVID-19 Pandemic Onset.

IEEE signal processing letters·2021
Same author

A study on the use of Gumbel approximation with the Bernoulli spatial scan statistic.

Statistics in medicine·2013
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

Area of Science:

  • Computational chemistry
  • Graph theory
  • Bioinformatics

Background:

  • Molecular structures are represented as graphs for computational analysis.
  • Maximum Common Subgraph (MCS) isomorphism is crucial for identifying structural relationships between molecules.
  • Clique detection algorithms can efficiently implement MCS detection.

Purpose of the Study:

  • To compare the efficiency of different clique-detection algorithms for MCS detection in molecular graphs.
  • To identify the most suitable algorithm for applications involving low edge-density correspondence graphs.

Main Methods:

  • Comparison of various clique-detection algorithms, including Carraghan and Pardalos and Bron-Kerbosch.
  • Experimental evaluation using small molecules and protein structures.

Related Experiment Videos

  • Analysis of algorithm performance on correspondence graphs with varying edge densities.

    • Main Results:

    • The Carraghan and Pardalos algorithm is 2-3 times faster than the Bron-Kerbosch algorithm for MCS detection in typical molecular graph applications.
    • The Bron-Kerbosch algorithm identifies all common substructures, not just the largest ones.
    • The Carraghan and Pardalos algorithm is most efficient for correspondence graphs with low edge densities.

    Conclusions:

    • The Carraghan and Pardalos algorithm offers significant speed improvements for MCS detection in chemical and biological contexts.
    • Combining Carraghan-Pardalos and Bron-Kerbosch algorithms can enhance the efficiency of database searching systems that use MCS for structural similarity.
    • Algorithm choice depends on whether the largest common subgraph or all common substructures are required.