Compositional Techniques for Asynchronous Boolean Networks

Abstract

Boolean networks are widely used as a qualitative modelling approach for analysing complex systems, particularly in biological applications. They provide a range of techniques including identifying attractors (key cyclic behaviour) that represent an important phenomenon in biological systems. Two main semantics are usually considered in Boolean networks: synchronous, where entities update simultaneously, and asynchronous, where each entity updates independently. However, their application is limited by the state space explosion problem. Due to these issues, compositional approaches have been considered, and in particular, a new novel composition approach for synchronous Boolean networks was presented based on emerging entities between Boolean networks using Boolean connectives.

This thesis is set up to develop a general compositional theory for asynchronous Boolean networks. As a starting point, we investigate the existing compositional framework for synchronous Boolean networks as applied to the asynchronous settings, and new interesting results and compositional techniques are developed. This work helps to highlight the major differences between the two Boolean network semantics. Since interference is a key factor in this compositional theory, we formalise the crucial and novel asynchronous interference state graph. Importantly, we show it bounds the behaviour of submodels under a composition. We develop new compositional analysis techniques for the behaviour of composed models and a range of new results for the asynchronous setting is developed with respect to behaviour preservation. This involved adapting the synchronous behaviour preservation results to an asynchronous nature and developing new behaviour preservation results that are tailored for asynchronous semantics. Furthermore, we explore whether behaviour in an asynchronous interference state graph of a submodel can occur in a composition.

Given the importance of attractor analysis in Boolean networks, we develop compositional techniques for detecting attractors under asynchronous composition. We start by focusing on a compositional approach for identifying point attractors, which allows us to develop the insight and ideas necessary to identify all attractors in a composition. The general approach we develop is based on identifying candidates for submodels, which are cyclic structures that may contain escape steps that depend on interference. These candidates can potentially be composed to form attractors. We investigate the practical aspects of the theoretical techniques we developed for detecting attractors compositionally. We focus on generating candidates, which is a complex task involved in identifying attractors. This includes developing an algorithm for generating candidates, and a prototype tool was developed based on this algorithm. To address this complexity, we consider an approach for bounding the search space of candidates by setting an upper bound on the size of attractors we need to identify.