Annegret K Wagler
email: annegret.wagler@univ-bpclermont.frwegener@isima.fr

Jan-Thierry Wegener

Preprocessing for Network Reconstruction: Feasibility Test and Handling Infeasibility

The context of this work is the reconstruction of Petri net models for biological systems from experimental data. Such methods aim at generating all network alternatives tting the given data. For a successful reconstruction, the data need to satisfy two properties: reproducibility and monotonicity. In this paper, we focus on a necessary preprocessing step for a recent reconstruction approach. We test the data for reproducibility, provide a feasibility test to detect cases where the reconstruction from the given data may fail, and provide a strategy to cope with the infeasible cases. After having performed the preprocessing step, it is guaranteed that the (given or modied) data are appropriate as input for the main reconstruction algorithm.

Introduction

The aim of systems biology is to analyze and understand dierent phenomena as, e.g., responses of cells to environmental changes, host-pathogen interactions, or eects of gene defects. To gain the required insight into the underlying biological systems, experiments are performed and the resulting experimental data have to be interpreted in terms of models that reect the observed phenomena. Depending on the biological aim and the type and quality of the available data, dierent types of mathematical models are used and corresponding methods for their reconstruction have been developed. We focus on Petri nets, a framework which turned out to coherently model both static interactions in terms of networks and dynamic processes in terms of state changes [START_REF] Chen | Quantitative Petri net model fo gene regulated metabolic networks in the cell[END_REF][START_REF] Koch | Petri nets[END_REF][START_REF] Marwan | Petri nets as a framework for the reconstruction and analysis of signal transduction pathways and regulatory networks[END_REF][START_REF] Pinney | Petri net representations in systems biology[END_REF].

In fact, a (standard) network P = (P, T, A, w) reects the involved system components by places p ∈ P and their interactions by transitions t ∈ T , the arcs in A ⊂ (P × T ) ∪ (T × P ) link places and transitions, and the arc weights w : A → N reect stoichiometric coecients of the corresponding reactions. Moreover, each place p ∈ P can be marked with an integral number x p of tokens dening a system state x ∈ Z |P | + . If a capacity cap(p) is given for the places, This work was founded by the French National Research Agency, the European Commission (Feder funds) and the Région Auvergne in the Framework of the LabEx IMobS 3 . then x p ≤ cap(p) follows and we obtain X := {x ∈ N |P | : x p ≤ cap(p)} as set of potential states. A transition t ∈ T is enabled in a state x if x p ≥ w(p, t) for all p with (p, t) ∈ A (and x p + w(t, p) ≤ cap(p) for all (t, p) ∈ A), switching or ring t yields a successor state succ(x) = x with x p = x p -w(p, t) for all (p, t) ∈ A and x p = x p + w(t, p) for all (t, p) ∈ A. Dynamic processes are represented by sequences of such state changes.

Petri nets can be reconstructed from experimental data by exact, exclusively data-driven approaches [START_REF] Durzinsky | Reconstruction of extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Wagler | Prediction of network structure[END_REF]. These approaches take as input a set P of places and discrete time-series data X given by sequences (x 0 ; x 1 , . . . , x m ) of experimentally observed system states. The goal is to determine all Petri nets (P, T, A, w) that are able to reproduce the data in a simulation.

In general, there can be more than one transition enabled at a state. The decision which transition switches is typically taken randomly (and the dynamic behavior is analyzed in terms of reachability, starting from a certain initial state).

To properly predict the dynamic behavior, (standard) Petri nets have to be equipped with additional activation rules to force the switching or ring of special transitions, and to prevent all others from switching. This can be done by using priority relations and control-arcs and leads to the notion of X -deterministic Petri nets [START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF][START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF], which show a prescribed behavior on the experimentally observed subset X of states: the reconstructed Petri nets do not only contain enough transitions to reach the experimentally observed successors x j+1 from x j , but exactly this transition will be selected among all enabled ones in x j which is necessary to reach x j+1 (see Section 2.2 for details).

For a successful reconstruction, the data X need to satisfy two properties: reproducibility (for each x j ∈ X there is a unique observed successor state succ X (x j ) = x j+1 ∈ X ) and monotonicity (meaning that all essential responses are indeed reported in the experiments), see Section 2.1. Having reproducible data is clearly evident for a successful reconstruction; the necessity of monotone data is shown in [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF].

In this paper, we focus on a necessary preprocessing step for the reconstruction approach described in [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF]. We test the data for reproducibility, provide a feasibility test (based on previous works in [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF]) to detect cases where the reconstruction from the given data may fail (see Section 3.1), and provide a strategy (based on previous works in [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF]) to cope with infeasible cases (see Section 3.2).

We close with some concluding remarks.

Note that the here presented results appeared without proofs in [START_REF] Wagler | Preprocessing for network reconstruction: Feasibility test and handling infeasibility[END_REF].

Reconstructing Petri Nets from Experimental Data

In this section we describe the input and the desired output of the reconstruction method from [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF]. Moreover, we briey sketch the reconstruction procedure; for a detailed description, we refer the reader to [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF].

