Combinatorial evaluation of systems including decomposition of a system representation into fundamental cycles Number:7,394,472 from the United States Patent and Trademark Office (PTO) owispatent One embodiment of the present invention includes a computer operable to represent a physical system with a graphical data structure corresponding to a matroid. The graphical data structure corresponds to a number of vertices and a number of edges that each correspond to two of the vertices. The computer is further operable to define a closed pathway arrangement with the graphical data structure and identify each different one of a number of fundamental cycles by evaluating a different respective one of the edges with a spanning tree representation. The fundamental cycles each include three or more of the vertices.<H representation, decomposition, Combinatorial, e, 7394472.html, Patent, pto, 7394472

Title: Combinatorial evaluation of systems including decomposition of a system representation into fundamental cycles

Abstract: One embodiment of the present invention includes a computer operable to represent a physical system with a graphical data structure corresponding to a matroid. The graphical data structure corresponds to a number of vertices and a number of edges that each correspond to two of the vertices. The computer is further operable to define a closed pathway arrangement with the graphical data structure and identify each different one of a number of fundamental cycles by evaluating a different respective one of the edges with a spanning tree representation. The fundamental cycles each include three or more of the vertices.

Patent Number: 7,394,472 Issued on 07/01/2008 to Oliveira, et al.

Inventors: Oliveira; Joseph S. (Richland, WA), Jones-Oliveira; Janet B. (Richland, WA), Bailey; Colin G. (Wellington, NZ), Gull; Dean W. (Seattle, WA)
Assignee: Battelle Memorial Institute (Richland, WA)

Appl. No.: 11/247,424

Filed: October 11, 2005

Related U.S. Patent Documents


Application Number	Filing Date	Patent Number	Issue Date
60617380	Oct., 2004

Current U.S. Class: 345/645 ; 340/825.02; 345/420; 345/440; 370/254; 370/408; 709/201; 709/220; 709/249; 715/853

Current International Class: G06F 15/16 (20060101); G06F 17/50 (20060101); G06T 15/00 (20060101); G06T 15/20 (20060101); G06T 17/00 (20060101); G06T 17/20 (20060101); H04L 12/56 (20060101)

Field of Search: 709/201,204,220-224,249,250,252 345/420,423,440,645 340/825.02,825,2.1 370/230,229,254-256,400,408,457-458 715/734-736,853-854 716/1,3 726/3 382/158

References Cited [Referenced By]

U.S. Patent Documents


5257363	October 1993	Shapiro et al.
5282147	January 1994	Goetz et al.
5649198	July 1997	Shibata et al.
5926101	July 1999	Dasgupta
5940542	August 1999	Li et al.
5947899	September 1999	Winslow et al.
6114825	September 2000	Katz
6205533	March 2001	Margolus
6647141	November 2003	Li
6671874	December 2003	Passova
2003/0229807	December 2003	Qiao et al.
2004/0059736	March 2004	Willse et al.
2004/0109407	June 2004	Grover et al.
2004/0263880	December 2004	Ito et al.
2005/0075848	April 2005	Taylor et al.
2005/0111386	May 2005	Jain et al.

Foreign Patent Documents


0 938 045	Aug., 1999	EP
1 085 693	Mar., 2001	EP

Other References

WJ. Heuett, Biochemical Reaction Network Analysis, Oct. 28, 2002, University of Washington, Department of Applied Mathematics. cited by other .
Mathematical Biology, Feb. 11, 2002, Computational Sciences & Mathematics. cited by other .
Gjalt G. De Jong *, Bill Lin, A Communicating Petri Net Model for the Design of Concurrent Asynchronous Modules, IMEC Kapeldreef 75, B 3001 Leuven, Belgium. cited by other .
Matthew C. Cary, Lattice Basis Reduction Algorithms and Applications, Feb. 27, 2002. cited by other .
Understanding Spanning-Tree Protocol. cited by other .
Linear Programming and Game Theory, Network Models. cited by other .
James Oxley, What is a Matroid?, May 1, 2003, 1991 Mathematics Subject Classification, Department of Mathematics, Louisiana State University, Baton rouge, LA. cited by other .
Gunter M. Ziegler*, Oriented Matroids Today, Sep. 10, 1998, Department of Mathematics, Technische Universitat Berlin, Berlin, Germany. cited by other .
W. Imrich and P. Stadler, Minimum Cycle Bases of Product Graphs, Dept. of Mathematics and Applied Geometry, Montanuniversitat Leoben, Leoben, Austria; (Date Unknown). cited by other .
J. Oliveira, C. Bailey, J. Jones-Oliveira, D. Dixon, An Algebraic-combinatorial Model for the Identification and Mapping of Biochemical Pathways, 2001 Society for Mathematical. cited by other .
J. Oliveira et al., A Computational Model for the Identification of Biochemical Pathways in the Krebs Cycle, Journal of Computational Biology, vol. 10, Nov. 1, 2003, pp. 57-82. cited by other.

Primary Examiner: Sajous; Wesner
Attorney, Agent or Firm: Krieg DeVault LLP Paynter; L. Scott

Government Interests

GOVERNMENT RIGHTS

This invention was made with Government support under Contract Number DE-AC0676RL01830 awarded by the U.S. Department of Energy. The Government has certain rights in the invention.

Parent Case Text

CROSS-REFERENCE TO RELATED APPLICATIONS

The present application claims the benefit of U.S. Provisional Patent Application No. 60/617,380 filed 8 Oct. 2004, which is hereby incorporated by reference in its entirety.

Claims

What is claimed is:

1. A method, comprising: preparing a model of a physical system, the model corresponding to a graphical dataset defining a number of vertices each corresponding to a different system variable and a number of edges each corresponding to a conditional transition path between two of the vertices, the model defining a closed pathway structure including a plurality of closed pathways; and decomposing the closed pathway structure of the model into a minimal set of fundamental cycles numbering less than the plurality of closed pathways, the fundamental cycles each being unique relative to one another, the decomposing of the closed pathway structure including: identifying a number of unique two-cycles each including two different members of the vertices; and successively evaluating different ones of the edges to identify the fundamental cycles belonging to the minimal set that each include three or more different members of the vertices.

