Biology Reference
In-Depth Information
Fig. 1. Path search from vertex A to vertex I in a graph. When reaching vertex I, the corresponding path will be read out.
The second step is the path search. For a correct and fast implementation we perform an exhaustive
search by traversing our graph structure. Starting with the start vertex we visit recursively all vertices
until the end vertex is reached, see Fig. 1. In this way a vertex can be visited more than once. This
ensures us to find all paths, but leads to an exponential running time in the worst-case. Despite the
fact that the running time for our case study is still acceptable (much less than a second), an improved
implementation is under development.
Because of the density and the large amount of reversible reactions in biochemical networks, the
exhaustive search, as introduced above, results generally in a huge amount of possible loop-free paths;
see the result section for examples. Using dedicated constraints the search becomes more purposeful in
order to get only the paths of interest.
The Constraint Concept
The definition of a constraint language is the main contribution of the approach presented in this paper.
The use of constraints gives us the possibility to characterise biological requirements in metabolic paths
search. Constraints could be used to model situations such as loss-of-function mutations of enzymes or
absence of substrates, and to perform specific path searches fulfilling these requirements. Furthermore, a
concentration on special paths of interest, e.g., paths through specific vertices, paths with a given length,
etc., should be supported.
A basic objective of our constraint definition language is high user acceptance by an intuitive, but
powerful user interface. To reach these aims, we reduced the language elements to a small number of
basic constraints (such as “should include a specific vertex”, “should be smaller than ten vertices”, etc).
Starting from these simple atomic constraints, more powerful composite constraints of any complexity can
be constructed using logical operators as AND, OR, and NOT. In the following, we explain our constraint
definition language. Constraints are defined as Strings ("") using brackets and logical operators.
Brackets:
{}
stand for the specification of constraints, e.g., i
{
AT P
}
,
and ( ),
[]
for logically combined constraints, e.g.,
[
(
i
{
AT P
}
)
|
(
i
{
ADP
}
)
]
.
These two types of brackets are introduced to improve the readability.
