Bioinformatics Vol. 18 no. 3 2002
Pages 465-469
© 2002 Oxford University Press
The complexity of comparing reaction systems
Los Alamos National Laboratory, Los Alamos, NM 87545, USA
Received on August 28, 2001
; revised on October 30, 2001
; accepted on November 9, 2001
Motivation: As more genomic data becomes available there is increased attention on understanding the mechanisms encoded in the genome. New XML dialects like CellML and Systems Biology Markup Language (SBML) are being developed to describe biological networks of all types. In the absence of detailed kinetic information for these networks, stoichiometric data is an especially valuable source of information. Network databases are the next logical step beyond storing purely genomic information. Just as comparison of entries in genomic databases has been a vital algorithmic problem through the course of the sequencing project, comparison of networks in network databases will be a crucial problem as we seek to integrate higher-order network knowledge.
Results: We show that comparing the stoichiometric structure of two reactions systems is equivalent to the graph isomorphism problem. This is encouraging because graph isomorphism is, in practice, a tractable problem using heuristics. The analogous problem of searching for a subsystem of a reaction system is NP-complete. We also discuss heuristic issues in implementations for practical comparison of stoichiometric matrices.
Contact: ettinger{at}lanl.gov