Input: Experimental Time-Series Data

First, a set of components P (later represented by the set of places) is chosen which is expected to be crucial for the studied phenomenon and which can be treated in terms of measurements 1 .

To perform an experiment, the system is stimulated in a state x 0 (by external stimuli like the change of nutrient concentrations or the exposition to some pathogens) to generate an initial state x 1 ∈ X . Then the system's response to the stimulation is observed and the resulting state changes are measured at certain time points. This yields a sequence X (x 1 , x k ) = (x 0 ; x 1 , . . . , x k ) of states x i ∈ X reecting the time-dependent response of the system to the stimulation. Note that we also provide the state x 0 as the starting point for the stimulation, which will be needed later (see Section 3.2).

Every sequence has an observed terminal state x k ∈ X , without further changes of the system. The set of all terminal states in X is denoted by X term . For technical reasons, we interpret a terminal state x k ∈ X term as a state which has itself as observed successor state, i.e., x k = succ X (x k ).

Typically, several experiments starting from dierent initial states in a set X ini ⊆ X are necessary to describe the whole phenomenon, and we obtain experimental time-series data of the form

X = {X (x 1 , x k ) : x 1 ∈ X ini , x k ∈ X term }. We write x ∈ X to indicate that x is an element of a sequence X (x 1 , x k ) ∈ X .
Example 1. As running example, we consider the light-induced sporulation of Physarum polycephalum. The developmental decision of P. polycephalum plasmodia to enter the sporulation pathway is controlled by environmental factors like visible light [START_REF] Starostzik | Functional mapping of the branched signal transduction pathway that controls sporulation in Physarum polycephalum[END_REF]. A phytochrome-like photoreversible photoreceptor protein is involved in the control of sporulation Spo which occurs in two stages P F R and P R . If the dark-adapted form P F R absorbs far-red light F R, the receptor is converted into its red-absorbing form P R , which causes sporulation. If P R is exposed to red light R, it is photo-converted back to the initial stage P F R , which can prevent sporulation in an early stage, but does not prevent sporulation in a later stage. Figure 1 gives an example of experimental time-series data reecting this behavior, containing three time-series: X (x 1 , x 4 ) = (x 0 ; x 1 , x 2 , x 3 , x 4 ), X (x 5 , x 0 ) = (x 2 ; x 5 , x 0 ) and X (x 6 , x 8 ) = (x 3 ; x 6 , x 7 , x 8 ).

In the best case, two consecutively measured states x j , x j+1 ∈ X are also consecutive system states, i.e., x j+1 can be obtained from x j by switching a single transition. This is, however, in general not the case (and depends on the chosen time points to measure the states in X ), but x j+1 is obtained from x j by a switching sequence of some length, where the intermediate states are not reported in X . 1 Possibly, it is known that a certain component plays a crucial role, but it is not possible to measure the values of that component experimentally. For a successful reconstruction, the data X need to satisfy two properties: reproducibility and monotonicity. The data X are reproducible if for each x j ∈ X there is a unique observed successor state succ X (x j ) = x j+1 ∈ X . Moreover, the data X are monotone if for each such pair (x j , x j+1 ) ∈ X , the possible intermediate states x j = y 1 , y 2 , ..., y m+1 = x j+1 satisfy Whereas reproducibility is obviously necessary, it was shown in [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF] that monotonicity has to be required or, equivalently, that all essential responses are indeed reported in the experiments 2 .

x 0       0 0 1 0 0       x 1       1 0 1 0 0       x 2       0 0 0 1 0       x 3       0 0 0 1 0       x 4       0 0 0 1 1       x 5       0 1 0 1 0       x 6       0 1 0 1 0       x 7       0 0 1 0 0       x 8       0 0 1 0 1       FR R R d 1 d 2 d 3 d 4 d 5 d 6

Output: X -Deterministic Extended Petri Nets

A standard Petri net P = (P, T, A, w) ts the given data X when it is able to perform every observed state change from x j ∈ X to succ X (x j ) = x j+1 ∈ X . This can be interpreted as follows. With P, an incidence matrix M ∈ Z |P |×|T | is associated, where each row corresponds to a place p ∈ P of the network, and each column M •t to the update vector r t of a transition t ∈ T :

r t p = M pt :=      -w(p, t) if (p, t) ∈ A, +w(t, p) if (t, p) ∈ A, 0 otherwise.
Reaching x j+1 from x j by a switching sequence using the transitions from a subset T ⊆ T is equivalent to obtain the state vector x j+1 from x j by adding 2 When continuous data is discretized, all local minima and maxima of the measured values have to be kept for each p ∈ P to ensure monotonicity.

the corresponding columns M •t of M for all t ∈ T :

x j + t∈T M •t = x j+1 . (1)
Hence, T has to contain enough transitions to perform all experimentally observed switching sequences. The network P = (P, T, A, w) is conformal with X if, for any two consecutive states x j , succ X (x j ) = x j+1 ∈ X , the linear equation system x j+1 -x j = M λ has an integral solution λ ∈ N |T | such that λ is the incidence vector of a sequence (t 1 , ..., t m ) of transition switches, i.e., there are intermediate states

