## 5 Dependent Shrink Algorithm and Case Study
### Dependent Shrink Algorithm
Particularly for signaling pathways, owing to their complex structure, including protein formations and enzyme reactions, computational methods are essential to estimate as much reaction data as possible from biologically-valid data. In this paper, we presented an algorithm to shrink the transitions in a timed Petri net model into a smaller number of transitions based on their dependency with respect to the firing frequency and, equally, their amount of delay. Figure 16: Shrink example of Petri net model and its equivalence classes. (**a**) transitions surrounded by a line satisfies a dependent relation; (**b**) transformed net by applying dependent shrink; (**c**) equivalence classes. Figure 17: Example structure that cannot be shrunk into a single transition. We have first introduced a new concept, called the dependency relation, over a set of transitions of a Petri net model representing a signaling pathway, which is in fact an equivalence relation over transitions. Through a structural analysis, we obtained several properties, one important result of which is that shrinking a connected subnet, induced by transitions with a dependency relation, into a transition never affects other parts of a Petri net. Based on these results, we designed an Algorithm 1 with time complexity \(O(|P||E|)\) to reduce the Petri net size by applying a dependent shrink process for two elementary structures, i.e., a \"single-input and single-output structure\" and a \"conflict structure\", in order to efficiently find a transition set with a dependency relation. A case study was conducted by applying our algorithm to the signaling pathway Petri net model of IL-3, and as a result, IL-3 finally becomes a single transition, which means that all reaction speeds of IL-3 are dependent on one another and that measuring one reaction speed can help in deriving all other speeds. Our proposed method can be applied not only to signaling pathways, but also to other biological pathways in which retention-freeness holds, for example to metabolic pathways. If, in a timed Petri net model constructed from such a biological pathway, there exists a transition violating retention-freeness, then some discrepancy should happen in the biological pathway, i.e., missing interaction and/or extra interaction, which will be caused by mutations or alternations to the pathway. Such a biological inconsistency is expected to be found with our technique. We have also pointed out that there may remain some subnets with a dependency relation in the resultant net after applying Algorithm 1 because only a dependent shrink of a \"single-input and single-output structure\" and a \"conflict structure\" are adopted. We indicated that this can be resolved by solving a series of linear equations for such a subnet without taking up too much computation time because the size of the subnet should be much smaller compared with the original net. As future work, we are planning to: (1) develop a method to find such a subnet that includes only the places possessing a single-output and multiple-input transitions with a dependency relation; (2) design an algorithm to find the transitions with a dependency relation from the solution of a series of the prior mentioned linear equations; (3) extend our method to a stochastic Petri net by taking into account probabilistic firing delay times.