This paper presents a class of Stochastic Petri Nets with concurrent transition firings. It is assumed that transitions occur in steps and that for every step each enabled transition decides probabilistically whether it wants to participate in the step or not. Among the transitions which what to participate in a step, a maximal number is chosen to perform the firing step. The observable behavior is defined and equivalence relations are introduced. The equivalence relations extend the well-known trace and bisimulation equivalences for systems with step semantics to Stochastik Petri Nets with concurrent transition firing. It is shown that the equivalence notions form a lattice of interrelations.

This paper presents a class of Stochastic Petri Nets with concurrent transition firings. It is assumed that transitions occur in steps and that for every step each enabled transition decides probabilistically whether it wants to participate in the step or not. Among the transitions which what to participate in a step, a maximal number is chosen to perform the firing step. The observable behavior is defined and equivalence relations are introduced. The equivalence relations extend the well-known trace and bisimulation equivalences for systems with step semantics to Stochastik Petri Nets with concurrent transition firing. It is shown that the equivalence notions form a lattice of interrelations.

The paper is devoted to the investigation of behavioral equivalences of concurrent systems modeled by Petri nets with silent transitions. Basic τ-equivalences and back-forth τ-bisimulation equivalences known from the literature are supplemented by new ones, giving rise to complete set of equivalence notions in interleaving / true concurrency and linear / branching time semantcis. Their interrelations are examined for the general class of nets as well as for their subclasses of nets without siltent transitions and sequential nets (nets without concurrent transitions). In addition, the preservation of all the equivalence notions by refinements (allowing one to consider the systems to be modeled on a lower abstraction levels) is investigated.