2. The method of claim 1, wherein the decomposing of the closed pathway structure further includes: preparing a matrix from the model; determining a basis size of a nullspace of the matrix; and preparing a spanning tree representation and adjoining each of the different ones of the edges to identify each of the fundamental cycles of the minimal set that include three or more of the vertices in one-to-one correspondence.

3. The method of claim 1, wherein the preparing of the model includes: establishing a data structure corresponding to a multigraph representation of the system; and transforming the multigraph representation into an undirected graph representation.

4. The method of claim 3, which includes: preparing the multigraph representation from a hyperdigraph representation; and determining a nullspace of a matrix corresponding to the undirected graph representation.

5. The method of claim 4, which includes providing the hyperdigraph representation from a Petri net representative of the system, the hyperdigraph representation corresponding to an oriented matroid.

6. The method of claim 1, wherein the system includes a physical network, the network including a number of spaced apart nodes in operatively coupled by a number of links.

7. The method of claim 2, wherein the physical network defines an electric power grid.

8. An apparatus, comprising: a device carrying operating logic executable by a computer to perform the method of claim 1.

9. The apparatus of claim 8, wherein the device includes a removable memory device.

10. The apparatus of claim 8, wherein the device includes at least a portion of a computer network.

11. An apparatus, comprising: a computer operable to model a physical network with a graphical data structure representative of a matroid, the physical network including several spatially separated nodes coupled together by a number of corresponding links, the corresponding links each operatively connecting two of the nodes to provide for network transmission between the two of the nodes, the data structure defining a closed pathway arrangement, the computer being operable to process the graphical data structure relative to a spanning tree data structure to decompose the closed pathways into a minimal cycle set representative of all pathways of the closed pathway arrangement.

12. The apparatus of claim. 11, wherein the computer includes one or more processors and a removable memory device encoded with operating logic executable by the one or more processors to determine the minimal cycle set and store the minimal cycle set in a database form.

13. The apparatus of claim 11, wherein the data structure corresponds to a number of vertices connected by edges and the computer includes means for identifying a number of two cycles, the two-cycles each corresponding to a different pair of the vertices, and means for progressively evaluating different ones of the edges to identify members of the minimal cycle set that each include three or more of the vertices.

14. The apparatus of claim 11, wherein the computer includes: means for representing the network with a first type of graph; means for transforming the first type of graph to a second type of graph; means for preparing a matrix from the second type of graph; and means for determining a basis of a nullspace for the matrix, the basis corresponding to membership of the minimal cycle set.

15. An apparatus, comprising: a computer operable to prepare a model of a physical system, the model corresponding to a graphical dataset defining a number of vertices each corresponding to a different system variable and a number of edges each corresponding to a conditional flow path between two of the vertices, the model defining a closed pathway structure including a plurality of closed pathways, the computer being operable to decompose the closed pathway structure of the model into a minimal set of fundamental cycles numbering less than the plurality of closed pathways, the fundamental cycles each being unique relative to one another, the computer performing decomposition of the closed pathway structure by identifying a number of unique two-cycles each including two different members of the vertices and successively evaluating different ones of the edges to identify the fundamental cycles belonging to the minimal set that each include three or more different members of the vertices.

16. The apparatus of claim 15, wherein the computer is further operable to determine a matrix from the graphic dataset and determine a basis for a nullspace of the matrix.

17. The apparatus of claim 15, wherein the computer includes a memory and is operable to store the minimal set in a database form.

18. The apparatus of claim 15, the computer including means for evaluating a perturbation of the network based on the minimal set of the fundamental cycles.

19. A method, comprising: representing a physical system with a graphic data structure corresponding to a number of vertices and a number of edges, the edges each corresponding to two of the vertices; defining a closed pathway arrangement with the graphical data structure; and for each different one of a number of unique fundamental cycles of the closed pathway arrangement, identifying the different one of the fundamental cycles as a function of a spanning tree representation and a different one of the edges, the fundamental cycles each including three or more of the vertices.

20. The method of claim 19, which includes: establishing a matrix representation corresponding to the graphical data structure; determining a basis size of a nullspace corresponding to the matrix.

21. The method of claim 19, wherein the vertices each correspond to a state variable of the system, the edges each correspond to a conditional transition path, and further comprising: preparing the graphic data structure from a hyperdigraph representation; and determining each of the two-cycles of the closed pathway arrangement.

22. The method of claim 19, which includes evaluating a perturbation of the system with the fundamental cycles.

23. The method of claim 19, which includes: preparing a minimal cycle set including the fundamental cycles; and determining frequency of occurrence of each different one of the vertices in the minimal cycle set.

24. The method of claim 19, wherein the system includes an electric power grid.

25. The method of claim 19, wherein the data structure corresponds to a multigraph representation of the system and which includes: preparing the data structure from a Petri net representation; transforming the multigraph representation into an undirected graph representation; and determining a basis size for a nullspace of a matrix corresponding to the undirected graph representation.

26. A device including operating logic executable by a computer to perform the method of claim 19.

27. An apparatus, comprising: a computer operable to represent a physical system with a graphical data structure corresponding to a matroid, the graphical data structure corresponding to a number of vertices and a number of edges, the edges each corresponding to two of the vertices, the computer being further operable to define a closed pathway arrangement with the graphical data structure and identify a different one of a number of fundamental cycles by evaluating a different respective one of the edges with a spanning tree representation, the fundamental cycles each including three or more of the vertices.

28. The apparatus of claim 27, wherein the computer is further operable to determine a matrix from the graphic dataset and determine a basis for a nullspace of the matrix.

29. The apparatus of claim 27, wherein the computer includes a memory and is operable to determine a minimal set of the fundamental cycles that is representative of all pathways defined by the closed pathway arrangement and store the minimal set in the memory in a database form.

