# Modeling Delayed Dynamics in Biological Regulatory Networks from Time Series Data +
## 4 Learning Timed Automata Networks
### Algorithm
* Let \(\varphi:=\emptyset\)
* Step 1: According to \(\Gamma\), for each time step \(t\) where a component \(a\) changes its value from \(a_{i}\) to \(a_{j}\), with \(a_{i},a_{j}\in\mathcal{S}_{a}\):
* **for all**\(\ell\in\wp(\chi_{a}),|\ell|\leq i\), generate exhaustively all timed local transitions: \[\tau:=(a_{i},\ell,a_{j},\delta)\] such that,
* **if**\(\exists(c_{k},\ell_{c},c_{l},\delta_{c})\in\mathcal{T}\) with \(a\in\ell_{c}\) and \(\Pi_{t}^{c}\geq\Pi_{t}^{a}\wedge\Pi_{t}^{c}\geq\Pi_{t}^{b}\)\(\forall b\in\ell\)**then**\(\delta=t-\delta_{t}^{c}\) **else**\(\delta=t-max(\Pi_{t}^{a},\Pi_{t}^{b})\) with \(h\in\ell\wedge\forall b\in\ell\), \(b\
eq h,\Pi_{t}^{b}\leq\Pi_{t}^{b}\). * Add all timed local transition \(\tau\) in \(\varphi\)
* Step 2: Create in \(\Phi\) as much as possible T-AN \(\mathcal{AN}^{\prime}=(\Sigma,\mathcal{S},\varphi^{\prime})\) with \(\varphi^{\prime}\subseteq\Phi\) a set of timed local transitions that can realize \(\Gamma\), such that \(\varphi^{\prime}\) is minimal: \[\forall\mathcal{AN}^{\prime}=(\Sigma,\mathcal{S},\varphi^{\prime})\in\phi, \
exists\varphi^{\prime\prime}\subseteq\Phi,\varphi^{\prime\prime}\subset \varphi^{\prime},\text{such that $\varphi^{\prime}$can realize $\Gamma$}\] \[\forall a\in\Sigma,\forall t\text{ a time step in $\Gamma, \exists!\tau\in\varphi$, such that $\tau$ explains $\Pi_{t}^{a}$}\]  
**Algorithm 1** MoT-AN: modeling timed automata networks. Because of the delays and the non-deterministic semantics, it is not possible to decide whether a timed local transition is absolutely correct or not. However, we can output the minimal sets of timed local transitions, which are necessary to realize all of the dynamics changes. However, since observations are not perfect, we cannot safely remove non-consistent transitions. Thus, we refine the output model by filters taking into account the different possible perturbations. These filters are detailed more later in Section 5. For the rest of the article, we denote by \(\Pi_{t}^{x}\) the last change of each component \(x\) comparing to \(t\) ( i.e., \(\forall x\in\Sigma\ \Pi_{t}^{x}\leq t\)). **Theorem 1** (Completeness). : _Let \(\mathcal{AN}=(\Sigma,\mathcal{S},\mathcal{T})\) be a T-AN, \(\Gamma\) be a chronogram of the components of \(\mathcal{AN}\), \(i\) the indegree with \(i\in\mathbb{N}\) and \(R\in\mathcal{T}\) the set of timed local transitions that realized the chronogram \(\Gamma\), such that \((a_{i},l,a_{j},\delta)\in R\implies|l|\leq i\). Let \(\chi\) be the regulation influences of all \(a\in\Sigma\). Let \(\mathcal{AN}^{\prime}=(\Sigma,\mathcal{S},\emptyset)\) be a T-AN. Given \(\mathcal{AN}^{\prime}\), \(\Gamma\), \(\chi\) and \(i\) as input, Algorithm 1 is complete: it will output a set of T-AN \(\phi\), such that \(\exists\mathcal{AN}^{\prime\prime}=(\Sigma,\mathcal{S},\varphi^{\prime})\in\phi\) with \(R\subseteq\varphi^{\prime}\)._  
Proof. : Let us suppose that the algorithm is not complete, then there is a timed local transition \(h\in R\) that realized \(\Gamma\) and \(h\
ot\in\varphi^{\prime}\). In Algorithm 1, after Step 1, \(\varphi\) contains all timed local transitions that can realize each change of the chronogram \(\Gamma\). Here, there is no timed local transition \(h\in R\) that realizes\(\Gamma\), which is not generated by the algorithm, so \(h\in\varphi\). Then, it implies that at Step 2, \(\forall\varphi^{\prime},h\
ot\in\varphi^{\prime}\). However, since \(h\) realizes one of the changes of \(\Gamma\) and \(h\) is generated at Step 1, then it will be present in one of the minimal subsets of timed local transitions; such that \(h\) will be in one of the networks outputted by the algorithm. If \(\mathcal{AN}=(\Sigma,\mathcal{S},\mathcal{T})\) is a T-AN learned model regarding the chronogram \(\Gamma\) and the interaction graph \(\chi\) of the automata in \(\Sigma\), such that \(\forall\Pi_{t}^{x}\in\Gamma\)\(\exists\tau\in\mathcal{T}\), which realize \(\Pi_{t}^{x}\). **Theorem 2** (Complexity).