The modeling and evaluation calculus FMC-QE, the Fundamental Modeling Concepts for Quanti-tative Evaluation [1], extends the Fundamental Modeling Concepts (FMC) for performance modeling and prediction. In this new methodology, the hierarchical service requests are in the main focus, because they are the origin of every service provisioning process. Similar to physics, these service requests are a tuple of value and unit, which enables hierarchical service request transformations at the hierarchical borders and therefore the hierarchical modeling. Through reducing the model complexity of the models by decomposing the system in different hierarchical views, the distinction between operational and control states and the calculation of the performance values on the assumption of the steady state, FMC-QE has a scalable applica-bility on complex systems. According to FMC, the system is modeled in a 3-dimensional hierarchical representation space, where system performance parameters are described in three arbitrarily fine-grained hierarchi-cal bipartite diagrams. The hierarchical service request structures are modeled in Entity Relationship Diagrams. The static server structures, divided into logical and real servers, are de-scribed as Block Diagrams. The dynamic behavior and the control structures are specified as Petri Nets, more precisely Colored Time Augmented Petri Nets. From the structures and pa-rameters of the performance model, a hierarchical set of equations is derived. The calculation of the performance values is done on the assumption of stationary processes and is based on fundamental laws of the performance analysis: Little's Law and the Forced Traffic Flow Law. Little's Law is used within the different hierarchical levels (horizontal) and the Forced Traffic Flow Law is the key to the dependencies among the hierarchical levels (vertical). This calculation is suitable for complex models and allows a fast (re-)calculation of different performance scenarios in order to support development and configuration decisions. Within the Research Group Zorn at the Hasso Plattner Institute, the work is embedded in a broader research in the development of FMC-QE. While this work is concentrated on the theoretical background, description and definition of the methodology as well as the extension and validation of the applicability, other topics are in the development of an FMC-QE modeling and evaluation tool and the usage of FMC-QE in the design of an adaptive transport layer in order to fulfill Quality of Service and Service Level Agreements in volatile service based environments. This thesis contains a state-of-the-art, the description of FMC-QE as well as extensions of FMC-QE in representative general models and case studies. In the state-of-the-art part of the thesis in chapter 2, an overview on existing Queueing Theory and Time Augmented Petri Net models and other quantitative modeling and evaluation languages and methodologies is given. Also other hierarchical quantitative modeling frameworks will be considered. The description of FMC-QE in chapter 3 consists of a summary of the foundations of FMC-QE, basic definitions, the graphical notations, the FMC-QE Calculus and the modeling of open queueing networks as an introductory example. The extensions of FMC-QE in chapter 4 consist of the integration of the summation method in order to support the handling of closed networks and the modeling of multiclass and semaphore scenarios. Furthermore, FMC-QE is compared to other performance modeling and evaluation approaches. In the case study part in chapter 5, proof-of-concept examples, like the modeling of a service based search portal, a service based SAP NetWeaver application and the Axis2 Web service framework will be provided. Finally, conclusions are given by a summary of contributions and an outlook on future work in chapter 6. [1] Werner Zorn. FMC-QE - A New Approach in Quantitative Modeling. In Hamid R. Arabnia, editor, Procee-dings of the International Conference on Modeling, Simulation and Visualization Methods (MSV 2007) within WorldComp ’07, pages 280 – 287, Las Vegas, NV, USA, June 2007. CSREA Press. ISBN 1-60132-029-9. / FMC-QE (Fundamental Modeling Concepts for Quantitative Evaluation [1]) ist eine auf FMC, den Fundamental Modeling Concepts, basierende Methodik zur Modellierung des Leistungsverhaltens von Systemen mit einem dazugehörenden Kalkül zur Erstellung von Leistungsvorhersagen wie Antwortzeiten und Durchsatz. In dieser neuen Methodik steht die Modellierung der hierarchischen Bedienanforderungen im Mittelpunkt, da sie der Ursprung aller dienstbasierenden Systeme sind. Wie in der Physik sind in FMC-QE die Bedienanforderungen Tupel aus Wert und Einheit, um Auftragstransformationen an Hierarchiegrenzen zu ermöglichen. Da die Komplexität durch eine Dekomposition in mehreren Sichten und in verschiedene hierarchische Schichten, die Unterscheidung von Operations- und Kontrollzuständen, sowie dazugehörige Berechungen unter Annahme der Stationarität reduziert wird, skaliert die Anwendbarkeit von FMC-QE auf komplexe Systeme. Gemäß FMC wird das zu modellierende System in einem 3-dimensionalen hierarchischen Beschreibungsraum dargestellt. Die quantitativen Kenngrößen der Systeme werden in drei beliebig frei-granularen hierarchischen bi-partiten Graphen beschrieben. Die hierarchische Struktur der Bedienanforderungen wird in Entity Relationship Diagrammen beschrieben. Die statischen Bedienerstrukturen, unterteilt in logische und reale Bediener, sind in Aufbaudiagrammen erläutert. Außerdem werden Petri Netze, genauer Farbige Zeit-behaftete Petri Netze, dazu verwendet, die dynamischen Abläufe, sowie die Kontrollflüsse im System zu beschreiben. Anschließend wird eine Menge von hierarchischen Gleichungen von der Struktur und den Parametern des Modells abgeleitet. Diese Gleichungen, die auf dem stationären Zustand des Systems beruhen, basieren auf den beiden Fundamental Gesetzen der Leistungsanalyse, dem Gesetz von Little und dem Verkehrsflussgesetz. Das Gesetz von Little definiert hierbei Beziehungen innerhalb einer hierarchischen Schicht (horizontal) und das Verkehrsflussgesetz wiederum Beziehungen zwischen hierarchischen Schichten (vertikal). Die Berechungen erlauben Leistungsvorhersagen für komplexe Systeme durch eine effiziente Berechnung von Leistungsgrößen für eine große Auswahl von System- und Lastkonfigurationen. Innerhalb der Forschungsgruppe von Prof. Dr.-Ing Werner Zorn am Hasso Plattner Institut an der Universität Potsdam ist die vorliegende Arbeit in einen größeren Forschungskontext im Bereich FMC-QE eingebettet. Während hier ein Fokus auf dem theoretischen Hintergrund, der Beschreibung und der Definition der Methodik als auch der Anwendbarkeit und Erweiterung gelegt wurde, sind andere Arbeiten auf dem Gebiet der Entwicklung einer Anwendung zur Modellierung und Evaluierung von Systemen mit FMC-QE bzw. der Verwendung von FMC-QE zur Entwicklung einer adaptiven Transportschicht zur Einhaltung von Dienstgüten (Quality of Service) und Dienstvereinbarungen (Service Level Agreements) in volatilen dienstbasierten Systemen beheimatet. Diese Arbeit umfasst einen Einblick in den Stand der Technik, die Beschreibung von FMC-QE sowie die Weiterentwicklung von FMC-QE in repräsentativen allgemeinen Modellen und Fallstudien. Das Kapitel 2: Stand der Technik gibt einen Überblick über die Warteschlangentheorie, Zeit-behaftete Petri Netze, weitere Leistungsbeschreibungs- und Leistungsvorhersagungstechniken sowie die Verwendung von Hierarchien in Leistungsbeschreibungstechniken. Die Beschreibung von FMC-QE in Kapitel 3 enthält die Erläuterung der Grundlagen von FMC-QE, die Beschreibung einiger Grundannahmen, der graphischen Notation, dem mathematischen Modell und einem erläuternden Beispiel. In Kapitel 4: Erweiterungen von FMC-QE wird die Behandlung weiterer allgemeiner Modelle, wie die Modellklasse von geschlossenen Netzen, Synchronisierung und Mehrklassen-Modelle beschrieben. Außerdem wird FMC-QE mit dem Stand der Technik verglichen. In Kapitel 5 werden Machbarkeitsstudien beschrieben. Schließlich werden in Kapitel 6 eine Zusammenfassung und ein Ausblick gegeben. [1] Werner Zorn. FMC-QE - A New Approach in Quantitative Modeling. In Hamid R. Arabnia, editor, Proceedings of the International Conference on Modeling, Simulation and Visualization Methods (MSV 2007) within WorldComp ’07, 280 – 287, Las Vegas, NV, USA, Juni 2007. CSREA Press. ISBN 1-60132-029-9.