30. The apparatus of claim 27, the computer including means for evaluating a perturbation of the network based on the minimal set of the fundamental cycles.

Description

BACKGROUND

The present invention relates to data processing and more particularly, but not exclusively, relates to a unique methodology for the decomposition of a network-of-networks representation of a system into a set of fundamental cycles, where the fundamental cycles are used to completely characterize and control both linear and nonlinear systems.

There is an ongoing desire to more meaningfully evaluate and control complex systems behaviors. Frequently, these systems can be modeled as a finite group of constituents that interact in a predictable manner based on certain physical rules or conditions. Even so, the application of existing mathematical tools to fully evaluate these systems can be time/cost prohibitive, and sometimes can provide misleading results due to round-off errors or the like. Also, current evaluation/simulation schemes are often not up to the task of analyzing the impact that multiple, simultaneous perturbations can have on such systems. Accordingly, there continues to be a demand for further contributions in this area of technology.

SUMMARY

One embodiment of the present invention is a unique data processing technique. Other embodiments include unique apparatus, devices, and methods for processing data.

A further embodiment comprises: representing a network with a graphical data structure corresponding to a matroid; defining a number of closed pathways with the graphical data structure; and recursively processing the graphical data structure to decompose the closed pathways into a minimal cycle set representative of the complex network.

Another embodiment includes a computer that has means for representing a physical system with a graphic data structure corresponding to a number of vertices and a number of edges, means for defining a closed pathway arrangement with the graphical data structure, and means for identifying each different one of a number of the fundamental cycles of the closed pathway arrangement based on a spanning tree representation and a different respective one of the edges.

Yet another embodiment comprises: preparing a model of a physical system and decomposing a closed pathway structure defined by the model into a minimal set of fundamental cycles that are unique relative to one another. This decomposition includes identifying a number of unique two-cycles each including two different members of the vertices and successively evaluating different ones of the edges to identify the fundamental cycles belonging to the minimal set that each include three or more different members of the vertices. In one form, the model corresponds to a graphical dataset defining a number of vertices that are each representative of a different system variable and a number of edges that are each representative of a conditional transition path between two of the vertices.

In another embodiment, a computer models a physical network with a graphical data structure representative of a matroid that corresponds to a closed pathway arrangement. This physical network includes several spatially separated nodes coupled together by a number of corresponding links that each operatively couple two of the nodes to provide for network transmission therebetween. The computer processes the graphical data structure relative to a spanning tree representation to decompose the closed pathway arrangement into a minimal cycle set representative of all pathways thereof.

In a further embodiment, a computer executes operating logic to prepare a model of a physical system that corresponds to a graphical dataset defining a number of vertices and a number of edges. The vertices are each representative of a different system state variable and the edges are each representative of a conditional flow path between two of the vertices. The model defines a closed pathway structure including a plurality of closed pathways. As it is executed, the operating logic decomposes the closed pathway structure of the model into a minimal set of fundamental cycles numbering less than the plurality of closed pathways. These fundamental cycles are unique relative to one another. Decomposition of the closed pathway structure includes identifying a number of unique two-cycles each including two different members of the vertices and successively evaluating different ones of the edges to identify the fundamental cycles belonging to the minimal set.

A different embodiment includes: representing a physical system with a graphic data structure corresponding to a number of vertices and a number of edges, the edges each corresponding to two of the vertices; defining a closed pathway arrangement with the graphical data structure; and for each different one of a number of unique fundamental cycles of the closed pathway arrangement, identifying the different one of the fundamental cycles as a function of a spanning tree representation and a different one of the edges, where the fundamental cycles each include three or more of the vertices.

Accordingly, one object of the present invention is to provide a unique data processing technique.

Another object is to provide a unique apparatus, device, or method for processing data and/or modeling a system.

Further objects, embodiments, forms, features, aspects, benefits, and advantages of the present invention will become apparent from the drawings and detailed description contained herein.

BRIEF DESCRIPTION OF THE VIEWS OF THE DRAWING

FIG. 1 is a diagrammatic view of a computing system.

FIG. 2 is a flowchart illustrating a data processing procedure that can be executed with the system of FIG. 1.

FIGS. 3-5 are diagrammatic views relating to Petri net representation and corresponding incidence matrices for biochemical reactions that can be evaluated under the procedure of FIG. 2.

FIG. 6 is a view of a graph corresponding to the Petri net representation of FIG. 4 and incidence matrix of FIG. 5.

FIG. 7 is a diagrammatic view of a minimal cycle set corresponding to the Petri net of FIG. 4 and incidence matrix of FIG. 5.

FIGS. 8 and 9 are flowcharts illustrating a routine for determining a minimal cycle set based on a matroid representation.

FIG. 10 is a Petri net representation of the Krebs cycle processed in accordance with the procedure of FIG. 2.

FIG. 11 is chart listing places for the Petri net representation of FIG. 10.

FIGS. 12-19 are more detailed Petri net representations of subreactions 1, 2/3, 4, 5, 6, 7, 8, and 9; respectively, of the Krebs cycle depicted in FIG. 10.

FIG. 20 is a diagram of a portion of an incidence matrix for the Petri net representation of the Krebs cycle represented in FIG. 10.

FIGS. 21 and 22 are charts listing occurrence of transitions and places, respectively, in the minimal cycle set for the Krebs cycle represented in FIG. 10; where the minimal cycle set was determined in accordance with the routine of FIGS. 8 and 9.

FIG. 23 is a diagrammatic view of the "forward only" minimal cycles corresponding to the Krebs cycle representation of FIG. 10.

FIG. 24 is a control flow diagram for electric power grid evaluation process that includes application of the procedure of FIG. 2.

FIG. 25 is a Petri net representation of an electric power circuit.

FIG. 26 is schematic view of one type of electrical power grid distribution network.

FIG. 27 is a Petri net representation of the network of FIG. 26.

FIG. 28 is a chart of a minimal cycle set corresponding to the Petri net representation of FIG. 27 as provided in accordance with the routine of FIGS. 8 and 9.

