Paper Info
Title
Static analysis of biological regulatory networks dynamics using abstract interpretation
Abstract
The analysis of the dynamics of Biological Regulatory Networks (BRNs) requires innovative methods to cope with the state-space explosion. This paper settles an original approach for deciding reachability properties based on Process Hitting, which is a framework suitable for modelling dynamical complex systems. In particular, Process Hitting has been shown to be of interest in providing compact models of the dynamics of BRNs with discrete values. Process Hitting splits a finite number of processes into so-called sorts and describes the way each process is able to act upon (that is, to 'hit') another one (or itself) in order to 'bounce' it as another process of the same sort with further actions. By using complementary abstract interpretations of the succession of actions in Process Hitting, we build a very efficient static analysis to over-and under-approximate reachability properties, which avoids the need to build the underlying states graph. The analysis is proved to have a low theoretical complexity, in particular when the number of processes per sorts is limited, while a very large number of sorts can be managed. This makes such an approach very promising for the scalable analysis of abstract complex systems. We illustrate this through the analysis of a large BRN of 94 components. Our method replies quasi-instantaneously to reachability questions, while standard model-checking techniques regularly fail because of the combinatoric explosion of behaviours.
Year
DOI
Venue
2012
10.1017/S0960129511000739
Mathematical Structures in Computer Science
Keywords
Field
DocType
efficient static analysis,finite number,combinatoric explosion,complementary abstract interpretation,abstract complex system,large number,scalable analysis,reachability property,under-approximate reachability property,biological regulatory networks dynamic,process hitting
Complex system,Discrete mathematics,Work in process,Computer science,Abstract interpretation,sort,Static analysis,Reachability,Theoretical computer science,Large numbers,Artificial intelligence,Scalability
Journal
Volume
Issue
ISSN
22
4
0960-1295
Citations 
PageRank 
References 
5
0.48
8
Authors
3
Name
Order
Citations
PageRank
Loïc Paulevé120418.68
Morgan Magnin211512.71
Olivier Roux3102.44