Abstract interpretation and types for systems biology

Abstract : Abstract interpretation is a theory of abstraction that has been introduced for the analysis of programs. In particular, it has proved useful for organizing the multiple semantics of a given programming language in a hierarchy corresponding to different detail levels, and for defining type systems for programming languages and program analyzers in software engineering. In this paper, we investigate the application of these concepts to systems biology formalisms. More specifically, we consider the Systems Biology Markup Language SBML, and the Biochemical Abstract Machine BIOCHAM with its differential, stochastic, discrete and boolean semantics. We first show how all of these different semantics, except the differential one, can be formally related by simple Galois connections. Then we define three type systems: one for checking or inferring the functions of proteins in a reaction model, one for checking or inferring the activation and inhibition effects of proteins in a reaction model, and another one for checking or inferring the topology of compartments or locations. We show that the framework of abstract interpretation elegantly applies to the formalization of these further abstractions, and to the implementation of linear or quadratic time type checking as well as type inference algorithms. Furthermore, we show a theorem of independence of the graph of activation and inhibition effects from the kinetic expressions in the reaction model, under general conditions. Through some examples, we show that the analysis of biochemical models by type inference provides accurate and useful information. Interestingly, such a mathematical formalization of the abstractions commonly used in systems biology already provides some guidelines for the extensions of biochemical reaction rule languages.
Document type :
Journal articles
Complete list of metadatas

Cited literature [45 references]  Display  Hide  Download

https://hal.inria.fr/hal-01431355
Contributor : Sylvain Soliman <>
Submitted on : Tuesday, January 10, 2017 - 4:57:57 PM
Last modification on : Thursday, October 17, 2019 - 11:15:08 AM
Long-term archiving on : Tuesday, April 11, 2017 - 4:26:54 PM

File

FS07tcs.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

François Fages, Sylvain Soliman. Abstract interpretation and types for systems biology. Theoretical Computer Science, Elsevier, 2008, 403 (1), pp.52--70. ⟨10.1016/j.tcs.2008.04.024⟩. ⟨hal-01431355⟩

Share

Metrics

Record views

356

Files downloads

410