Companies strive to improve their business processes in order to remain competitive. Process mining aims to infer meaningful insights from process-related data and attracted the attention of practitioners, tool-vendors, and researchers in recent years. Traditionally, event logs are assumed to describe the as-is situation. But this is not necessarily the case in environments where logging may be compromised due to manual logging. For example, hospital staff may need to manually enter information regarding the patient’s treatment. As a result, events or timestamps may be missing or incorrect. In this paper, we make use of process knowledge captured in process models, and provide a method to repair missing events in the logs. This way, we facilitate analysis of incomplete logs. We realize the repair by combining stochastic Petri nets, alignments, and Bayesian networks. We evaluate the results using both synthetic data and real event data from a Dutch hospital. / Unternehmen optimieren ihre Geschäftsprozesse laufend um im kompetitiven Umfeld zu bestehen. Das Ziel von Process Mining ist es, bedeutende Erkenntnisse aus prozessrelevanten Daten zu extrahieren. In den letzten Jahren sorgte Process Mining bei Experten, Werkzeugherstellern und Forschern zunehmend für Aufsehen. Traditionell wird dabei angenommen, dass Ereignisprotokolle die tatsächliche Ist-Situation widerspiegeln. Dies ist jedoch nicht unbedingt der Fall, wenn prozessrelevante Ereignisse manuell erfasst werden. Ein Beispiel hierfür findet sich im Krankenhaus, in dem das Personal Behandlungen meist manuell dokumentiert. Vergessene oder fehlerhafte Einträge in Ereignisprotokollen sind in solchen Fällen nicht auszuschließen. In diesem technischen Bericht wird eine Methode vorgestellt, die das Wissen aus Prozessmodellen und historischen Daten nutzt um fehlende Einträge in Ereignisprotokollen zu reparieren. Somit wird die Analyse unvollständiger Ereignisprotokolle erleichtert. Die Reparatur erfolgt mit einer Kombination aus stochastischen Petri Netzen, Alignments und Bayes'schen Netzen. Die Ergebnisse werden mit synthetischen Daten und echten Daten eines holländischen Krankenhauses evaluiert.