FIGS. 29 and 30 are charts listing occurrence of places and transitions, respectively, in the minimal cycle set of FIG. 28.

FIG. 31 is schematic view of another type of electrical power grid distribution network.

FIG. 32 is a Petri net representation of the network of FIG. 31.

FIGS. 33 and 34 are charts that collectively depict a minimal cycle set corresponding to the Petri net representation of FIG. 32 as determined in accordance with the routine of FIGS. 8 and 9.

FIG. 35 is a diagrammatic view of certain two-cycles for the Petri net of FIG. 32.

DETAILED DESCRIPTION OF SELECTED EMBODIMENTS

For the purpose of promoting an understanding of the principles of the invention, reference will now be made to the embodiments illustrated in the drawings and specific language will be used to describe the same. It will nevertheless be understood that no limitation of the scope of the invention is thereby intended. Any alterations and further modifications in the described embodiments, and any further applications of the principles of the invention as described herein are contemplated as would normally occur to one skilled in the art to which the invention relates.

FIG. 1 diagrammatically depicts computer system 20 of one embodiment of the present invention. System 20 includes computer 21 with processor 22. Processor 22 can be of any type, and is configured to operate in accordance with programming instructions, dedicated hardware, and/or another form of operating logic. In one embodiment, processor 22 is integrated circuit based, including one or more digital, solid-state central processing units each in the form of a microprocessor. Processor 22 can include one or more central processing units (CPUs) configured for operation in a parallel, pipeline, or other multiprocessing arrangement.

System 20 also includes operator input devices 24 and operator output devices 26 operatively coupled to processor 22. Input devices 24 include a conventional mouse 24a and keyboard 24b, and alternatively or additionally can include a trackball, light pen, voice recognition subsystem, and/or different input device type as would occur to those skilled in the art. Output devices 26 include a conventional graphic display 26a, such as a color or noncolor plasma, Cathode Ray Tube (CRT), or Liquid Crystal Display (LCD) type, and color or noncolor printer 26b. Alternatively or additionally output devices 26 can include an aural output system and/or different output device type as would occur to those skilled in the art. Further, in other embodiments, more or fewer operator input devices 24 or operator output devices 26 may be utilized.

System 20 also includes memory 28 operatively coupled to processor 22. Memory 28 can be of one or more types, such as solid-state electronic memory, magnetic memory, optical memory, or a combination of these. As illustrated in FIG. 1, memory 28 includes a removable/portable memory device 28a that can be an optical disk (such as a CD ROM or DVD); a magnetically encoded hard disk, floppy disk, tape, or cartridge; and/or a different form as would occur to those skilled in the art. In one embodiment, at least a portion of memory 28 is operable to store executable operating logic for processor 22 in the form of programming instructions. Alternatively or additionally, memory 28 can be arranged to store data other than programming instructions for processor 22. In still other embodiments, memory 28 and/or portable memory device 28a may not be present.

System 20 also includes computer network 30, which can be a Local Area Network (LAN); a Municipal Area Network (MAN); a Wide Area Network (WAN), such as the Internet; another type as would occur to those skilled in the art; or a combination of these. Network 30 couples computer 40 to computer 21; where computer 40 is remotely located relative to computer 21. Computer 40 can include a processor, input devices, output devices, and/or memory as described in connection with computer 21; however these features of computer 40 are not shown to preserve clarity. Computer 40 and computer 21 can be arranged as client and server, respectively, in relation to some or all of the data processing of the present invention. For this arrangement, it should be understood that many other remote computers 40 could be included as clients of computer 21, but are not shown to preserve clarity. In another embodiment, computer 21 and computer 40 can both be participating members of a distributed processing arrangement with one or more processors located at a different site relative to one or more others. The distributed processors of such an arrangement can be used collectively to execute routines according to the present invention. In still other embodiments, remote computer 40 may be absent.

Operating logic for processor 22 is arranged to facilitate performance of various routines, subroutines, procedures, stages, operations, and/or conditionals described hereinafter. This operating logic can be of a dedicated, hardwired variety and/or in the form of programming instructions (software and/or firmware) as is appropriate for the particular processor arrangement. Such logic can be at least partially encoded on device 28a for storage and/or transport to another computer. Alternatively or additionally, the logic of computer 21 can be in the form of one or more signals carried by a transmission medium, such as network 30.

System 20 is also depicted with computer-accessible data sources or datasets generally designated as corpora 50. Corpora 50 include datasets 52 local to computer 21 and remotely located datasets 54 accessible via network 30. Computer 21 is operable to process data selected from one or more of corpora 50. The one or more corpora 50 can be accessed with a data extraction routine executed by processor 22 to selectively extract information according to predefined criteria. In addition to datasets 52 and 54, data may be acquired from a datastream as represented by local datastream source 56 and/or remote datastream source 58, which may be live, realtime, or otherwise. The data mined in this manner can be processed with system 20 to provide one or more corresponding data processing outputs in accordance with the operating logic of processor 22.

FIG. 2 illustrates a flowchart of data processing procedure 120. Procedure 120 can be implemented in accordance with operating logic of system 20. Procedure 120 begins with operation 122. In operation 122, a physical system is selected for evaluation. Typically, the selected system is characterized by data from corpora 50, such a datasets 52 and/or 54 accessed directly/locally or indirectly/remotely through network 30. The system can be of any type, including but not limited to a biological process or reaction, such as the Krebs cycle; a communication system, such as a computer network, a telephone network, a collection of communicating individuals and/or devices; an arrangement of related signals of a homogenous or heterogenous type; a circuit of an electric, magnetic, optical, pneumatic, and/or hydraulic type; a manufacturing or assembly procedure/process; a meteorological model; and/or an economic model, just to name a few representative examples.