x j = y 1 , y 2 , ..., y m+1 = x j+1 with y l + M •t l = y l+1 for 1 ≤ l ≤ m.
Hereby, monotonicity avoids unnecessary solutions, since no homogeneous solutions of equation ( 1) have to be considered, see [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF][START_REF] Wagler | Prediction of network structure[END_REF].

To also force that the networks exhibit the experimentally observed dynamic behavior in a simulation, we equip standard networks with additional activation rules to further control the switching of enabled transitions, see [START_REF] Durzinsky | Reconstruction of extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF][START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF][START_REF] Wagler | On minimality and equivalence of Petri nets[END_REF].

On the one hand, control-arcs can be used to represent catalytic or inhibitory

dependencies. An extended Petri net P = (P, T, (A ∪ A R ∪ A I ), w) is a Petri net which has, besides the (standard) arcs in A, two additional sets of so-called control-arcs: the set of read-arcs A R ⊂ P × T and the set of inhibitor-arcs A I ⊂ P × T . We denote the set of all arcs by A = A ∪ A R ∪ A I . Here, an enabled transition t ∈ T coupled with a read-arc (resp. an inhibitor-arc) to a place p ∈ P can switch in a state x only if a token (resp. no token) is present in p; we denote by T A (x) the set of all such transitions.

