STEPP – Search Tool for Exploration of Petri net Paths: A New Tool for Petri Net-Based Path Analysis in Biochemical Networks - Biological Petri Nets - page 121

SuSy rev, respectively, which reflects the biological behaviour correctly. Thus, this path search can also
be used to validate Petri net models of biochemical networks.

CONCLUSIONS

We have introduced a new tool to search for paths with constraints in biochemical networks. We
have explained the algorithm consisting of an exhaustive path search and the application of additional
constraints defined by a special language. This language is described in the paper using various examples.
We provided a case study for the sucrose-to-starch breakdown in the potato tuber to show the correctness
and usefulness of the tool. Biological aspects related to special pathways of our case study are also
discussed. The presented tool has been designed for application in path searches in biochemical systems
to find alternative paths in the system. We have implemented a Web interface, which includes a Graphical
User Interface and supports the definition of constraints. So far, there exists an interface to Petri nets,
which can be extended easily to other formats. In order to enhance the performance we will implement
an improved algorithm, which considers constraints during the path search.

ACKNOWLEDGEMENTS

We would like to thank the anonymous referee for helpful advices.This work was partly supported by
the Federal Ministry of Education and Research of Germany (BMBF), BCB project 0312705D.

REFERENCES

• Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2001). Introduction to algorithms. The MIT Press, Cambridge,

Masschusetts, London, England.

• Heiner, M., Koch, I. and Will, J. (2004). Model validation of biological pathways using Petri nets - demonstrated for

apoptosis. Biosystems 75 , 15-28.

• Heiner, M. and Koch, I. (2004). Petri Net Based Model Validation in Systems Biology Proc. IACATPN, Springer Verlag,

Berlin, LNCS 3099, 216-237.

• Hofestadt, R. (1994). A Petri net Application of Metabolic Processes. J. System Analysis, Modelling, and Simulation 16 ,

113-122.

• Hofestadt, R. and Thelen, S. (1998). Quantitative Modelling of Biochemical Networks. In Silico Biol. 1, 0006.

• Kanehisa, M. and Goto, S. (2000). KEGG: Kyoto Encyclopedia of Genes and Genomes. Nucleic Acids Res. 28 , 27-30.

• Koch, I., Junker, B. H. and Heiner, M. (2004). Application of Petri net theory for modelling and validation of the sucrose

breakdown pathway in the potato tuber. Bioinformatics, Advance Access, Nov. 16.

• Matsuno, H., Fujita, S., Doi, A., Nagasaki, M. and Miyano, S. (2003). Towards Pathway Modelling and Simulation. In:

Applications and Theory of Petri Nets 2003, Proc. IACATPN, van der Aalst, W. and Best, E. (eds.), Springer Verlag,

Berlin, LNCS 2679, 3-22.
• Murata, T. (1989). Petri nets: properties, analysis, and applications. Proc. of the IEEE 77 , 541-580.
• Reddy, V. N., Mavrovouniotis, M. L. and Liebman, M. N.(1993). Petri Net Representation in Metabolic Pathways. Proc.
Int. Conf. Intell. Syst. Mol. Biol. 1 , 328-336.
• Reddy, V. N., Mavrovouniotis, M. L. and Liebman, M. N.(1996). Qualitative analysis of biochemical reaction systems.
Comput. Biol. Med. 26 , 9-24.

• Starke, P. H. and Roch, S. (1999). Manual: INA - The Intergrated Net Analyzer, http://www.informatik.hu-

berlin.de/˜starke/ina.html , Humboldt University, Berlin.

• Voss, K., Heiner, M. and Koch, I. (2003). Steady State Analysis of metabolic pathways using Petri nets. In Silico Biol. 3 ,

0031.