Organizations try to gain competitive advantages, and to increase customer satisfaction. To ensure the quality and efficiency of their business processes, they perform business process management. An important part of process management that happens on the daily operational level is process controlling. A prerequisite of controlling is process monitoring, i.e., keeping track of the performed activities in running process instances. Only by process monitoring can business analysts detect delays and react to deviations from the expected or guaranteed performance of a process instance. To enable monitoring, process events need to be collected from the process environment. When a business process is orchestrated by a process execution engine, monitoring is available for all orchestrated process activities. Many business processes, however, do not lend themselves to automatic orchestration, e.g., because of required freedom of action. This situation is often encountered in hospitals, where most business processes are manually enacted. Hence, in practice it is often inefficient or infeasible to document and monitor every process activity. Additionally, manual process execution and documentation is prone to errors, e.g., documentation of activities can be forgotten. Thus, organizations face the challenge of process events that occur, but are not observed by the monitoring environment. These unobserved process events can serve as basis for operational process decisions, even without exact knowledge of when they happened or when they will happen. An exemplary decision is whether to invest more resources to manage timely completion of a case, anticipating that the process end event will occur too late. This thesis offers means to reason about unobserved process events in a probabilistic way. We address decisive questions of process managers (e.g., "when will the case be finished?", or "when did we perform the activity that we forgot to document?") in this thesis. As main contribution, we introduce an advanced probabilistic model to business process management that is based on a stochastic variant of Petri nets. We present a holistic approach to use the model effectively along the business process lifecycle. Therefore, we provide techniques to discover such models from historical observations, to predict the termination time of processes, and to ensure quality by missing data management. We propose mechanisms to optimize configuration for monitoring and prediction, i.e., to offer guidance in selecting important activities to monitor. An implementation is provided as a proof of concept. For evaluation, we compare the accuracy of the approach with that of state-of-the-art approaches using real process data of a hospital. Additionally, we show its more general applicability in other domains by applying the approach on process data from logistics and finance. / Unternehmen versuchen Wettbewerbsvorteile zu gewinnen und die Kundenzufriedenheit zu erhöhen. Um die Qualität und die Effizienz ihrer Prozesse zu gewährleisten, wenden Unternehmen Geschäftsprozessmanagement an. Hierbei spielt die Prozesskontrolle im täglichen Betrieb eine wichtige Rolle. Prozesskontrolle wird durch Prozessmonitoring ermöglicht, d.h. durch die Überwachung des Prozessfortschritts laufender Prozessinstanzen. So können Verzögerungen entdeckt und es kann entsprechend reagiert werden, um Prozesse wie erwartet und termingerecht beenden zu können. Um Prozessmonitoring zu ermöglichen, müssen prozessrelevante Ereignisse aus der Prozessumgebung gesammelt und ausgewertet werden. Sofern eine Prozessausführungsengine die Orchestrierung von Geschäftsprozessen übernimmt, kann jede Prozessaktivität überwacht werden. Aber viele Geschäftsprozesse eignen sich nicht für automatisierte Orchestrierung, da sie z.B. besonders viel Handlungsfreiheit erfordern. Dies ist in Krankenhäusern der Fall, in denen Geschäftsprozesse oft manuell durchgeführt werden. Daher ist es meist umständlich oder unmöglich, jeden Prozessfortschritt zu erfassen. Zudem ist händische Prozessausführung und -dokumentation fehleranfällig, so wird z.B. manchmal vergessen zu dokumentieren. Eine Herausforderung für Unternehmen ist, dass manche Prozessereignisse nicht im Prozessmonitoring erfasst werden. Solch unbeobachtete Prozessereignisse können jedoch als Entscheidungsgrundlage dienen, selbst wenn kein exaktes Wissen über den Zeitpunkt ihres Auftretens vorliegt. Zum Beispiel ist bei der Prozesskontrolle zu entscheiden, ob zusätzliche Ressourcen eingesetzt werden sollen, wenn eine Verspätung angenommen wird. Diese Arbeit stellt einen probabilistischen Ansatz für den Umgang mit unbeobachteten Prozessereignissen vor. Dabei werden entscheidende Fragen von Prozessmanagern beantwortet (z.B. "Wann werden wir den Fall beenden?", oder "Wann wurde die Aktivität ausgeführt, die nicht dokumentiert wurde?"). Der Hauptbeitrag der Arbeit ist die Einführung eines erweiterten probabilistischen Modells ins Geschäftsprozessmanagement, das auf stochastischen Petri Netzen basiert. Dabei wird ein ganzheitlicher Ansatz zur Unterstützung der einzelnen Phasen des Geschäftsprozesslebenszyklus verfolgt. Es werden Techniken zum Lernen des probabilistischen Modells, zum Vorhersagen des Zeitpunkts des Prozessendes, zum Qualitätsmanagement von Dokumentationen durch Erkennung fehlender Einträge, und zur Optimierung von Monitoringkonfigurationen bereitgestellt. Letztere dient zur Auswahl von relevanten Stellen im Prozess, die beobachtet werden sollten. Diese Techniken wurden in einer quelloffenen prototypischen Anwendung implementiert. Zur Evaluierung wird der Ansatz mit existierenden Alternativen an echten Prozessdaten eines Krankenhauses gemessen. Die generelle Anwendbarkeit in weiteren Domänen wird examplarisch an Prozessdaten aus der Logistik und dem Finanzwesen gezeigt.

The paper is devoted to the investigation of behavioral equivalences of concurrent systems modeled by Petri nets with silent transitions. Basic τ-equivalences and back-forth τ-bisimulation equivalences known from the literature are supplemented by new ones, giving rise to complete set of equivalence notions in interleaving / true concurrency and linear / branching time semantcis. Their interrelations are examined for the general class of nets as well as for their subclasses of nets without siltent transitions and sequential nets (nets without concurrent transitions). In addition, the preservation of all the equivalence notions by refinements (allowing one to consider the systems to be modeled on a lower abstraction levels) is investigated.