On the other hand, in [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Torres | Encoding the dynamics of deterministic systems[END_REF][START_REF] Wagler | Prediction of network structure[END_REF] the concept of priority relations among the transitions of a network was introduced in order to allow the modeling of deterministic systems. In [START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF] it is proposed to model priorities by partial orders O on the transitions to reect the rates of the corresponding reactions where the fastest reaction has highest priority and, thus, is taken. For each state x, only a transition is allowed to switch if it is enabled and there is no other enabled transition with higher priority according to O; we denote by T A,O (x) the set of all such transitions. We call (P, O) a Petri net with priorities if P = (P, T, A, w) is a (standard or extended) Petri net and O a priority relation on T . The extended Petri net with priorities (P, O) is X -deterministic if {t l } = T A,O (y l ) holds for all y l . The desired output of the reconstruction approach consists of the set of all X -deterministic extended Petri nets (P, cap, O) (all having the same set P of places and the same capacities cap deduced from X by cap(p) = max{x p : x ∈ X }).

Figure 2 shows an X -deterministic extended Petri net tting the experimental data from Example 1.

Steps of the Reconstruction Approach

To reconstruct X -deterministic extended Petri nets from experimental timeseries data X , the following approach is proposed by [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF], based on previous works in [START_REF] Durzinsky | Reconstruction of extended Petri nets from time series data and its application to signal transduction and to gene regulatory networks[END_REF][START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF][START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF]. As initial step, extract the observed changes of states from the experimental data. For that, dene the set D := d j = x j+1 -x j : x j+1 = succ X (x j ) ∈ X . Generating the complete list of all X -deterministic extended Petri nets P = (P, T, A, w) includes nding the corresponding standard networks and their incidence matrices M ∈ Z |P |×|T | . The rst step is to describe the potential update vectors which might constitute the columns of M . Due to monotonicity, it suces to represent any d j ∈ D using update vectors from the following set only:

F
Box(d j ) =    r ∈ Z |P | : 0 ≤ r p ≤ d p if d j p > 0 d p ≤ r p ≤ 0 if d j p < 0 r p = 0 if d j p = 0    \ {0}.
Next, we determine for any d j ∈ D, the set Λ(d j ) of all integral solutions of

d j = r t ∈ Box(d j ) λ t r t , λ t ∈ Z + ,
and for each λ ∈ Λ(d j ), the (multi-)set R(d j , λ) = {r t ∈ Box(d j ) : λ t = 0} of update vectors used for this solution λ. Every permutation π = (r t1 , . . . , r tm ) of the elements of a set R(d j , λ) gives rise to a sequence of intermediate states resolved by adding appropriate control-arcs. In [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF], it is proposed to construct a priority conict graph G whose nodes correspond to all possible sequences σ π,λ (x j , d j ) and whose edges reect weak and strong priority conicts. In G, all node subsets S are generated that select exactly one sequence σ π,λ (x j , d j ) per dierence vector d j ∈ D such that no strong priority conicts occur between the selected sequences. Each such subset S gives rise to a standard network P S = (P, T S , A S , w) which is conformal with X and can be made X -deterministic by inserting control-arcs and combining the priority relations O σ for all σ ∈ S:

x j = y 1 , y 2 , ..., y m , y m+1 = x j+1 with σ = σ π,λ (x j , d j ) = (y 1 , r t1 ), (y 2 ,
• we obtain the columns of the incidence matrix M S of the network by taking the union of all sets R(d j , λ) corresponding to the sequences σ = σ π,λ (x j , d j ) selected by σ ∈ S; • for each weak priority conict between σ, σ ∈ S involving update vectors r t = r t and intermediate states y = y , include either a read-arc (p, t) ∈ A R with weight w(p, t) > y p for some p with y p > y p or an inhibitor-arc (p, t) ∈ A I with weight w(p, t) < y p for some p with y p < y p to disable transition t resulting from r t at y ,

• for each σ ∈ S, dene O σ by O σ = {t i > t : t ∈ T A S ∪A R ∪A I (y i ) \ {t i }, 1 ≤
i ≤ m} and let O S = σ∈S O σ be the studied partial order.

This implies nally that every extended network P S = (P, T S , A S ∪ A R ∪ A I , w) together with the partial order O S is X -deterministic, see [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF] for details.

Feasibility Test and Handling Infeasibility

Before the reconstruction is started, a preprocessing step is necessary in order to verify or falsify whether the experimental time-series data X is suitable for reconstructing X -deterministic extended Petri nets (see Section 3.1). If the test is successful, the reconstruction algorithm can be applied. For the case that the given data are not suitable for the reconstruction, we provide a method to handle the infeasible cases (see Section 3.2). For that, we interpret (as in [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF])

the experimental time-series data X as a directed graph, the experiment graph D(X ) = (V X , A D ∪ A S ) of X , having the measured states x ∈ X as nodes and two kinds of arcs:

• A D := {(x j , x j+1 ) : x j+1 = succ X (x j )} for the observed responses,

• A S := {(x 0 , x 1 ) : X (x 1 , x k ) = (x 0 ; x 1 , . . . , x k )} for the stimulations.

D(X ) can be interpreted as a minor of the reachability graph, where observed responses may correspond to directed paths with intermediate states.

Our main objective is to test the given experimental time-series data X for reproducibility, i.e., whether each state x ∈ X has a unique successor state succ X (x) ∈ X . We provide a feasibility test to ensure this property (based on previous tests for standard Petri nets [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF] and extended Petri nets [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF], see Section 3.1). If this test fails, we have a state x ∈ X with at least two successors in X , and it is not possible to reconstruct an X -deterministic extended Petri net from X in its current form. As proposed in [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF][START_REF] Wagler | Prediction of network structure[END_REF], this situation can be resolved by adding further components 3 to P with the goal to split any state 3 Since P is only a projection from the real world, it is possible that some components of the system, crucial for the studied phenomenon, were not taken into account or could not be experimentally measured.

x ∈ X with two successors into dierent states each having a unique successor.

We present in Section 3.2 an approach for this step (based on previous works for standard Petri nets [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF]).

3.1 X -Determinism Conicts and Feasibility Test Denition 1. Let X be experimental time-series data. We say that two timeseries X i = X (x i0 , x i k ) and X = X (x 0 , x m ) are in X -determinism conict, when there exists a state x ∈ X with succ Xi (x) = succ X (x) and call x the corresponding X -determinism conict state. We have

• a strong X -determinism conict if x i k = x m or X i = X ; • a weak X -determinism conict if x i k = x m and X i = X .
The denition of strong X -determinism conicts includes the case discussed in [START_REF] Durzinsky | Reconstruction of extended Petri nets from time-series data by using logical control functions[END_REF][START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF] that there must not exist a terminal state x j ∈ X term that occurs as intermediate state in an experiment and the case that a state x j ∈ X \ X term has itself as successor, which would result in d j = 0 (see Example 2).

Example 2. In the experimental time-series data X shown in Figure 1 we have no weak but two strong X -determinism conicts:

• in the sequence X (x 1 , x 4 ) the states x 2 and x 3 are equal but have dierent successor states,

• the sequences X (x 5 , x 0 ) and X (x 6 , x 8 ) have equal initial state x 5 = x 6 , but dierent terminal states. Besides the initial states, the states x 0 and x 7 are X -determinism conict states.

Obviously, every X -determinism conict violates the condition of the data being reproducible. Conversely, if no X -determinism conict occurs, the data are reproducible and we have: Lemma 1. Let X be experimental time-series data. If every state x ∈ X has a unique successor state succ X (x) ∈ X then there exists an X -deterministic extended Petri net.

Proof. The pre-condition that every state x ∈ X has a unique successor in X includes the cases that no state x j ∈ X \ X term has itself as successor (and, thus, d j = 0 follows for all d j ∈ D) and that no terminal state x k ∈ X term is an intermediate state of any experiment.

Having d j = 0 for all d j ∈ D guarantees the existence of a standard network being conformal with X : By construction, Box(d j ) is non-empty due to d j = 0 for all d j ∈ D. Hence, d j is a trivial representation λ 0 for itself with R(d j , λ 0 ) = {d j }, and the standard network P whose incidence matrix has all vectors d j ∈ D as columns is conformal with X .

P can be made X -deterministic by adding appropriate control-arcs: Suppose that there are x j , x l ∈ X such that d j and d l with d j = d l are enabled at both states x j and x l . By pre-condition, one of them is not a terminal state, say

x j / ∈ X term . Then d j has to be turned into a transition t j disabled at x l . For that, include either a read-arc (p, t j ) ∈ A R with weight w(p, t j ) > x l p for some p with x j p > x l p , or an inhibitor-arc (p, t j ) ∈ A R with weight w(p, t j ) < x l p for some p with x j p < x l p . This can be done since x j = x l by pre-condition (otherwise, x j = x l would be a state having two dierent successors x j + d j and x l + d j ).

Therefore, the existence of an extended Petri net (where on each x j ∈ X the transition t j resulting from d j has highest priority, including priority t l < t j ∈ O for each of the above described conicts) being X -deterministic is ensured.

Two time-series X (x i0 , x i k ) and X (x 0 , x m ) with x i k = x m may be in weak X -determinism conict, due to dierently chosen time points of the measurements. We test the data for such a situation and try to resolve the conict by linearizing these sequences, respecting monotonicity.

A linear order L (or total order ) on a set S is a partial order where additionally (a ≤ b) ∈ L or (b ≤ a) ∈ L holds for all a, b ∈ S. In this case, we say that the set S is totally ordered (w.r.t. L). A totally ordered subset U ⊆ S of a partially ordered set S is called a chain of S.

On a time-series X (x 1 , x k ) = (x 0 ; x 1 , . . . , x k ), a linear order is induced by the successor relation: x j ≤ x j+1 i x j+1 = succ X (x 1 ,x k ) (x j ), hence X can be considered as a partially ordered set (ordered by the successor relation), where each time-series X (x 1 , x k ) is a chain of X . Let succ X (x j ) = x j+1 and Box(x j , x j+1 ) := y ∈ X :

x j p ≤ y p ≤ x j+1 p if x j p ≤ x j+1 p x j p ≥ y p ≥ x j+1 p if x j p ≥ x j+1 p .
Note that due to monotonicity, all intermediate states y of any rened sequence from x j to x j+1 lie in Box(x j , x j+1 ). Consequently, if two time-series X i = X (x i0 , x i k ) and X = X (x 0 , x m ) with x i k = x m are in weak X -determinism conict, and x is a determinism conict state then we have to test whether succ Xi (x) ∈ Box(x, succ X (x)) or succ X (x) ∈ Box(x, succ Xi (x)), see Figure 3.

If the test fails, we cannot nd a X -deterministic linear order. Otherwise, x = succ Xi (x) or x = succ X (x) is a new X -determinism conict state, and the test has to be repeated for x (see Algorithm 1). This works since at least the terminal states x i k and x m are equal. Whenever this test is successful for x and all subsequent X -determinism conict states x , we say that it is resolvable, otherwise we say it is an unresolvable weak X -determinism conict.

We next prove the correctness of Algorithm 1.

Lemma 2. Let X be experimental time-series data and let X i = X (x i0 , x i k ) and X = X (x 0 , x m ) be two time-series in a weak X -determinism conict. Algorithm 1 returns linearized times-series for X i and X if and only if the weak X -determinism conict is resolvable.

Proof. Let x ∈ X be a conict state for X i and X . We show that false is returned if and only if the conict in x is not resolvable.

x i0

x 0 x succ Xi (x) succ X (x)

x ik = x m ? ? Fig. 3. This gure shows a weak X -determinism conict. To resolve this conict we can test if the two dierent successor states (resulting from two dierent experiments) of the X -determinism conict state x can be ordered respecting monotonicity. In other words, we test if one of these successor states is an unmeasured intermediate state of x and the other successor state.

Algorithm 1 Resolving weak X -determinism conicts by linearization Input: time-series X (x i 0 , x i k ), X (x 0 , x m ) in weak X -determinism conict Output: adjusted time-series if resolvable weak X -determinism conict or false otherwise 1: for all conict states x do 2:

x i ← succ X (x i 0 ,x i k ) (x), x ← succ X (x 0 ,x m ) (x) 3:
L ← ∅ stores the linear order 4:

while

x i = x do 5: if x i ∈ Box(x, x ) then 6: L ← L ∪ {x i < x } 7:
x ← x i 8:

x i ← succ X (x i 0 ,x i k ) (x i ) 9:
else if x l ∈ Box(x, x i ) then 10:

L ← L ∪ {x < x i } 11:

x ← x 12:

x ← succ X (x 0 ,x m ) (x ) 13: else 14: return false 15: return adjusted time-series according to L In line 2 the variables x i and x are initialized as successor state of x in the corresponding time-series. The set L, which stores the linear order, is initialized with the empty set in line 3.

If we have x i = x then one of the following is true:

(i) x i = x = x i k = x m , i.e.
, both states are the terminal states of the timeseries,

(ii) all successor states after x are equal in both time-series, and thus further linearization is not necessary, (iii) both time-series have equal successor states after x, but there is another weak conict state in the time-series.

While in the rst two cases the algorithm stops, in (iii) the algorithm continues due to the for loop in line 1.

In line 5 (resp. 9) it is tested if x i ∈ Box(x, x ) (resp. x ∈ Box(x, x i ))

(see Figure 3 for an illustration). Note that this is possibly true for several successor states of x. However, the intermediate states of a decomposition must be monotone and therefore, the tested states must respect the monotonicity constraint as well. This is ensured by lines 7 and 8 (resp. 11 and 12). If some states are not monotone intermediate states of the other time-series, then it follows that there exist a state x i+1 = succ

X i (x i ) so that x i+1 / ∈ Box(x i , x ) but x i+1 ∈ Box(x i-1 , x ), with x i = succ X i (x i ).
Depending on which state comes next in the linear order, the set L is updated accordingly in line 6 (resp. 10). Since the case x ∈ Box(x, x i ) is tested analogously, we ensure that the successor states of x in one times-series is within the box of x and the successor state of the other time-series; and, in the case of several successor states within that box, that they are monotone. If neither is true, then it follows that the conict is not resolvable. Hereby, line 14 returns false . When the algorithm stops in line 15, two time-series are returned based on the computed linear order.

The algorithm always stops after a nite number of steps since we have x i k = x m , ensuring that line 4 is called nitely often (time-series are by denition nite) before being true or line 14 is called before. This enables us to formulate the following feasibility test: Theorem 1. Let X be experimental time-series data. There exists an X -deterministic extended Petri net if and only if there are neither strong X -determinism conicts nor unresolvable weak X -determinism conicts.

Proof. ⇐ If every state x ∈ X has a unique successor in X , the assertion follows from Lemma 1.

Let there be two time-series X (x i0 , x i k ) and X (x 0 , x m ) in a resolvable weak X -determinism conict in state x ∈ X . Due to monotonicity of the data and by denition of a resolvable weak X -determinism conict state, there exists a linear order on the subsequences of the time-series starting with x, so that every successor after x is unique, i.e., we have a rened sequence (x, x1 , . . . , xk ), with xk = x i k = x m , and for all 1 ≤ j ≤ k we have xj ∈ X (x i0 , x i k ) or xj ∈ X (x 0 , x m ). Now we consider the following time-series X (x i0 , x i k ) = (x i1 , x i2 , . . . , x, x1 , . . . , xk ) and X (x 0 , x m ) = (x 1 , x 2 , . . . , x, x1 , . . . , xk ). Let X be now the experimental time-series data containing all (if necessary linearized) time-series from X . Then every state in X has a unique successor state, and thus, Lemma 1 can be applied to X , proving the statement.

⇒ We show, if there exists a strong X -determinism conict or an unresolvable weak X -determinism conicts then there does not exist an X -deterministic extended Petri net.

Firstly, let x j ∈ X be a strong X -determinism conict state so that x j has itself as successor state. Then d j = 0 follows and, thus, Box(d j ) = ∅. Therefore, there does not exist a standard Petri net conformal with X and, thus, no X -deterministic extended Petri net.

Secondly, let x j ∈ X be a strong X -determinism conict state for two timeseries X i = X (x i0 , x i k ) and X = X (x 0 , x m ). Then, by denition, succ Xi (x j ) = succ X (x j ). We show that this X -determinism conict can neither be resolved by priorities nor by control-arcs.

Let d i , d such that succ Xi (x j ) = x j + d i and succ X (x j ) = x j + d . For the trivial decompositions σ π,λ (x j , d i ) = ((x j , r t i )) and σ π,λ (x j , d ) = ((x j , r t )), the time-series X i implies t < t i ∈ O while X implies t i < t ∈ O. This conict can only be resolved by adding control arcs. Let t i < t ∈ O, then control-arcs must be added to disable t in x j . But then t i can never re in x j . Analogously, if t i < t ∈ O then t can never re in x j . In the case that t < t i / ∈ O and t i < t / ∈ O then again either X i and/or X are no longer valid using the same arguments. Thus, there is no extended Petri net with priorities being X -deterministic. Now we consider non-trivial decompositions σ π,λ (x j , d i ) = ((y i1 , r t i1 ), . . . , (y imi , r t im i )) and σ π,λ (x j , d ) = ((y 1 , r t 1 ), . . . , (y m , r t m )).

Since the successor of x j is not equal in both time-series, i.e., succ Xi (x j ) = succ X (x j ) it follows that there exist y iji and y j with y iji = y j but y i(ji+1) = y (j +1) . Then the same argument as above can be applied to y iji (resp. y j ). Finally, let x j ∈ X be an unresolvable weak X -determinism conict state for two time-series X i = X (x i0 , x i k ) and X = X (x 0 , x m ). We consider the two decompositions σ π,λ (x j , d i ) = ((y i1 , r t i1 ), . . . , (y imi , r t im i )) and σ π,λ (x j , d ) = ((y 1 , r t 1 ), . . . , (y m , r t m )) so that y i1 = y 1 , y i2 = y 2 , . . . , y ij = y j but y i(j+1) = y (j+1) . By denition of an unresolvable weak X -determinism conict, such a decomposition always exists. Now again, the same arguments from above can be applied to y ij (resp. y j ). Thus, there does not exist an X -deterministic extended Petri net, which proves this theorem.

Handling Infeasibility

Due to Theorem 1, it is impossible to reconstruct X -deterministic extended Petri nets from experimental time-series data X containing a strong X -determinism conict or an unresolvable weak X -determinism conict. In this section we show how these conicts can be resolved by using additional components.

For that we extend, as proposed in [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF][START_REF] Marwan | A mathematical approach to solve the network reconstruction problem[END_REF], all the n-dimensional state vectors x ∈ X to suitable (n + a)-dimensional vectors

x j := x j z j ∈ X = x = x z ∈ Z n+a : 0 ≤ z ≤ 1, x ∈ X .
The studied extensions x j ∈ N n+a of the states x j ∈ X correspond to suitable labelings of the experiment graph D(X ): if a = 1, to (0, 1)-labelings, where label i is assigned to node x j if x j n+1 = z j = i is selected for i ∈ {0, 1}; if a = 2, to (0, 1, 2, 3)-labelings, where the labels are assigned to the four dierent states (0, 0) T , (1, 0) T , (0, 1) T and (1, 1) T ; if a ≥ 3 we use similar encodings for all 2 a dierent 0/1-vectors.

x 0 0 x 1 0 x 2 0 x 3 1 x 4 1 x 5 0 x 6 1 x 7 1 x 8 1 FR R R d 1 d 2 d 3 d 4 d 5 d 6 x 0 0 x 1 0 x 2 0 x 3 1
x 4 0

x 5 0

x 6 1

x 7 1 where equations (2a) ensure that every state has a unique successor state (Condition (i) from Denition 2), equations (2b) that no stimulation changes the state of additional components (Condition (ii)), and equations (2c) preserve equal difference vectors (Condition (iii)). The conditions (2d) ensure that we have binary decision variables y ij . Each valid labeling corresponds to a vector in P(a).

x 8 0 FR R R
Note, due to inequalities (2a) the optimization problem is non-linear and has a non-convex set of feasible solutions. However, it is only necessary to nd the minimal a so that P(a) = ∅. We can consider the set P(a) as the union of 2 a convex sets (see Figure 5 for an illustration). Therefore, we can split the problem into 2 a linear subproblems, each having a convex (=polyhedral) feasible region.

For that, we dene two sets for each subproblem 1 ≤ k ≤ 2 a , namely P + (k) and P -(k), so that P + (k) ∪ P -(k) = {1, . . . , a} and P + (k) ∩ P -(k) = ∅ and P + (p) = P + (q), P -(p) = P -(q) for all p = q. The sets induce the indices i so that y ji -y li -(y pi -y qi ) ≥ 0 and y ji -y li -(y pi -y qi ) ≤ 0, respectively. Hereby, we have all possible combinations. For the sake of readability let z jlpqi = y ji -y li -(y pi -y qi ). Then we replace inequalities (2a) by the following constraints

i + ∈P + (k) z jlpqi + - i -∈P -(k)
z jlpqi -≥ 1 for all (x j , x l ), (x p , x q ) ∈ A D , (3a) z jlpqi + ≥ 0 for all i + ∈ P + (k), for all (x j , x l ), (x p , x q ) ∈ A D ,

z jlpqi -≤ 0 for all i + ∈ P + (k), for all (x j , x l ), (x p , x q ) ∈ A D ,

where A D := {(x j , x l ), (x p , x q ) ∈ A D with x j = x p , x l = x q }. These linear subproblems can be solved by standard solvers, and the optimal solution a of the original problem is obtained if one subproblem turns out to be feasible. All (minimal) valid labelings are then in P(a).

Conclusion

In this work, we give a preprocessing step for a reconstruction algorithm from [START_REF] Favre | Reconstructing X -deterministic extended Petri nets from experimental time-series data X[END_REF] that reconstructs extended Petri nets with priorities from experimental timeseries data X , so-called X -deterministic extended Petri nets. For a successful reconstruction the data must be reproducible and monotone. While reproducibility is clearly evident, the necessity of monotone data is shown in [START_REF] Durzinsky | A combinatorial approach to reconstruct Petri nets from experimental data[END_REF]. In this paper we give a feasibility test for the data and a strategy for handling infeasible cases.

Firstly, the preprocessing step examines the given experimental time-series data for reproducibility, i.e., it tests if all measured states x ∈ X have a unique successor state (see Section 3.1). If this test is successful we can reconstruct an X -deterministic extended Petri net (Lemma 1).

Whenever two time-series X i and X have a common state x but dierent successor states in each of these sequences (i.e., succ Xi (x) = succ X (x)) we have an X -determinism conict. Depending on whether the terminal states of these conicts are equal or not, we have a weak or a strong X -determinism conict.

When we encounter a weak X -determinism conict we try to linearize the two sequences by the induced order of the successor relation. This is done in the second step of the preprocessing (see Section 3.1).

If linearizing the time-series is not possible or when there are strong X -determinism conicts, we cannot reproduce X -deterministic extended Petri nets (Theorem 1). In this case we extend the data by adding additional components to every state of X (see Section 3.2). Finally, in order to compute valid vectors of additional components, we solve an optimization problem.

After having performed the preprocessing step, the reproducibility of the (given or modied) data X can be guaranteed such that X can serve as appropriate input for the main reconstruction algorithm.

Fig. 1 .

 1 Fig. 1. This gure shows experimental time-series data X for the light-induced sporulation of Physarum polycephalum. The experimental setting uses the set P = {F R, R, P f r , Pr, Sp} of studied components, observed states are represented by vectors of the form x = (xF R, xR, xP f r , xP r , xSp) T having 0/1-entries only. Dashed arrows represent stimulations to the system and solid arrows represent the observed responses.

y 1 p ≤ y 2 p≤ x j+1 p and y 1 p ≥ y 2 p

 212 ≤ . . . ≤ y m p ≤ y m+1 p for all p ∈ P with x j p ≥ . . . ≥ y m p ≥ y m+1 p for all p ∈ P with x j p ≥ x j+1 p .

6 Fig. 4 .

 64 Fig. 4. This gure shows values for additional components resolving the strong X -determinism conicts from Example 2 in Figure 1.

Fig. 5 .

 5 Fig.[START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF]. In this gure the division of (2a) into 2 a subproblems is illustrated within the 2-dimensional space (i.e., a = 2). Each of the resulting 4 subproblems has a convex feasible region (highlighted by the dotted regions) whose union corresponds to the feasible region of the original problem.

  Fig.2. This gure shows an X -deterministic extended Petri net tting the experimental data from Example 1. The set P of components has been extended by a component committed which cannot be measured directly, but only indirectly deduced by the behavior of Physarum polycephalum observed in the experiment. The here shown network corresponds to solution (a) from Figure4. It has a read-arc from Pr to t 2 and one from committed to t 3 . Furthermore, we have the set of priorities O = {t 2 < t 4 , t 3 < t 4 }. The control-arcs and priorities ensure |TA,O(x)| = 1 for every state x ∈ X .

		Pr		t 2	commited
	R	t 1	t 4	R
		Pfr			t 3	Sp

  Two sequences σ and σ are in priority conict if there are update vectors r t = r t and intermediate states y, y such that t, t ∈ T (y) ∩ T (y ) and (y, r t ) ∈ σ but (y , r t ) ∈ σ (since this implies t > t in O σ but t > t in O σ ). We have a weak (resp. strong) priority conict if y = y (resp. y = y ) which can (resp. cannot) be

r t2 ), . . . , (y m , r tm ) which induces a priority relation O σ since transition t i resulting from r ti is supposed to have highest priority in y i for 1 ≤ i ≤ m.

By using appropriate additional components, states that appear equal in experimental time-series data X become dierent in X (see Figure 4). It is already stressed in [START_REF] Durzinsky | An algorithmic framework for network reconstruction[END_REF] that not every labeling for the experiment graph D(X ) is reasonable, as a state x k ∈ X with x k ∈ X term might have a successor state, a state x j might have multiple successor states, or some stimulation changes more than the target input component(s). To obtain suitable labelings for Xdeterministic extended Petri nets, we adjust Denition 15 from [5]: Denition 2. A labeling L of X is valid if it satises the following conditions:

(i) every state x has a unique successor state succ(x), >From Condition (i) we can conclude that we have x = succ X (x) if and only if x ∈ X term . Condition (ii) ensures that a stimulation does not change more than the target input component(s), and nally, Condition (iii) ensures a minimal number of label switches, while keeping the data as close as possible to the original measurements. Furthermore, due to symmetry reasons, we can choose a label for one state, e.g., a conict state.

Example 3. Besides symmetric solutions, there are two possible valid labelings with a = 1 for the experimental time-series data from Figure 1. These two solutions are shown in Figure 4. The solutions are obtained by applying the conditions of Denition 2 as follows. We start by selecting an X -determinism conict state, here x 2 , and choose its label as x 2 z = 0. Due to Condition (ii), x 5 z = 0 follows. Condition (i) implies that x 3 (resp. x 6 ) must be dierent from x 2 (resp. x 5 ). Therefore, x 3 z = 1 and x 6 z = 1 follows. Since we have d 4 = d 5 , Condition (iii) implies that the only valid labels for x 0 and x 7 are 0 and 1, respectively. Condition (ii) shows x 1 z = 0. Finally, we can choose a label for x 4 and x 8 , respectively. However, since d 3 = d 6 , if follows from (iii) that both labels must be equal.

In order to nd all valid labelings of a general experiment graph D(X ) = (V X , A D ∪ A S ) we set up an optimization problem encoding the conditions for valid labelings and having as objective the minimization of the number a of additional components. For that we introduce decision variables y ji to determine whether label i is assigned to x j .

We are interested in nding min{a ∈ N : P(a) = ∅}, where P(a) is given by

y ji -y li = 0 for all (x j , x l ) ∈ A S (2b) y ji -y li = y pi -y qi for all (x j , x l ), (x p , x q ) ∈ A D , with x lx j = x px q (2c) y j1 , . . . , y j2 a ∈ {0, 1} for all (x j , x l ) ∈ A D , i = 1, . . . , 2 a , (2d)