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

Maximum common subgraph: some upper bound and lower bound results.

Xiuzhen Huang1, Jing Lai, Steven F Jennings

  • 1Department of Computer Science, Arkansas State University, State University, Arkansas 72467, USA. xzhuang@csm.astate.edu

BMC Bioinformatics
|January 16, 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

Local Water Ordering Directs Early-Stage Nucleation in the Humidity-Responsive Self-Assembly of Phenylalanine Dipeptide at the Air Surface.

The journal of physical chemistry. B·2026
Same author

Quantifying weak intermolecular interactions at soft matter interfaces with sum frequency generation vibrational spectroscopy.

Advances in colloid and interface science·2026
Same author

Galactosylated LNP-mediated hepatic Sam68 silencing improves glucose homeostasis in diabetes by suppressing gluconeogenesis.

Journal of nanobiotechnology·2026
Same author

Tenofovir Alafenamide in the Treatment of Chronic Hepatitis B Virus Infection in the High-Replicative Low-Inflammatory Phase: A 48-Week Randomized Controlled Trial.

Journal of medical virology·2026
Same author

Bioelectrical impedance analysis-derived phase angle predicts sarcopenia in older adults with type 2 diabetes mellitus.

Endocrinologia, diabetes y nutricion·2026
Same author

Impact of G-CSF on Donor TCR Clonal Diversity and T Cell Function During Donor HSC Mobilisation.

Cell proliferation·2026
Same journal

OpenIMC: an open-source platform for analyzing single-cell and spatial proteomics by imaging mass cytometry.

BMC bioinformatics·2026
Same journal

NAP: an open source pipeline for cross-domain microbiome profiling using Nanopore sequencing-derived amplicon data.

BMC bioinformatics·2026
Same journal

SurvGME: an R package for survival analysis with graphical and measurement error models.

BMC bioinformatics·2026
Same journal

SimMapNet: a Bayesian framework for gene regulatory network inference using gene ontology similarities as external hint.

BMC bioinformatics·2026
Same journal

Dual channel drug-drug interactions extraction based on cross attention.

BMC bioinformatics·2026
Same journal

FeSseqdb: a curated sequence-level database and interpretable machine learning framework for identifying iron-sulfur proteins.

BMC bioinformatics·2026
See all related articles

This study introduces a new lower bound for solving the maximum common induced subgraph problem in bioinformatics. The research also presents novel techniques for efficiently approaching this computational challenge.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Graph Theory

Background:

  • Structure matching is crucial for understanding biological functions.
  • Bioinformatics models this as a maximum common subgraph problem.
  • Maximum common induced subgraph is a key variant of interest.

Purpose of the Study:

  • To derive a new lower bound for exact algorithms solving the maximum common induced subgraph problem.
  • To investigate upper bounds and develop new algorithmic techniques.
  • To explore the applicability of parameterized computation in bioinformatics.

Main Methods:

  • Utilizing parameterized computation to establish a new lower bound.
  • Reducing the maximum common induced subgraph problem to a maximum clique problem.

Related Experiment Videos

  • Analyzing the product graph of the two input graphs.

    • Main Results:

    • A new, asymptotically tight lower bound for maximum common induced subgraph algorithms.
    • The best known lower bound for exact algorithms in this area.
    • Algorithmic techniques that reduce the problem to maximum clique finding.

    Conclusions:

    • Parameterized computation offers a promising avenue for bioinformatics problems like maximum common subgraph.
    • The derived hardness results and proposed methods pave the way for future research.
    • Further exploration of efficient algorithms for subgraph problems is warranted.