Die lebenden Organismen sind für eine wissenschaftliche Analyse zu kompliziert, wenn man sie als Ganzes und in ihrer vollen Komplexität betrachtet. Die vorliegende Arbeit behandelt die topologischen Eigenschaften von zwei wichtigen Teilen der lebenden Organismen: die metabolischen und die regulatorischen Systeme. Topolgische Eigenschaften sind solche, die durch die Netwerkstruktur bedingt werden. Ein Signalsystem ist eine spezielle Art von regulatorischem System. Zwischen den metabolischen und Signalnetzen gibt es wichtige Unterschiede, die ihre Behandlung in unterschiedlicher Weise erfordert. In der metabolischen Pfadanalyse ist das Konzept der elementaren Flussmoden bereits als ein passendes Instrument für die Charakterisierung der einfachsten essentiellen Wege in biochemischen Systemen etabliert. Wir untersuchen die Eigenschaften und Vorteile dieses Konzepts in einigen besonderen Fällen. Zuerst untersuchen wir die vielfach vorkommenden Enzyme mit niedriger Spezifität (z.B. Nukleosiddiphosphokinase, Uridinkinase, Transketolase, Transaldolase). Sie können parallel verschiedene Substrate und Produkte umwandeln. Auch die Enzym-Mechanismen sind vielfältig, wie wir mit dem Reaktionsschema für bifunktionelle Enzyme veranschaulichen. Wir betrachten dabei nur den Fall, dass ein bestimmtes aktives Zentrum mehrere Reaktionen katalysiert. Der Fall, dass das studierte Enzym mehrere solche aktiven Zentren hat, kann in den Fall mehrerer Enzyme transformiert werden, die nur ein aktives Zentrum haben. Wenn eine Krankheit das Ausgangsenzym ändert, werden dann in der Analyse auch alle ersetzenden Enzyme geändert. Es gibt zwei unterschiedliche Betrachtungsweisen, um multifunktionelle Enzyme zu beschreiben. Zum einen kann man die Gesamtreaktionen betrachten und zum anderen die elementaren Reaktionsschritte (Hemireaktionen, Halbreaktionen). Für Enzyme mit zwei oder mehr Funktionen ist es wichtig, nur linear unabhängige Funktionen zu betrachten, weil sonst zyklische elementare Moden auftreten würden, die keine Nettoumwandlung durchführen. Jedoch ist die Wahl der linear unabhängigen Funktionen nicht a priori eindeutig. Wir stellen eine Methode für das Treffen dieser Wahl vor, indem wir die konvexe Basis des Hemireaktions-Systems betrachten. Eine formale Anwendung des Algorithmus für das Berechnen der elementaren Flussmoden (Routen) erbringt das Resultat, dass die Zahl solcher Moden manchmal vom Niveau der Beschreibung abhängt, wenn einige Reaktionen reversibel sind und die Produkte der multifunktionellen Enzyme externe Metabolite sind, oder einige multifunktionelle Enzyme zum Teil die gleichen Stoffwechselprodukte umwandeln. Jedoch kann dieses Problem durch eine geeignete Deutung der Definition der elementaren Moden und die korrekte Wahl der unabhängigen Funktionen der Multifunktionsenzyme gelöst werden. Die Analyse wird durch einige kleinere Beispiele und ein größeres biochemisches Beispiel veranschaulicht, das aus dem Nukleotidmetabolismus stammt und die zwei Arten der Beschreibung für Nukleosiddiphosphokinase und Adenylatekinase vergleicht. Der Nukleotidmetabolismus spielt eine wichtige Rolle in lebenden Organismen und ist gegenüber allen möglichen Störungen in seiner internen Balance sehr empfindlich. Gefährliche Krankheiten können auftreten, wenn einige Enzyme nicht richtig funktionieren. Mit Hilfe des Konzeptes des elementaren Flussmodus erklären wir das Auftreten und den Schweregrad von Krankheiten, die auf Enzymdefizienzen basieren. Wenn ein Enzym vollständig gehemmt wird, werden einige metabolische Wege blockiert. Wenn jedoch einige alternative Wege noch bestehen, ist die Krankheit weniger gefährlich. Unsere Analyse ist darauf gerichtet, alternative Wege, wesentliche Enzyme und solche Enzyme, die immer zusammenarbeiten zu finden. Der letzte Begriff ist auch als "Enzyme subset" bekannt und stellt einen intermediären Schritt im Algorithmus zur Berechnung der elementaren Flussmoden dar. Wir diskutieren bereits bekannte und bisher nur hypothetische Mechanismen einiger Krankheiten (proliferative Krankheiten, Immundefizienzen), die auf Störungen des Nukleotidmetabolismus oder seiner Ausbeutung durch Viren und Parasiten beruhen. Die meisten Strategien, die für das Bekämpfen solcher Krankheiten eingesetzt werden, basieren auf der Unterbrechung des Nukleotidmetabolismus an bestimmten Stellen. Diese Strategien können aber auch zur Akkumulation toxischer Stoffe führen und dadurch Nebenwirkungen hervorrufen. Deswegen hilft ein besseres Verständnis dieses Systems, wirkungsvollere Medikamente zu entwickeln, und eine gute strukturelle Analyse kann viele experimentelle Bemühungen ersparen. Konzepte aus der Theorie der Petri-Netze liefern zusätzliche Werkzeuge für das Modellieren metabolischer Netzwerke. In Kapitel 4 werden die ähnlichkeiten zwischen einigen Konzepten in der traditionellen biochemischen Modellierung und analogen Konzepten aus der Petri-Netztheorie besprochen. Zum Beispiel entspricht die stochiometrische Matrix eines metabolischen Netzwerkes der Inzidenzmatrix des Petri-Netzes. Die Flussmoden und die Erhaltungs-Relationen haben die T-Invarianten beziehungsweise P-Invarianten als Gegenstücke. Wir decken die biologische Bedeutung einiger weiterer Begriffe aus der Theorie der Petri-Netze auf, nämlich "traps", "{siphons", "deadlocks" und "Lebendigkeit". Wir konzentrieren uns auf der topologischen Analyse anstatt auf die Analyse des dynamischen Verhaltens. Die geeignete Behandlung der externen Stoffwechselprodukte wird ebenfalls besprochen. Zur Illustration werden einige einfache theoretische Beispiele vorgestellt. Außerdem werden einige Petri-Netze präsentiert, die konkreten biochemischen Netzen entsprechen, um unsere Resultate zu belegen. Zum Beispiel wird die Rolle der Triosephosphatisomerase (TPI) im Metabolismus von Trypanosoma brucei ausgewertet, indem "traps" und "siphons" ermittelt werden. Alle behandelten Eigenschaften von Petri-Netzen werden anhand eines Systems illustriert, das aus dem Nukleotidmetabolismus stammt. Während viele Bemühungen für das Zerlegen metabolischer Systeme, (elementare Flußmoden, extreme Wege) erfolgt sind, sind bisher unseres Wissens keine Versuche in dieser Richtung für Signalübertragungssysteme unternommen worden. Eine spezielle Eigenschaft von Signalnetzwerken in lebenden Zellen ist, dass Aktivierungen, Hemmungen und biochemische Reaktionen normalerweise gleichzeitig anwesend sind. Selbst wenn sie nicht Reaktionen enthalten, machen Mehrfach-Aktivierungen oder Mehrfach-Hemmungen die Netzwerke in hohem Grade verzweigt. Es ist eine schwierige und sehr zeitraubende Aufgabe, alle Faktoren, die einen Einfluss auf ein gegebenes Ziel haben, ohne eine automatische Methode zu ermitteln. Bereits in Kapitel 1 heben wir die ähnlichkeiten und Unterschiede zwischen den metabolischen und Signal-Netzwerken hervor. In Kapitel 5 errichten wir einen Rahmen und präsentieren einen Algorithmus für die Zerlegung von Signalnetzwerken in kleinere Einheiten, die einfacher zu studieren und zu verstehen sind. Zwei Fälle werden untersucht: ein einfacheres, wenn nur monomolekulare Aktivierungen oder Reaktionen anwesend sind, und ein komplizierterer Fall, wenn die Aktivierungen und die Reaktionen multimolekular sein können. Ihre Beschreibung erfordert unterschiedliche Methoden: klassische Graphen bzw. Petrinetze. Wir besprechen die Probleme, die in unserem Modell wegen des Vorhandenseins von Hemmungen oder von unbekannten Effekten im Netz auftreten. Der vorgeschlagene Algorithmus ermittelt die Faktoren, die zusammenwirken und die Zielsubstanzen, die auf dem gleichen Weg beeinflusst werden. Die Zyklen, die im System auftreten, und mögliche fehlende Reaktionen werden ebenfalls ermittelt . Theoretische Beispiele veranschaulichen unsere Resultate. Anhand der T-Zell-Antigen-Rezeptor-Signalkaskade zeigen wir, wie die Methoden in realen Systemen angewendet werden können. / The living organisms are too complex when considering them as a whole. The present thesis deals with the topological properties of two important parts of living organisms: the metabolic and the regulatory systems. The topological properties are those features that are determined by the network structure. A classification in metabolic and regulatory systems is often used. A signalling system is a special kind of regulatory system. Between metabolic and signalling networks, there are important differences that impose their treatment in different ways. In metabolic pathway analysis, the elementary flux mode concept is already established as a proper tool for identifying the smallest essential routes in biochemical systems. We examine its features and advantages in some particular cases. Firstly, many enzymes operate with low specificity (e.g. nucleoside diphosphokinase, uridine kinase, transketolase, transaldolase), so that various substrates and products can be converted. Also the enzymatic mechanisms are diverse, as we have illustrated with reaction schemes for bifunctional enzymes. Therefore, there are two different approaches to describe multifunctional enzymes (We considered only the case when a certain active site hosts several reactions. The case when the studied enzyme has several such active sites can be transformed into that of several enzymes having only one active site. If a disease alters the initial enzyme, also all substituting enzymes are altered.): in terms of overall reactions and in terms of reactions steps (hemi-reactions, half-reactions). For enzymes with two or more functions, it is important to consider only linearly independent functions, because otherwise cyclic elementary modes would occur which do not perform any net transformation. However, the choice of linearly independent functions is not a priori unique. In Chapter 2, we give a method for making this choice unique by considering the convex basis of the hemi-reactions system. The set of linearly independent functions provided by our algorithm coincides, in the case of transketolase in pentose phosphate pathway, with the set of linearly independent functions mentioned in literature. A formal application of the algorithm for computing elementary flux modes (pathways) yields the result that the number of such modes sometimes depends on the level of description if some reactions are reversible and the products of the multifunctional enzymes are external metabolites or some multifunctional enzymes partly share the same metabolites. However, this problem can be solved by appropriate interpretation of the definition of elementary modes and the correct choice of independent functions of multifunctional enzymes. The analysis is illustrated by a biochemical example taken from nucleotide metabolism, comparing the two ways of description for nucleoside diphosphokinase and adenylate kinase, and by several smaller examples. The nucleotide metabolism plays an important role in living organisms and is very sensitive to any perturbations in its internal balance. Dangerous diseases may occur if some enzymes do not work properly. With the help of elementary flux mode concept, we explain the occurrence and severity of diseases based on enzyme deficiencies. If an enzyme is completely inhibited, some metabolic routes are blocked. If, however, some alternative routes still exist, the disease is less dangerous. In Chapter 3, we focus on finding alternative routes, essential enzymes and enzymes operating together. The latter notion is also known as ,,enzyme subset`` and represents an intermediary step in calculating the elementary flux modes. The known or hypothesised mechanisms of several disorders, occurred due to the malfunctioning of nucleotide metabolism (proliferative diseases, immunodeficiency diseases) or due to its hijacking by viruses and parasites, are given. Most strategies adopted for curing such diseases are based on nucleotide metabolism interruption. Therefore, a better understanding of this system helps developing more effective drugs and a good structural analysis can spare many experimental efforts. Petri net concepts provide additional tools for the modelling of metabolic networks. In Chapter 4, the similarities between the counterparts in traditional biochemical modelling and Petri net theory are discussed. For example, the stoichiometry matrix of a metabolic network corresponds to the incidence matrix of the Petri net. The flux modes and conservation relations have the T-invariants, respectively, P-invariants as counterparts. We reveal the biological meaning of some notions specific to the Petri net framework (traps, siphons, deadlocks, liveness). We focus on the topological analysis rather than on the analysis of the dynamic behaviour. The treatment of external metabolites is discussed. Some simple theoretical examples are presented for illustration. Also the Petri nets corresponding to some biochemical networks are built to support our results. For example, the role of triose phosphate isomerase (TPI) in Trypanosoma brucei metabolism is evaluated by detecting siphons and traps. All Petri net properties treated in above-mentioned chapter (4) are exemplified on a system extracted from nucleotide metabolism. While for decomposing metabolic systems, many efforts have been done (elementary flux modes, convex basis, extreme pathways), for signalling maps, as far as we know, no attempt in this direction has been made. A special characteristic of signalling networks is that activations, inhibitions, and biochemical reactions are normally present in parallel. Even if they do not contain reactions, multi-part activations or inhibitions make them highly branched. To detect all factors that have an influence on a given target, without using an automatic method, is a difficult and very time-consuming effort. Already in Chapter 1 (Backgrounds), we highlight the similarities and differences between metabolic and signalling networks. In Chapter 5, we build a framework and algorithm for decomposing signalling networks in smaller units, which are easier to study and understand. Two cases are investigated: a simpler one, when only monomolecular activations or reactions are present, and a more complex case, when the activations and reactions can be multimolecular. Their description requires different instruments: classical graphs and Petri nets, respectively. We discuss the problems that occur in our model due to the presence of some inhibitions or unknown effects in the network. The algorithm that we propose detects the factors that are acting together and the targets that are affected on the same route. The cycles that occur in the system are also highlighted. We point out possible missing reactions. Theoretical examples illustrate out findings. Using the T cell antigen-receptor signalling cascade, we show how it can be applied to real systems.