Procedure 120 continues with operation 128. In operation 128, the selected system is described in terms of a group of interconnected constituents or nodes with a form of network and/or graphic model. In one form, a Petri net representation is generated. This form is readily interchangeable with a hyperdigraph model, that is suitable for mathematical treatment as a matroid. By way of nonlimiting example, a biochemical reaction can be selected as a system in operation 122 subject to Petri net modeling in operation 128.

To better understand this approach, certain terminology is further described. A "directed graph" is a data structure that conveys connectivity and direction. It is composed of two sets: a vertex set and an edge set. Typically circles or "dots" represent vertices and arrows represent edges in a directed graph. A vertex contains a data element, and an edge specifies a rule and direction for the relationship between any two vertices. A "Petri net" is an extension of this notion in which edges (called "transitions") are allowed many input and output vertices (called "places"). In modeling a biochemical pathway with a Petri net, a "place" represents a chemical species, and a "transition" represents a chemical event. In this context, a "chemical event" refers to any interaction that converts one molecule into another, including intermediate or transitory processes, such as a complex formation. A chemical event could be a classical chemical reaction (e.g., condensation, phosphorylation), an enzymatic process (e.g., substrate binding, release of product), and/or various reactant and product interactions where the chemical nature of the interacting partners is not changed, (e.g., complex formation).

The Petri net model provides a corresponding set of combinatorial tools for deducing the qualitative control logic of biochemical networks. This approach defines states in the system to be marked places and associated tokens as circles with a "P" designator in Petri net illustrations herein. These places symbolically represent biomolecular species such as metabolites, enzymes, and cofactors, etc. The systematic nature of this modeling approach studies the circuit arrangements or partitions of a biochemical network as functions of the marked places (biochemical species), subject to a set of process control rules defined by the transition conditionals of the Petri net that appear as rectangles or squares between places and have the "t" 0 (transition) designator in associated Petri net illustrations. When a transition is executed, it has been "fired" and a set of transitions being fired is called a firing sequence.

FIG. 3 depicts a table comparing different ways to represent molecular reaction and complex formation, in the second and third rows, respectively. The first row and first column provide labeling for FIG. 3. The second column designates a conventional chemical equation form, the third column provides a symbolic representation of the reaction, and the fourth column depicts a corresponding Petri net form. The phenomenological model of a kinetic reaction network can be defined in generality by a Petri net. Complex biochemical processes can be considered in terms of two types of biochemical building blocks: (1) molecular reaction and (2) complex formation, which are depicted in the second and third rows of FIG. 3, respectively. These building blocks can be considered as Petri net stencils. In the Petri net representations, forward paths are denoted by solid lines with directional arrows, and backward paths are denoted by dashed lines with directional arrows.

The topology of a Petri net is completely specified by its incidence matrix, whose rows are places and columns are transitions. The last column of FIG. 3 provides incidence matrices each corresponding to the Petri net representation of the same row. Each entry in the incidence matrix is a 0, 1, or -1. These quantities specify the absence or presence of a connecting edge between two places, as well as its direction. Circuits can be found by generating the incidence matrix. If information is flowing from a place to a transition, the corresponding matrix entry is -1, representing a loss. If the flow is from a transition to a place, the corresponding matrix entry is +1, representing a gain. The matrix entry is zero otherwise. Associated with a Petri net is a marking space. Markings can be considered as a vector of token counts representing information or measure of the state represented by the corresponding place P. A place producing the information is referred to as a source; and a place consuming the information is a sink. Flux conservation is achieved when the rate at which tokens are being produced equals the rate at which tokens are being consumed. When the flux for a given firing sequence starts and ends at the same point, it is called a circuit. These circuits can be of interest because they represent the paths by which the network is passing as well as conserving information.

FIG. 4 provides a comparison between various ways of representing an enzyme reaction, including a Petri net model in the fourth column. As depicted in FIG. 4, an enzyme-catalyzed reaction is modeled as a series of separate stages as follows (not necessarily the actual physical process): (1) interaction of substrates, (2) association of the interacting substrates with the enzyme, (3) transformation of substrates to products by the enzyme, (4) dissociation of products from the enzyme, and (5) separation of the products from one another. This model focuses on accounting for each molecular species and its corresponding set of possible reactions. The biochemical reaction is viewed as an edge or subset of edges in a graph, depicting flow of information rather than detailed reaction mechanisms.

The Petri net representation in turn defines a hyperdigraph. For a hyperdigraph representation, the vertices represent the places P of the network and the edges represent the transitions t (rules or conditions that must be true before transitioning between places). As with all hypergraphs, Petri net edges may connect a set of vertices with cardinality greater than two. In order to identify the circuit decomposition of a general network as further described hereinafter, the hyperdigraph representation of the Petri net is transformed to satisfy the more general condition of being a graph. There are several ways to obtain a faithful graph representation of the hyperdigraph. For example, one can either transform the hyperdigraph into a directed bipartite graph or into an undirected graph while maintaining a record of the added edges, compressed multiedges, and all of the directional information. The conversion of the hyperdigraph arises because there may be multiple inputs and/or outputs associated with the transitions that are more readily manipulated when in a true graph form.

The molecular reaction presented in the second row of FIG. 3 is a simple reversible reaction path that is referred to as a simple circuit in the network model and a two-cycle in the graph representation. The complex formation in the last row of FIG. 3 is a more complex example. As can be seen in the Petri net representation of complex formation, transition ti contains the rule combining the flow of information from places P.sub.1 and P.sub.2 to P.sub.3; similarly, transition t.sub.2 contains the rule splitting the flow of information from place P.sub.3 into places P.sub.1 and P.sub.2. The representation assumes that all transitions are simply unary, where the regulation cannot be specified. To address these conditions, a graph is associated with a Petri net that has exactly the same cycles as the net has circuits.

Once the incidence matrix N is generated, the left nullspace of the matrix can be determined by finding solutions of N.sup.Tv=0, where n corresponds to the number of reacting species within the biochemical system (places), m corresponds to the number of reactions that are taking place (transitions), and v is the n-dimensional solution vector.

