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

The complexity of comparing reaction systems.

Mark Ettinger1

  • 1Los Alamos National Laboratory, Los Alamos, NM 87545, USA. ettinger@lanl.gov

Bioinformatics (Oxford, England)
|April 6, 2002
PubMed
Summary

Comparing biological reaction systems using stoichiometric data is equivalent to the graph isomorphism problem. This approach offers a practical method for analyzing complex biological networks, unlike subsystem searches which are NP-complete.

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

Weekly oral alendronic Acid in male osteoporosis.

Clinical drug investigation·2007
Same author

Prevention of bone loss in postmenopausal women treated with lasofoxifene compared with raloxifene.

Menopause (New York, N.Y.)·2006
Same author

Improving compliance and persistence with bisphosphonate therapy for osteoporosis.

The American journal of medicine·2006
See all related articles

Area of Science:

  • Systems Biology
  • Bioinformatics
  • Computational Biology

Background:

  • Increasing genomic data necessitates understanding encoded biological mechanisms.
  • XML formats like CellML and Systems Biology Markup Language (SBML) are emerging for biological network description.
  • Stoichiometric data is crucial for analyzing biological networks lacking kinetic information.

Purpose of the Study:

  • To establish a computational method for comparing biological reaction systems.
  • To determine the algorithmic complexity of comparing stoichiometric network structures.
  • To explore practical approaches for integrating higher-order network knowledge.

Main Methods:

  • Formulating the comparison of stoichiometric structures as a graph isomorphism problem.
  • Analyzing the computational complexity of related network comparison tasks.
  • Discussing heuristic implementations for practical stoichiometric matrix comparison.

Main Results:

  • Comparing stoichiometric structures of reaction systems is equivalent to the graph isomorphism problem.
  • Graph isomorphism is practically tractable using heuristic algorithms.
  • Searching for subsystems within reaction systems is an NP-complete problem.

Conclusions:

  • Stoichiometric network comparison is algorithmically feasible and practical.
  • Heuristic approaches are key to efficiently comparing biological networks.
  • Network databases and comparison algorithms are vital for advancing systems biology.

Related Experiment Videos