# Modeling Delayed Dynamics in Biological Regulatory Networks from Time Series Data +
## 4 Learning Timed Automata Networks
### Algorithm
: _Let \(\mathcal{AN}=(\Sigma,\mathcal{S},\mathcal{T})\) be a T-AN, \(|\Sigma|\) be the number of automata of \(\mathcal{AN}\), \(\eta\) the total number of local states of an automaton of \(\mathcal{AN}\) and \(i\) the maximal in-degree of all transitions with \(0\leq i\leq|\Sigma|\). Let \(\Gamma\) be a chronogram of the components of \(\mathcal{AN}\) over \(T\) units of time, such that \(c\) is the number of changes in \(\Gamma\), \(0\leq c\leq T\). The memory use of Algorithm 1 belongs to \(O(T\cdot(|\Sigma|\cdot\eta)^{|i|}\cdot 2^{T\cdot(|\Sigma|\cdot\eta)^{|i|}})\) that is bounded by \(O(T\cdot|\Sigma|^{T\cdot(|\Sigma|^{|\Sigma|+1}})\). The complexity of learning \(\mathcal{AN}\) by generating timed local transitions from the observations of \(\Gamma\) with Algorithm 1 belongs to \(O(c\cdot(|\Sigma|\cdot\eta)^{|i|}+2^{2\cdot T\cdot(|\Sigma|\cdot\eta)^{|i|}}+c \cdot 2^{T\cdot(|\Sigma|\cdot\eta)^{|i|}})\) that is bounded by \(O(T\cdot 2^{3\cdot T\cdot(|\Sigma|\cdot\eta)^{|\Sigma|}})\)._  
Proof. : Let \(p\) be an automaton local state of \(\mathcal{AN}\), then \(|\Sigma|\) is the maximal number of automaton that can influence \(p\). There is \((|\Sigma|\cdot\eta)^{|i|}\) possible combinations of those regulators that can influence \(p\) at the same time forming a timed local transition. There is at most \(T\) possible delays, so that there are \(T\cdot|\Sigma|\cdot(\Sigma\cdot\eta)^{|i|}\) possibles timed local transitions; thus, in Algorithm 1 at Step 1, the memory is bounded by \(O(T\cdot(|\Sigma|\cdot\eta)^{|i|})\), which belongs to \(O(T\cdot|\Sigma|^{|\Sigma|})\) since \(0\leq i\leq|\Sigma|\). Generating all minimal subsets of timed local transitions \(\varphi\) of \(\mathcal{AN}\) that can realize \(\Gamma\) can require one to generate at most \(2^{T\cdot|\Sigma|\cdot(|\Sigma|\cdot\eta)^{|i|}}\) sets of rules. Thus, the memory of our algorithm belongs to \(O(c\cdot(|\Sigma|\cdot\eta)^{|i|}+2^{2\cdot T\cdot(|\Sigma|\cdot\eta)^{|i|}}+ c\cdot 2^{T\cdot(|\Sigma|\cdot\eta)^{|i|}})\) and is bounded by \(O(T\cdot 2^{3\cdot T\cdot(|\Sigma|\cdot\eta)^{|\Sigma|}})\). The complexity of this algorithm belongs to \(O(c\cdot i^{|\Sigma|})\). Since \(0\leq i\leq|\Sigma|\) and \(0\leq c\leq T\), the complexity of Algorithm 1 is bounded by \(O(T\cdot|\Sigma|^{|\Sigma|}))\). Each set has to be compared with the others to keep only the minimal ones, which costs \(O(2^{2\cdot T\cdot(|\Sigma|\cdot\eta)^{|i|}})\). Furthermore, each set of timed local transitions has to realize each change of \(\Gamma\); it requires to check that \(c\) changes, and it costs \(O(c\cdot 2^{T\cdot(|\Sigma|\cdot\eta)^{|i|}})\). Finally, the total complexity of learning \(\mathcal{AN}\) by generating timed local transitions from the observations of \(\Gamma\) belongs to \(O(c\cdot(|\Sigma|\cdot\eta)^{|i|}+2^{2\cdot T\cdot(|\Sigma|\cdot\eta)^{|i|} }+c\cdot 2^{T\cdot(|\Sigma|\cdot\eta)^{|i|}})\) that is bounded by \(O(T\cdot 2^{3\cdot T\cdot(|\Sigma|\cdot\eta)^{|\Sigma|}})\). In practice, we can fix the maximal indegree of the generated timed local transitions and consider binary automaton (maximum of two local levels per automaton: \(\eta=2\)) to make the computation tractable. Considering an indegree \(i=2\), the complexity falls down to \(O(c\cdot(2\cdot 2)^{2}+2^{2\cdot T\cdot(2\cdot 2)^{2}}+c\cdot 2^{T\cdot(2\cdot 2 )^{2}})=O(c\cdot 16+2^{T\cdot 16}+c\cdot 2^{T\cdot 16})\). If at each time step, there is a change, so it is bounded by \(O(T\cdot 2^{3\cdot T\cdot(|\Sigma|\cdot 2)^{2}})=O(T\cdot 2^{3\cdot T\cdot(2\cdot 2 )^{2}})=O(T\cdot 2^{48\cdot T})\). Indeed, in biological systems, the number of interactions between components is not too large, so it is not the source of complexity, but the fact that we generate all possible minimal models. Besides, behavior can be captured with a simple combination consisting of two components, like in Section 3.2 of [4]. If we output only one model, we find that the complexity falls down to \(O(c\cdot 16)=O(c)\).