Biology Reference
In-Depth Information
of special enzymes, are more likely to be comprehensible with the knowledge and deep understanding
of alternative paths. The next step would be to answer the question, under which conditions which paths
could be active.
Methods for path searches in graphs are well-established techniques in computer science. There exist
several algorithms to search for paths in undirected and directed arbitrary graphs, such as breadth-first
search (BFS) and depth-first search (DFS), and other specialised variants as the Bellman-Ford algorithm,
the Dijkstra algorithm, the Floyd-Warshall algorithm, and others; for an overview see Cormen
et al.,
2001. The direct application of these methods to biochemical networks could result in an enormous
amount of possible paths. Typically, the complete amount of paths is not necessary. Even worse, its
manual management is hardly possible. To reduce the solution set to the in general much smaller subset
of interest, we suggest the definition of special constraints, which have to be fulfilled by all paths in the
solution set.
Existing Petri net tools, e.g., INA [Starke and Roch, 1999], search for paths in the reachability graph,
i.e. for paths from one state to another state of the system, to answer the question whether a special
system state is reachable from another given system state. In KEGG [Kanehisa and Goto, 2000] and other
network databases it can be searched for special pathways, but not for all paths between two arbitrary
chemical compounds, satisfying additional constraints.
For these reasons, we have implemented a stand-alone basic tool for path search between two arbitrary
vertices in the net using constraints in order to get those paths we are interested in. In this paper we
explain the search algorithm and the language definition to formulate constraints. In the result section
we show how to use the language for constraint definition and give several examples for specific path
searches for the sucrose-to starch breakdown in the potato tuber.
METHODS
A classical place/transition Petri net (P/T net) forms the basis for our considerations. The places
represent the metabolites or chemical compounds, while transitions stand for enzymes catalysing the
underlying chemical reactions. For further information on Petri nets and their application to biochemical
systems see Murata, 1982, or Heiner and Koch, 2004, respectively.
For the path search we specify two arbitrary vertices, which can be transitions or places, as start vertex
and as end vertex, for which all possible paths in between have to be computed. A path of length
k
is defined as a sequence of
k
vertices in the graph, which are connected by edges. The vertices are
enumerated along the path, beginning with the start vertex as number 1. The position of a vertex in a path
corresponds to the vertex number. No vertex occurs twice in a path, which is necessary to avoid loops.
Forward and backward reactions are considered to be the same vertex to circumvent loops between them.
The method consists of two main parts: firstly, the exhaustive path search by traversing the graph
representing our Petri net, secondly, the reduction of the paths, resulting from the exhaustive search by
evaluation of constraints.
Exhaustive Path Search
A first step is the creation of a special graph structure, which serves as basis for a fast path search.
Petri nets are converted using BFS as a fast algorithm to visit all vertices, which takes
O
(
V
+
E
)
time,
whereby
V
is the number of vertices and
E
the number of edges.