In addition to its topology or connectivity, a Petri net at a given time has a state or marking that is specified by the number of tokens (quantity of a molecular species) in each place. When a reaction or series of reactions takes place, the corresponding transitions are said to have fired, and the token numbers then change commensurate with the stoichiometry of the reaction. For example, if a firing sequence of the Petri net that describes the fumarase reaction fires once, there will subsequently be one less molecule of fumarate, one more molecule of L-malate, and the same number of molecules of fumarase. Table I depicts this process as follows:

TABLE-US-00001 TABLE I fumarate + fumarase fumarate: known as association, fumarate:fumarase L-malate:fumarase, known as transformation, L-malate:fumarase L-malate + fumarase, known as dissociation, and Collectively: fumarase + fumarase L-malate + fumarase.

Should the number of fumarate molecules be zero, this particular reaction will be unable to fire until some other reaction sequence replenishes this molecule. With the Petri net approach, the transformation of fumarate to L-malate can be modeled without detailed knowledge of how the process has occurred at the molecular level. Accordingly, uncertain parameter information can be effectively included in the network model if the connectivity is known.

Discrete approaches to modeling kinetics, such as the one under consideration can be desired when dealing with relatively small numbers of molecules relative to molar scales. Indeed, there are often only thousands to millions of a given protein molecule in a cell, which is far less than even pM quantities (10-12 moles=6.times.10.sup.11 molecules). Because chemical entities react in a unit fashion governed by the stoichiometry of the process (fractions of proteins do not react--only whole ones), integer-based modeling of protein reactions in a living cell is typically desired. Petri nets are generally an appropriate candidate for such modeling.

Consider one such example involving nonsimple reactions, the enzyme reaction presented in FIG. 4. The corresponding incidence matrix of the Petri net representation is also illustrated in FIG. 4. This incidence matrix yields an associated family of edge-sets with only six minimal elements corresponding to the three two-cycles: {t.sub.1, t.sub.2}, {t.sub.3, t.sub.4}, and {t.sub.5, t.sub.6}. The first and last of these two-cycles each give rise to two distinct cycles. A corresponding digraph for the enzyme reaction of FIG. 4 is presented in FIG. 6, with its corresponding incidence matrix being presented in FIG. 5. With the conversion of the Petri net of FIG. 4 to the digraph of FIG. 6, notation changes slightly, in that places of the Petri net become vertices "v" of the digraph and transitions of the Petri net become edges "e" of the digraph. For example, the transition of P.sub.4.fwdarw.t.sub.3.fwdarw.P.sub.5 is denoted by edge e.sub.10. Accordingly, the digraph of FIG. 6 distinguishes between multiple paths passing through a single transition, such that the communication of information through transition t.sub.1 is now split such that P.sub.4.fwdarw.t.sub.1.fwdarw.P.sub.5 becomes e.sub.2 and P.sub.4.fwdarw.t.sub.1.fwdarw.P.sub.1 becomes e.sub.7. The complete list of correspondences between transitions and digraph edges is provided in FIG. 5. The basis size was determined to be six. The seven unique minimal cycles or paths are presented in FIG. 7.

While this cycle decomposition can be determined by inspection from the graph of FIG. 6, in more complicated representations, a more systematic routine is envisioned. Returning to FIG. 2, procedure 120 advances from operation 128 to routine 140. Routine 140 provides an algorithm for decomposing the Petri net/hyperdigraph representation into a minimal set of fundamental circuits or cycles. FIGS. 8 and 9 illustrate routine 140 in greater detail in flowchart form. Routine 140 starts with the generation of a graphic data structure that corresponds to a Petri net or comparable model in operation 142. A hyperdigraph representation is prepared from the Petri net or alternatively could be directly used as an initial model. From the hyperdigraph representation, a multigraph representation, such as the digraph of FIG. 6 is prepared. This transformation results in the same number of graph vertices as places; however, edges are added in order to differential multiple paths through a given transition. Routine 140 proceeds from operation 142 to operation 144. In operation 144, the corresponding incidence matrix is generated. The creation of the matrix depicted in FIG. 5 for the FIG. 6 digraph corresponds to execution of operation 144.

Routine 140 continues with operation 146 in which the directed graph representation is transformed into an undirected graph and a corresponding incidence matrix is established, that corresponds to an oriented matroid. In converting to an undirected graph, edges are condensed by removing repeated edges and direction information is stripped. This edge and directional information is preserved as needed to reconstitute desired information regarding the initial model from which it is generated. It should be appreciated that there exists a bijective correspondence between the set of edges for this undirected graph and the set of obtainable two cycles of the initial model (Petri net/hyperdigraph), and that the undirected graph has cycles in one-to-one correspondence with the circuits of the directed bipartite graph representation of the Petri net. Based on this property, the cycles of an undirected graph form a Z.sub.2-vector space, which is the nullspace of the corresponding incidence matrix, considered as a Z.sub.2-matrix.

From operation 146, operation 148 is performed with the undirected graph. The vector space of cycles for the undirected graph has dimension (m-n+1) where m is the number of edges of the transformed matrix, and n the number of vertices. Hence the space has size 2.sup.(m-n+1). In operation 148, the basis size for this vector size of the nullspace is determined. This basis size may be found from a spanning tree for the graph. Continuing with operation 150, all two-cycles are determined, given that there exists a bijective correspondence between the set of edges in the undirected graph and the set of obtainable two-cycles.

Routine 140 continues with subroutine 160 that is more specifically described in flowchart form in FIG. 9. Subroutine 160 is directed to identifying any minimal cycles that include more than two vertices, such as three-cycles, four-cycles, etc. through application of a corresponding spanning tree. A "tree" is a mathematical structure that can be viewed as either a graph or as a data structure. The two views are equivalent, because a tree data structure contains not only a set of elements, but also connections between elements, giving a tree graph. A "tree graph" is a set of straight line segments connected at their ends containing no closed loops (cycles). In other words, it is a simple, undirected, connected, acyclic graph. A tree with n nodes has n-1 edges. Conversely, a connected graph with n nodes and n-1 edges is a tree. All trees are considered bipartite graphs. A "spanning tree" of a graph is a subset of n-1 edges that form a tree. The number of nonidentical spanning trees of a graph "G" is equal to any cofactor of the degree matrix of "G" minus the adjacency matrix of "G," which is known as the matrix tree theorem. A tree contains a unique spanning tree, a cycle graph C.sub.n contains n spanning trees.