Hintergrund und Zielsetzung: DMD ist die häufigste Form der Muskeldystrophie im Kindesalter und bis heute unheilbar. Sie wird durch das Fehlen des Proteins Dystrophin verursacht, welches verschiedene Signaltransduktionswege beeinflusst. Das Anliegen der Arbeit ist die Untersuchung und Modulation von Signaltransduktionswegen, die als alternative Therapiestrategie den Verlust von Dystrophin kompensieren könnten. Experimentelle Strategie: Für die Charakterisierung von Dystrophin nachgeschalteten Prozessen wurden mRNA-Expressionsanalysen in Muskelgeweben von DMD-Patienten und einem DMD-Brüderpaar mit einem infrafamiliär unterschiedlichen Verlauf der DMD durchgeführt. Aus diesen Expressionsdaten wurde erstmalig ein Petri-Netz entwickelt, welches Dystrophin mit in diesem Zusammenhang bisher unbekannten Signaltransduktionswegen verknüpft. Das Petri-Netz wurde auf Netzwerkintegrität und –verhalten mittels Invarianten- (INA) und theoretischen Knockout- (Mauritius Maps) Analysen untersucht. Durch beide Methoden läßt sich der maßgebliche Teilsignalweg bestimmen. In diesem Signalweg wurden die Proteinaktivität und die Genexpression durch siRNA, Vektor-DNA und chemische Substanzen in humanen SkMCs moduliert. Anschließend wurden die Proliferation und die Vitalität der Zellen sowie auch die Expression auf mRNA- und Protein-Niveau untersucht. Ergebnisse: RAP2B und CSNK1A1 waren in dem DMD-Brüderpaar differentiell exprimiert und konnten erstmalig in einem neuen, komplexen Signalweg in Zusammenhang mit Dystrophin nachgeschalteten Prozessen dargestellt werden. Mittelpunkt dieses Signalweges ist die De- und Aktivierung des Transkriptionsfaktors NFATc. Seine Zielgene umfassen neben anderen den negativen Proliferationsfaktor p21, das Dystrophin homologe UTRN und den Differenzierungsfaktor MYF5. Folglich würde ein Anstieg von UTRN eine unerwünschte Reduktion der Proliferationsrate von Myoblasten implizieren. Letzteres konnte bereits nachgewiesen werden und stellte das Motiv für weitere Studien dar. Jedoch zeigten siRNA- und Vektor-DNA-Experimente, daß NFATc nicht der ausschlaggebende Faktor für diese Zielgene ist. Die Substanzen Deflazacort (DFZ) und Cyclosporin A (CsA) wurden dagegen beschrieben, die Aktivierung von NFATc zu beeinflussen. Die Ergebnisse zeigten, daß beide Substanzen die Proliferation von Myoblasten erhöhen können. Die gleichzeitige Applikation von DFZ und CsA führte zu einem Anstieg der UTRN-Expression. Schlußfolgerung: Die Modulation der Proliferation und UTRN-Expression ist unabhängig von einander möglich. Entsprechend der Grundidee der Arbeit zeichnet sich eine neue Therapiestrategie ab, welche Dystrophin nachgeschaltete Prozesse einbezieht. / Background and aim: DMD is the most common muscular dystrophy in childhood and incurable to date. It is caused by the absence of dystrophin, what influences several signal transduction pathways. The thesis is interested in the investigation and modulation of signal transduction pathways that may compensate the lack of dystrophin as an alternative therapy strategy. Experimental strategy: To study Dystrophin downstream pathways the mRNA expression of DMD patients and two DMD siblings with an intra-familially different course of DMD were analysed in muscle tissue. On the basis of these expression data a Petri net was first developed implicating signal transduction pathways and Dystrophin downstream cascades. Invariant (INA) and theoretical knockout (Mauritius Maps) analyses were applied for studying network integrity and behaviour. Both methods provide information about the most relevant part of the network. In this part modulation of protein activity and of gene expression using siRNA, vector-DNA, and chemical substances were performed on human SkMCs. Subsequently, the cells were studied by proliferation and vitality tests as well as expression analyses at mRNA and protein level. Results: RAP2B and CSNK1A1 were differently expressed in two DMD siblings, and first are part of a signal transduction pathway implicating Dystrophin downstream processes. The central point of this pathway is the de- and activation of the transcription factor NFATc. Its target genes are, among others, the negative proliferation factor p21, the Dystrophin homologue UTRN, and the differentiation factor MYF5. Consequently, an increase in UTRN implicates an undesirably reduced myoblast proliferation rate. Latter was found in DMD patients and was target for further studies. But, siRNA and vector DNA experiments showed that NFATc is not the decisive factor for the target genes. Deflazacort and cyclosporin A are known to influence the activation of NFATc. The results first showed that both substances do induce myoblast proliferation. The use of deflazacort in combination with cyclosporin A resulted in an increase of UTRN expression. Conclusion: The modulation of proliferation and UTRN-expression independently of each other is possible. According to the basic idea of this study, a new therapeutic strategy becomes apparent, which considers Dystrophin downstream processes.