We have presented a Control Flow Analysis for Beta-binders, able to describe the essential behaviour of each of its boxes, in terms of possible interactions. When ap-plied to the version of Beta-binders, modelling biological compartments, the analysis has been extended accordingly. To this aim, it is also able to approximate the pos-sible movements across compartments. Furthermore, the analysis can offer a set of approximations of all the possible actions the beta-process under analysis can perform, with indication on the possible boxes and the compartments involved.
Simply exploiting the soundness of our analysis, in the first part of the work, we have proved some basic facts, that can be immediately used to establish simple properties, such as the absence of interaction of two boxes or the isolation of a box.
In the second part, we have addressed, for brevity, only part of the locality relations reported in [9]. Our approach can be easily extended to the other relations in [9]
and also to the causality-based relations, like the ones in [6] for the π−calculus.
Both results are useful for illustrating how suitable static techniques can be adapted to model biological systems, giving some insights on their behaviour.
In classical process algebras, communications are modelled in a key-lock style, by requiring that an input and an output can communicate only if they synchronize on the same channel. In Beta-binders the key-lock model for interaction is partially relaxed. Interactions between boxes are allowed when the types of binders show some form of compatibility. This is a nice feature, when formalising biological behaviour, maybe collecting part of specifications in different databases, because it allows to easily put together the needed components. It is sufficient to put them in different boxes, just establishing the proper binders. Under this regard, code re-use is easier than in the π-calculus. It would be interesting to exploit this is feature also from a static analysis point of view, looking for suitable ways of composing independent analyses of parts of systems.
In perspective, static analysis can be fruitfully exploited to study dynamic prop-erties of large biological systems, by keeping the computational costs low. Further-more, it can be used to reason about the model chosen for describing the biological system under consideration, by checking the properties on the model and by com-paring the obtained results with the experimental ones reported in the literature.
Acknowledgments. We are grateful to Pierpaolo Degano and Linda Brodo for their helpful discussions and comments.
References
[1] Bruce Alberts, Alexander Johnson, Julian Lewis, Martin Raff, Keith Roberts and Peter Walter.
Molecular Biology of the Cell. Garland Science, 2002.
[2] Chiara Bodei. A static analysis for Beta-Binders. Proceedings of From Biology To Concurrency and back Workshop (FBTC’07). Electronic Notes in Theoretical Computer Science 194(3): 69-85, 2008.
[3] Chiara Bodei, Pierpaolo Degano, Flemming Nielson, and Hanne Riis Nielson. Static analysis for the π-calculus with their application to security. Information and Computation (165): 68-92, 2001.
[4] Luca Cardelli. Brane Calculi - Interactions of Biological Membranes. Proceedings of Computational Methods in Systems Biology (CMSB’04). Lecture Notes in Computer Science 3082, pp. 257-278, Springer, 2005.
[5] Luca Cardelli and Andrew D. Gordon. Mobile Ambients. Theoretical Computer Science 240(1): 177-213 (2000).
[6] Michele Curti, Pierpaolo Degano, Corrado Priami, Cosima Baldari. Modeling biochemical pathways through enhanced pi-calculus. Theoretical Computer Science325:111–140, 2004,
[7] Vincent Danos, Jean Krivine. Transactions in RCCS. Proceedings of Conference on Concurrency Theory (CONCUR’05). Lecture Notes in Computer Science 3653, pp. 398-412, Springer 2005.
[8] Vincent Danos, Cosimo Laneve. Graphs for Core Molecular Biology. Proceedings of Computational Methods in Systems Biology (CMSB’03). Lecture Notes in Computer Science 2602, pp. 34-46, Springer 2003.
[9] Maria Luisa Guerriero, Corrado Priami and Alessandro Romanel. Static Biological Compartments with Beta-binders. Proceedings of Algebraic Biology, Second International Conference (AB’07), Lecture Notes in Computer Science 4545, pp. 247–261. Springer, 2007.
[10] Hiroaki Kitano Systems Biology: a brief overview. Science 2002, 295(5560):1662–1664.
[11] Robin Milner. Communicating and mobile systems: the π-calculus. Cambridge University Press, 1999.
[12] Hanne Riis Nielson and Flemming Nielson. Flow Logic: a multi-paradigmatic approach to static analysis.
The Essence of Computation: Complexity, Analysis, Transformation, Lecture Notes in Computer Science 2566, pp. 223-244, Springer, 2002.
[13] Flemming Nielson, Hanne Riis Nielson, and Ren Rydhof Hansen. Validating firewalls using flow logics.
Theoretical Computer Science 283(2): 381-418 (2002).
[14] Flemming Nielson, Hanne Riis Nielson, Corrado Priami, and Debora Schuch da Rosa. Control Flow Analysis for BioAmbients. Electronic Notes in Theoretical Computer Science 180(3): 65-79. 2007.
[15] Flemming Nielson, Hanne Riis Nielson, Debora Schuch da Rosa, and Corrado Priami. Static analysis for systems biology. Proceedings of workshop on Systeomatics - dynamic biological systems informatics.
Computer Science Press, Trinity College Dublin, 2004.
[16] Flemming Nielson and Helmut Seidl. Control Flow Analysis in cubic time. Proceedings of Proceedings of European Symposium on Programming (ESOP’01), Lecture Notes in Computer Science 2028, pp.
252-268. Springer Verlag, 2001.
[17] Davide Prandi, Corrado Priami and Paola Quaglia. Communicating by compatibility. Journal of Logic and Algebraic Programming 75 (2): 167-181, 2008.
[18] Corrado Priami. Computational thinking in Biology. TR-10-2007. Centre for Computational and Systems Biology, University of Trento, 2007.
[19] Corrado Priami and Paola Quaglia. Beta-binders for Biological Interactions. Proceedings of Proceedings of Computational Methods in Systems Biology (CMSB’04), Lecture Notes in Computer Science 3380, pp. 20–33. Springer, 2005.
[20] Corrado Priami and Paola Quaglia. Operational patterns in Beta-binders. Proceedings of Transactions on Computational Systems Biology, Lecture Notes in Computer Science 3380, pp. 50-65, Springer, 2005.
[21] Corrado Priami, Aviv Regev, Ehud Y. Shapiro, William Silverman. Application of a stochastic name-passing calculus to representation and simulation of molecular processes. Inf. Process. Lett. 80(1): 25-31 (2001).
[22] Paola Quaglia. On Beta-binders Communications. Proceedings of Montanari Festschrift. Lecture Notes in Computer Science 5065, pp. 457-472, Springer, 2008.
[23] Aviv Regev, Ekaterina M. Panina, William Silverman, Luca Cardelli, and Ehud Y. Shapiro.
BioAmbients: An abstraction for biological compartments. Theoretical Computer Science 325(1): 141-167. 2004, Elsevier.
[24] Aviv Regev, William Silverman, Ehud Y. Shapiro. Representation and Simulation of Biochemical Processes Using the pi-Calculus Process Algebra. Pacific Symposium on Biocomputing, pp. 459-470, 2001.
[25] Jeannette M.Wing. Computational thinking. Communications of the ACM, 49(3):33-35, 2006.
A Proofs
In this appendix restates the lemmata and theorems presented earlier in the paper and gives the proofs of their correctness.
A.1 Correctness of the Analysis Lemma A.1 (Substitution result)
(i) (ι, , ρ, κ) |=µP and v ∈ ρ(x) imply (ι, , ρ, κ) |=µP {v/x};
(ii) (ι, , ρ, κ) |=∗ B and v ∈ ρ(x) imply (ι, , ρ, κ) |=∗ B{v/x};
Proof. Both proofs proceed by structural induction and uses the following fact:
∀y : ρ(y({v/x})) ⊆ ρ(y)
If indeed y 6= x then ρ(y({v/x})) = ρ(y), while if y = x, then ρ(y({v/x})) = ρ(v).
Furthermore, v ∈ ρ(y), because v ∈ ρ(x) and x = y. Therefore ρ(v) ⊆ ρ(y).
[(i)] The proof is by structural induction on P . We consider here only the two most interesting cases.
Case P ≡ z(w).P0. We may assume that w 6= v, x. Now, (ι, , ρ, κ) |=µP amounts to checking that (ι, , ρ, κ) |=µP0 and that (1) ∀a ∈ ρ(z) : κ(µ)(a) ⊆ ρ(w);
(2) ∀a ∈ ρ(z) : a ∈ ι(µ) and ∀µ0 ∈ ι(∗) : b ∈ ι(µ0) then comp((µ)(a), (µ0)(b)) ⇒ κ(µ0)(b) ⊆ ρ(y). By the induction hypothesis and the fact stated above, we have that (ι, , ρ, κ) |=µP0{v/x}. Furthermore, since ρ(z{v/x}) ⊆ ρ(z), we have that a certain condition holds for ∀a ∈ ρ(z) then a fortiori it holds also for ∀a ∈ ρ(z{v/x}).
As a consequence: (1) ∀a ∈ ρ(z{v/x}) : κ(µ)(a) ⊆ ρ(w), and (2) ∀a ∈ ρ(z{v/x}) : a ∈ ι(µ) and ∀µ0 ∈ ι(∗) : b ∈ ι(µ0) then comp((µ)(a), (µ0)(b)) ⇒ κ(µ0)(b) ⊆ ρ(y).
This is equivalent to the required (ι, , ρ, κ) |=µP {v/x}.
Case P = hide(z).P0. Now, (ι, , ρ, κ) |=µP amounts to checking that (ι, , ρ, κ) |=µP0 and that ∀a ∈ ρ(z) : ah ∈ ι(µ). As above, since ρ(z{v/x}) ⊆ ρ(z), we have that ∀a ∈ ρ(z{v/x}) : ah ∈ ι(µ). For this reason and by the induction hypothesis, we obtain the required (ι, , ρ, κ) |=µP {v/x}.
[(ii)] The proof is by structural induction on B. We consider here only one case.
Case B = β(z : Γ)B[P ]µ. Now (ι, , ρ, κ) |=∗ B is equivalent to (ι, , ρ, κ) |=∗ B{v/x}, because z{v/x} = z.
2 Lemma A.2 (Invariance of Structural Congruence)
(i) If P ≡ Q and (ι, , ρ, κ) |=µP then (ι, , ρ, κ) |=µQ (ii) If B ≡ B0 and (ι, , ρ, κ) |=∗ B then (ι, , ρ, κ) |=∗ B0
Proof. The proof amounts to a straightforward inspection of each of the clauses
defining the structural congruence clauses. 2
Theorem A.3 (Subject reduction)
If B → B0 and (ι, , ρ, κ) |=∗ B then also (ι, , ρ, κ) |=∗B0. Proof. By induction on the inference of →.
Case (Intra). Let B be B[P ]µ, where P ≡ (ν ˜u)(x(w).P1| xhzi.P2| P3), and
B0 = B[(ν ˜u)(P1{z/w}| P2| P3)]µ. We have to prove that (ι, , ρ, κ) |=∗B0. (ι, , ρ, κ) |=∗ B[P ]µ, amounts to µ ∈ ι(∗), ∀ ˆβ(x : Γ) in B : x ∈ (µ) and ρ(Γ) ∈
(µ)(x), and – furthermore – to: (1) ∀a ∈ ρ(x) : ρ(z) ⊆ κ(µ)(a) ∧ (ι, , ρ, κ) |=µP1, (2a) ∀a ∈ ρ(x) : κ(µ)(a) ⊆ ρ(w) ∧ (ι, , ρ, κ) |=µP2 and (2b) ∀a ∈ ρ(z) : (a ∈ ι(µ) and ∀µ0 ∈ ι(∗) : b ∈ ι(µ0) then comp((µ)(a), (µ0)(b)) implies that κ(µ0)(b) ⊆ ρ(y), (3) ∧ (ι, , ρ, κ) |=µP3. Since ρ(x) = {x} and ρ(z) = {z}, (1) is equivalent to z ∈ ρ(x) ⊆ κ(µ)(x) and (2a) to κ(µ)(x) ⊆ ρ(w), and therefore we have that z ∈ ρ(w). By Lemma A.1 and (1), we have that (ι, , ρ, κ) |=µP1{z/w}, by (2a) and (3) we have that (ι, , ρ, κ) |=µP1{z/w}| P2| P3. We can obtain the required (ι, , ρ, κ) |=∗ B[(ν ˜u)(P1{z/w}| P2| P3)]µ.
Case (Inter). Let B be β(x : Γ)B∗1[P ]µP||β(y : ∆)B∗2[Q]µQ, where P ≡ (ν ˜u)(x(w).P1| P2), Q ≡ (ν ˜v)(yhzi.Q1| Q2), and B0 be B∗1[(ν ˜u)(P1| P2)]µP||B2∗[(ν ˜v)(Q1| Q2)]µQ, with Γ ∩ ∆ 6= ∅ and x, z /∈ ˜u and y, z /∈ ˜v.
We have to prove that (ι, , ρ, κ) |=∗ B0. (ι, , ρ, κ) |=∗ B in particu-lar, implies that µP, µQ ∈ ι(∗), (1) x ∈ ι(µP), GP = ρ(Γ) ∈ (µP)(x) and (ι, , ρ, κ) |=∗ B∗1[P ]µP; (2) y ∈ ι(µQ), GQ = ρ(∆) ∈ (µQ)(y) and (ι, , ρ, κ) |=∗ B∗2[Q]µQ; (3) ∀a ∈ ρ(x) : a ∈ ι(µ) and ∀µ0 ∈ ι(∗) : b ∈ ι(µ0) then since GP ∩ GQ 6= ∅, comp((µ)(a), (µ)(b)) implies that κ(µ0)(b) ⊆ ρ(y), and (ι, , ρ, κ) |=µP1 (4) ∀a ∈ ρ(y) : ρ(z) ⊆ κ(µ)(a) ∧ (ι, , ρ, κ) |=µQ1. Since ρ(x) = {x} and ρ(z) = {z}, we have that a = x ∈ ι(µ) and that z ⊆ κ(µ)(y).
Condition (3) is verified with b = y and then {z} = κ(µQ)(y) ⊆ ρ(w), i.e. z ∈ ρ(w).
By LemmaA.1 and the fact that z ∈ ρ(w), we have that (ι, , ρ, κ) |=µP P1{z/w}, and also that (ι, , ρ, κ) |=µP (ν ˜u)(P1| P2) and (ι, , ρ, κ) |=µQ (ν ˜v)(Q1| Q2) and finally the required (ι, , ρ, κ) |=∗ B∗1[(ν ˜u)(P1| P2)]µP||B2∗[(ν ˜v)(Q1| Q2)]µQ.
Case (Hide). Let B be B∗β(x : Γ)[P ]µ, with P ≡ (ν ˜u)(hide(x).P1| P2) and B0 be B∗βh(x : Γ)[(ν ˜u)(P1| P2)]µ. We have to prove that (ι, , ρ, κ) |=∗B0. (ι, , ρ, κ) |=∗ B in particular, implies that µ ∈ ι(∗), x ∈ ι(µ), ρ(Γ) ∈ (µ)(x) and that ∀a ∈ ρ(x) : ah ∈ ι(µ) ∧ (ι, , ρ, κ) |=µP . Since x is a value, then ρ(x) = {x}
and the above amounts to xh ∈ ι(µ). From this, from ρ(Γ) ∈ (µ)(x) and (ι, , ρ, κ) |=µP , we can conclude that (ι, , ρ, κ) |=µB∗βh(x : Γ)[(ν ˜u)(P1| P2)]µ. Case (Par) follows directly from the induction hypothesis.
Case (Struct) uses LemmaA.2.
2 Theorem A.4 (Outputs in κ)
(i) If (ι, , ρ, κ) |=∗ B and B →∗ B0 → B00, such that the last transition B0 → B00 is derived using the rule (Intra) on the output prefix xhzi in the box labelled µ, then z ∈ κ(µ)(x).
(ii) If (ι, , ρ, κ) |=∗ B and B →∗ B0 → B00, such that the last transition B0 → B00 is derived using the rule (Inter) on the output prefix yhzi in the box labelled µ, then z ∈ κ(µ)(y).
Proof. By induction on the length of the computation. By TheoremA.3, we have that (ι, , ρ, κ) |=∗ B0. Therefore the proof proceeds by induction on the transition rules used to derive B0→ B00.
[(i)]
Case (Intra). If this rule is applied, than B0 is in the form
B0[(ν ˜u)(x(w).P1| xhzi.P2| P3)]µ. Since (ι, , ρ, κ) |=∗ B0, we have that, in particular, (ι, , ρ, κ) |=µxhzi.P2 and also the required z ∈ κ(µ)(x), because ρ(x) = x and ρ(z) = z.
Cases (Inter), (Expose), (Hide), (Unhide). Transitions that use any of these rules will not use (Intra) and are therefore disregarded.
Cases (Par), (Struct) are straightforward, by applying the induction hypotheses.
[(ii)]
Case (Inter). If this rule is applied, than B0 is in the form β(x : Γ)B∗1[(ν ˜u)(x(w).P1| P2)]µP||β(y : ∆)B∗2[(ν ˜v)(yhzi.Q1| Q2)]µQ. Since (ι, , ρ, κ) |=∗ B0, we have that, in particular, (ι, , ρ, κ) |=µQ yhzi.Q1 and also the required z ∈ κ(µ)(x), because ρ(y) = y and ρ(z) = z.
Cases (Intra), (Expose), (Hide), (Unhide). Transitions that use any of these rules will not use (Intra) and are therefore disregarded.
Cases (Par), (Struct) are straightforward, by applying the induction hypotheses.2 In a completely similar way can be proved the following theorem, whose proof we skip.
Theorem A.5 (Values in ρ) If (ι, , ρ, κ) |=∗ B and B →∗ B0 → B00, such that B00 is either in the form B[P {v/x}|P0] or in the form B1[P {v/x}|P0]||B2[Q] then v ∈ ρ(x).
Theorem A.6 (Binders in ι and )
If (ι, , ρ, κ) |=∗B and B →∗ B0 → B00, such that the last transition is derived using an interface rule (Expose) or (Hide) or (Unhide) on the binder x with type Γ and B00 includes B[P ]µ and if (ˆx : Γ) occurs in B00 then ˆx ∈ ι(µ) ∧ ρ(Γ) ∈ (µ).
Proof. By induction on the length of the computation. By TheoremA.3, we have that (ι, , ρ, κ) |=∗ B0. Therefore the proof proceeds by induction on the transition rules used to derive B0→ B00.
Cases (Expose), (Hide) and (Unhide) are similar.
Case (Expose). If this rule is applied, than B0 is in the form B∗[(ν ˜u)(expose(x, Γ).P1| P2)]µ. Since (ι, , ρ, κ) |=∗B0 and therefore (ι, , ρ, κ) |=µ(ν ˜u)(expose(x, Γ).P1| P2) then, in particular, we have that x ∈ ι(µ) and ρ(Γ) ∈ (µ).
Cases (Expose), (Hide) and (Unhide) are similar.
Cases (Intra) and (Inter). Transitions that use any of these rules will not change the interface and are therefore disregarded.
Cases (Par), (Struct) are straightforward, by applying the induction hypotheses.
2
A.2 Existence of Estimates Theorem A.7 (Moore Family)
For any beta-process B the set {(ι, , ρ, κ)| (ι, , ρ, κ) |=∗ B} is a Moore family.
Proof. We proceed by structural induction on B. Let I a set of proposed estimates
and let J and (ιj, j, ρj, κj) such that J ⊆ I = {(ιj, j, ρj, κj)| j ∈ J }. Next, define (ι0, 0, ρ0, κ0) = uJ
We have to check that (ι0, 0, ρ0, κ0) |=∗ B. We just consider one case. The others are similar.
Case (β(x : Γ)B[P ]µ). Since ∀j ∈ J : (ιj, j, ρj, κj) |=∗ β(x : Γ)B[P ]µ, then
∀j ∈ J : x ∈ ιj(µ) and ρj(Γ) ∈ j(µ)(x) ∧ (ιj, j, ρj, κj) |=∗ B[P ]µ
Using the induction hypothesis and the fact that ι0 and 0are obtained in a pointwise way, we then obtain that
x ∈ ι0(µ), ρ(Γ) ∈ 0(µ)(x) and that (ι0, 0, ρ0, κ0) |=∗B[P ]µ
thus establishing the required (ι0, 0, ρ0, κ0) |=∗ β(x : Γ)B[P ]µ. 2 Theorem A.8 (Existence of Estimates)
For any beta-process B, there exists an analysis result (ι, , ρ, κ) such that (ι, , ρ, κ) |=∗ B.
Proof. The thesis follows from Theorem A.7, because a Moore family is never empty, then there always exists an estimate satisfying the rules in Table2. 2 A.3 Correctness of the Extended Analysis
Theorem A.9 (Label Correspondence) If B→ Bφ 0 and (ι, σ, , ρ, κ) |=∗ψ B then
• if φ = hhµ xhzi, µ x(w)i; ci then hµ ahdi@σ(µ), µ a(y)@σ(µ)i ∈ ψ, with (c; s) ∈ σ(µ);
• if φ = hhµ0 yhzi, µ1 x(w)i; ci then hµ0 bhdi@σ(µ0), µ1 a(y)@σ(µ1)i ∈ ψ, with (c0; s) ∈ σ(µ0), (c1; s) ∈ σ(µ1), and cl = c1−l or cl= c1−l, n and c = cl;
• if φ = hµ a; ci then hµ a@σ(µ)i ∈ ψ, with (c; s) ∈ σ(µ);
• if φ = hhµ in(x), µ0 move(y)i; c, ni then hµ in(b)@(c, n; i), µ0 move(a)@(c; i)i ∈ ψ;
• if φ = hhµ out(x), µ0 move(y)ic, ni then hµ out(b)@(c, n; i), µ0 move(a)@(c, n; i)i ∈ ψ.
The proof coincides with that of TheoremA.10. In fact, ψ just collects information recorded in the remaining components of the analysis.
Theorem A.10 (Subject reduction)
If B→ Bφ 0 and (ι, σ, , ρ, κ) |=∗ψ B then also (ι, σ, , ρ, κ) |=∗ψ B0.
Proof. [Case (In)]. Let B be β(x : Γ)B∗1[P ]µc,n;bP ||β(y : ∆)B∗2[Q]µc;iQ, with P = in(x).P1| P2 and Q = move(y).Q1| Q2 and with ∆ ∩ Γ = ∅.
Let B0 be β(x : Γ)B∗1[P1| P20]µc,n;bP ||β(y : ∆)B∗2[Q1| Q2]µc,n;iQ and φ = hµP in(x), µQ move(y); c, ni. We have to prove that if (ι, σ, , ρ, κ) |=∗ψ B then (ι, σ, , ρ, κ) |=∗ψ B0. (ι, σ, , ρ, κ) |=∗ψ B implies that:
(i) x ∈ ι(µP), (c, n; b) ∈ σ(µP), and (ι, σ, , ρ, κ) |=µψ Pi, with i = 1, 2;
(ii) in(x) ∈ ι(µP);
(iii) y ∈ ι(µQ), and (ι, σ, , ρ, κ) |=µψ Qi, with i = 1, 2;
(iv) (c; s) ∈ σ(µQ) and (µP)(x) ∩ (µQ)(y) 6= ∅ (by Therorem A.6) (v) (c, n; s) ∈ σ(µQ) and hµP in(x)@(c, n; b), µQ move(y)@(c; i)i ∈ ψ
Now, by (i) we have that (ι, σ, , ρ, κ) |=∗ψ β(x : Γ)B∗1[P1| P20]µc,n;bP . By (iii) and (v) we have that (ι, σ, , ρ, κ) |=∗ψ β(y : ∆)B∗2[Q1| Q2]µc,n;iQ , and therefore the thesis.
Furthermore, note that hµP in(x)@(c, n; b), µQ move(y)@(c; i)i ∈ ψ corresponds to φ = hµP in(x), µQ move(y); c, ni. We recall that in the dynamic label, the com-partment identifier is the one annotating the sub-comparment.
[Case (Out)]. The proof is analogous to the above one.
The other cases are similar to the ones proved in TheoremA.9. 2