Subroutine 160 begins with generation of a spanning tree representation for the graph in operation 162. Given the property that a fundamental cycle is one having only one edge not contained in the spanning tree, then the addition of any edge to this tree, which has no cycles initially, creates exactly one cycle. As a result, fundamental cycles have a one-to-one correspondence with the edges adjoined to the spanning tree.

Consequently, in operation 164, an edge is added from the graph that is not in the spanning tree representation. From operation 164, subroutine 160 continues with conditional 166. Conditional 166 tests if the cycle resulting from the addition of the edge in operation 162 is already contained in a listing of minimal cycles. This test includes determining whether the subject cycle can be composed from any smaller cycles of the listing, and only keeping those that cannot be composed from other smaller cycles of the list. This approach may result in redundantly listing one or more minimal cycles, which can be readily removed. If the test of conditional 166 is true (affirmative), subroutine 160 continues with operation 168. In operation 168, the subject cycle is listed. It should be appreciated that each minimal cycle corresponds to a null vector of the incidence matrix of the transformed graph. There is an empty cycle in the undirected graph and two empty cycles in the directed graph (digraph), that are ignored. Further, the reversibility assumption simplifies this process considerably, such that every undirected cycle gives rise to exactly two positive cycles-one in each direction.

Subroutine 160 continues from operation 168 with conditional 170. If the test of conditional 166 is false (negative), then subroutine 160 bypasses operation 168, and proceeds directly to conditional 170. Conditional 170 tests whether there are any more edges of the undirected graph to be evaluated with the spanning tree. If the test of conditional 170 is true (affirmative), subroutine 160 returns to operation 164 to evaluated the next edge. If the test of conditional 170 if false (negative), subroutine 160 returns to routine 140 of FIG. 8. Routine 140 proceeds from subroutine 160 to operation 180 to restore directionality and edge information as desired to the minimal cycle representation (listing) that results from subroutine 160. Routine 140 then returns.

Applying routine 140 to a more general case, the Krebs cycle has been evaluated. The tricarboxylic acid (TCA) or Krebs cycle is a series of biochemical reactions central to energy production in all eukaryotic cells. Substrates for the cycle include the products of glycolysis, protein, and lipid catabolism. Products of the TCA cycle are nucleotide reducing equivalents whose entry into the electron transport chain allows complete oxidation of molecules with concomitant production of adenosine triphosphate (ATP), the major energy molecule of the cell. In some instances not all small molecular species such as inorganic phosphate, carbon dioxide, and water are included in the model that follows, because they are not likely to have limiting concentrations in a living cell; however, the modeling approach does not preclude addition of such species in an alternative embodiment.

The Krebs cycle is the second stage in glucose oxidation. The Krebs cycle takes the products of glycolysis, which are pyruvates, and converts two of the carbons in pyruvate to CO.sub.2 and also transfers electrons to electron carriers. As part of this process, three molecules of nicotinamide adenine dinucleotide (oxidized form) (NAD) (where NAD is NAD+) are reduced to nicotinamide adenine dinucleotide H (reduced form) (NADH), and one molecule of flavin adenine dinucleotide (oxidized form) (FAD) is converted to flavin adenine dinucleotide H.sub.2 (reduced form) (FADH.sub.2).

Fifty-nine places and 86 transitions were utilized to specify the Krebs cycle in a Petri net representation that was simplified by not tracking the number of water molecules nor the CO.sub.2 released. From an operational control systems theory point of view, the transitions act as the control laws for the system whereas the places act as the place variables in the Petri net representation. The Petri net representation is a combinatorial abstraction of the molecular interactions defined over a chemical reaction space where the transitions define the operational conditions or roles that must be satisfied for a reaction to occur. In this graphical representation, a chemical species moves from one place to another subject to a transition rule based on chemical equilibria (thermodynamics) or kinetics. The chemical species do not pass formally through the transition but rather are subject to the rules described by the transition. In the Petri net model, two place nodes are connected subject to a transition node if it is possible for the second place to be reached from the first place through some physical/chemical mechanism which is reversible. Of course, the actual amount of chemical system reversibility may be very small and is dependent on the equilibrium constant and/or kinetic rate constants. Because all of the reactions under consideration are potentially reversible, these paired sets of transitions are identified explicitly. While not included in the described embodiment, in alternative embodiments, weights or probabilities can be assigned to the paths of the reactions, varying quantities of molecular species present can be established, the equilibrium constants and/or reaction rates made variable, and/or the timed sequence of various events could be varied.

The overall Petri net representation 300 is schematically depicted in block form in FIG. 10. Subreactions 1, 2/3, 4, 5, 6, 7, 8, and 9 are illustrated in FIGS. 12-19, respectively. Subreaction 1 involves places P.sub.58-P.sub.8 and transitions t.sub.1-t.sub.12; subreaction 2/3 involves places P.sub.8-P.sub.13 and transitions t.sub.13-t.sub.20; subreaction 4 involves places P.sub.13-P.sub.20 and transitions t.sub.21-t.sub.32; subreaction 5 involves places P.sub.20-P.sub.27 and transitions t.sub.33-t.sub.44; subreaction 6 involves places P.sub.27-P.sub.38 and transitions t.sub.45-t.sub.60; subreaction 7 involves places P.sub.38-P.sub.46 and places t.sub.61-t.sub.70; subreaction 8 involves places P.sub.48-P.sub.50 and transitions t.sub.71-t.sub.76; and subreaction 9 involves places P.sub.50-P.sub.58 and transitions t.sub.77-t.sub.86. It should be appreciated that FIG. 10 lacks specific place and transition designations due to preserve clarity. Forward paths are designated by directed solid lines and backward paths are designated by directed dashed lines. Forward and backward paths are given equal weight in terms of describing the possible paths along which information can flow. In the Petri net representations, connections are indicated regardless of whether that communication of information is via a forward or a backward path or combination thereof.

In our representation 300, the Krebs cycle is described by 59 places, one for each species in the cycle. The list of places is specified in FIG. 11. The places highlighted in bold are those later identified by the mathematical model to be of special interest. The places represent the various key chemical species, other than H+, H.sub.2O, and CO.sub.2, produced or consumed in the Krebs cycle.

In the Petri net representation 300 of the Krebs cycle presented in FIG. 10, nucleotide cofactor places are further designated by reference numeral 302 and the enzyme places are further designated by reference numeral 304. FIGS. 12-19 depict certain details of representation 300 not shown at the scale of FIG. 10 for the sake of clarity. Nonetheless, the cross-couplings involving places P57 or NADH, P58 or NAD, and P59 or coenzyme A [CoA] are specifically indicated in FIG. 10. These nucleotide cofactors are involved in interactions between the subreactions which provide alternative pathways through the Krebs cycle.

Having established Petri net 300, the incidence matrix is then constructed. Because the incidence matrix is relatively large, only a representative portion corresponding to its upper left quadrant is presented in FIG. 20. It should be understood that there are certain interesting features regarding the nucleotide cofactors: P57 (NADH), P58 (NAD), and P59 (CoA). For example, all of the forward paths go into P57 (from subreactions 4, 5, and 9) and all of its backward paths leave from P57 (10 other species within subreactions 4, 5, and 9). Conversely, all of the forward paths lead from P58 (from subreactions 4, 5, and 9) and all of its backward paths lead into P58 (again, interaction with other species within subreactions 4, 5, and 9). P59 is different because CoA has forward paths leading into it from subreactions 1 and 6, and its third forward path leads from CoA into Subreaction 5. CoA has backward paths to subreactions 1 and 6 and from subreaction 5. The evaluation of representation 300 includes performing routine 140 of FIGS. 8 and 9, as previously described, to determine a set of minimal cycles. Within the minimal cycle set, places and transitions that appear most and least often are considered and may then be examined in terms of their biochemical importance.

Next subreactions as detailed in FIGS. 12-19 are further considered. As depicted in FIG. 12, subreaction 1 is connected to subreaction 9 via a forward path and from subreaction 9 via a backward path. The citrate in Subreaction 1 is connected to, or may even be considered a part of, the combined subreactions 2/3 via a forward path and from subreactions 2/3 via a backward path. The citrate:CoA complex is connected to CoA, which in turn is connected to subreaction 5 in a forward path (and from a backward path) and to subreaction 6 in a backward path (and from a forward path). Note that CoA is included as a complex formation, similar to acetyl CoA. It is not drawn the same way because CoA is shared and appears in the network in several other subreactions. It should be appreciated that subreactions 2 and 3 were combined because the aconitase enzyme catalyzes two consecutive Krebs cycle reactions.

Subreactions 2/3 is depicted in FIG. 13, and are connected to the citrate of subreaction 1 via a backward path and from the same citrate via a forward path. The isocitrate of subreactions 2/3 is also a species of subreaction 4. Subreaction 4, as depicted in FIG. 14, shares isocitrate with subreactions 2/3. It also shares .alpha.-ketoglutarate with subreaction 5. Further complexity and system versatility is provided in subreaction 4 from its communication via cofactors NAD and NADH. Subreaction 5, as depicted in FIG. 15, is further described later in the text due to its orientation when extracted from FIG. 12. It should be appreciated that subreaction 5 shares .alpha.-ketoglutarate with subreaction 4 and it shares succinyl CoA with subreaction 6. Further, it couples to both subreaction 1 and the combined subreactions 2/3 and to subreaction 6 through P59 (CoA). It also couples to subreactions 4 and 9 through both NAD and NADH.

Subreaction 6, as depicted in FIG. 16, involves nucleotide cofactors guanosine diphosphate (GDP) and guanosine triphosphate (GTP). It shares succinyl CoA with subreaction 5 and succinate with subreaction 7. Communications through cofactor CoA have previously been described. Subreaction 7, as depicted in FIG. 17, involves nucleotide cofactors FAD and FADH. It shares succinate with subreaction 6 and fumarate with subreaction 8. Subreaction 8, as depicted in FIG. 18, shares fumarate with subreaction 7 and L-malate with subreaction 9. As depicted in FIG. 19, subreaction 9 completes the cycles with its sharing of oxaloacetate with subreaction 1. Its cross-couplings have previously been described. Accordingly, representation 300 corresponds to an extensive collection of circuits via forward and backward paths. Some admissible paths, however physically improbable, are more readily identified through this form of evaluation as compared to alternative methods of Krebs cycle analysis, and yet such paths may prove to be of interest from a biochemical and/or pharmaceutical point of view.

As previously indicated, FIG. 20 depicts a portion of the incidence matrix corresponding to representation 300. Specifically the matrix portion of FIG. 20 depicts entries for subreactions 1, 2/3 and 4. It should be appreciated that this depiction reveals a nearly block-banded matrix structure--the overlapping of the blocks being associated with adjacent subreactions--and the cross-couplings accomplished by the places P57, P58 and P59. Routine 140 was executed in software form using the representation 300 information to identify 73 two-cycles, while suppressing multiple edges. These same two-cycles can be recognized as all of the molecular reactions in the Krebs cycle representation 300, noting that each complex formation contains two two-cycles and each enzymatic reaction contains five two-cycles. The two-cycles may be counted by traversing the Krebs cycle backbone starting and ending at P56, which identities 43 two-cycles, and then adding an additional two-cycle for each of the 14 complex formations, and two additional two-cycles for each of the 8 enzyme reactions, for the total of 73.

The software of routine 140 next determined that the basis size is 15, which indicates that there are (2.sup.15-1) possibl