![]() Mizera, Andrzej ![]() ![]() ![]() in IEEE/ACM Transactions on Computational Biology and Bioinformatics (2018), 15(5), 1525-1537 Probabilistic Boolean networks (PBNs) is a well-established computational framework for modelling biological systems. The steady-state dynamics of PBNs is of crucial importance in the study of such ... [more ▼] Probabilistic Boolean networks (PBNs) is a well-established computational framework for modelling biological systems. The steady-state dynamics of PBNs is of crucial importance in the study of such systems. However, for large PBNs, which often arise in systems biology, obtaining the steady-state distribution poses a significant challenge. In this paper, we revive the two-state Markov chain approach to solve this problem. This paper contributes in three aspects. First, we identify a problem of generating biased results with the approach and we propose a few heuristics to avoid such a pitfall. Secondly, we conduct an extensive experimental comparison of the extended two-state Markov chain approach and another approach based on the Skart method. We analyse the results with machine learning techniques and we show that statistically the two-state Markov chain approach has a better performance. Finally, we demonstrate the potential of the extended two-state Markov chain approach on a case study of a large PBN model of apoptosis in hepatocytes. [less ▲] Detailed reference viewed: 166 (7 UL)![]() Yuan, Qixia ![]() Doctoral thesis (2017) Systems biology combines developments in the fields of computer science, mathematics, engineering, statistics, and biology to study biological networks from a holistic point of view in order to provide a ... [more ▼] Systems biology combines developments in the fields of computer science, mathematics, engineering, statistics, and biology to study biological networks from a holistic point of view in order to provide a comprehensive, system level understanding of the underlying system. Recent developments in biological laboratory techniques have led to a slew of increasingly complex and large biological networks. This poses a challenge for formal representation and analysis of those large networks efficiently. To understand biology at the system level, the focus should be on understanding the structure and dynamics of cellular and organismal function, rather than on the characteristics of isolated parts of a cell or organism. One of the most important focuses is the long-run dynamics of a network, as they often correspond to the functional states, such as proliferation, apoptosis, and differentiation. In this thesis, we concentrate on how to analyse long-run dynamics of biological networks. In particular, we examine situations where the networks in question are very large. In the literature, quite a few mathematical models, such as ordinary differential equations, Petri nets, and Boolean networks (BNs), have been proposed for representing biological networks. These models provide different levels of details and have different advantages. Since we are interested in large networks and their long-run dynamics, we need to use ``coarse-grained" level models that focus on the system behaviour of the network while neglecting molecular details. In particular, we use probabilistic Boolean networks (PBNs) to describe biological networks. By focusing on the wiring of a network, a PBN not only simplifies the representation of the network, but it also captures the important characteristics of the dynamics of the network. Within the framework of PBNs, the analysis of long-run dynamics of a biological network can be performed with regard to two aspects. The first aspect lies in the identification of the so-called attractors of the constituent BNs of a PBN. An attractor of a BN is a set of states, inside which the network will stay forever once it goes in; thus capturing the network's long-term behaviour. A few methods have been discussed for computing attractors in the literature. For example, the binary decision diagram based approach and the satisfiability based approach. These methods, however, are either restricted by the network size, or can only be applied to synchronous networks where all the elements in the network are updated synchronously at each time step. To overcome these issues, we propose a decomposition-based method. The method works in three steps: we decompose a large network into small sub-networks, detect attractors in sub-networks, and recover the attractors of the original network using the attractors of the sub-networks. Our methods can be applied to both asynchronous networks, where only one element in the network is updated at each time step, and synchronous networks. Experimental results show that our proposed method is significantly faster than the state-of-the-art methods. The second aspect lies in the computation of steady-state probabilities of a PBN with perturbations. The perturbations of a PBN allow for a random, with a small probability, alteration of the current state of the PBN. In a PBN with perturbations, the long-run dynamics is characterised by the steady-state probability of being in a certain set of states. Various methods for computing steady-state probabilities can be applied to small networks. However, for large networks, the simulation-based statistical methods remain the only viable choice. A crucial issue for such methods is the efficiency. The long-run analysis of large networks requires the computation of steady-state probabilities to be finished as soon as possible. To reach this goal, we apply various techniques. First, we revive an efficient Monte Carlo simulation method called the two-state Markov chain approach for making the computations. We identify an initialisation problem, which may lead to biased results of this method, and propose several heuristics to avoid this problem. Secondly, we develop several techniques to speed up the simulation of PBNs. These techniques include the multiple central processing unit based parallelisation, the multiple graphic processing unit based parallelisation, and the structure-based parallelisation. Experimental results show that these techniques can lead to speedups from ten times to several hundreds of times. Lastly, we have implemented the above mentioned techniques for identification of attractors and the computation of steady-state probabilities in a tool called ASSA-PBN. A case-study for analysing an apoptosis network with this tool is provided. [less ▲] Detailed reference viewed: 158 (37 UL)![]() ; ; Yuan, Qixia ![]() in Proceedings of 20th International Conference on Fundamental Approaches to Software Engineering (2017) Detailed reference viewed: 149 (11 UL)![]() Mizera, Andrzej ![]() ![]() in Proceedings of the 3rd International Symposium on Dependable Software Engineering: Theories, Tools, and Applications (2017) Detailed reference viewed: 166 (5 UL)![]() Mizera, Andrzej ![]() ![]() ![]() in Proceedings of the 31st ACM Symposium on Applied Computing (2016, April) Probabilistic Boolean networks (PBNs) is a widely used computational framework for modelling biological systems. The steady-state dynamics of PBNs is of special interest in the analysis of biological ... [more ▼] Probabilistic Boolean networks (PBNs) is a widely used computational framework for modelling biological systems. The steady-state dynamics of PBNs is of special interest in the analysis of biological machinery. However, obtaining the steady-state distributions for such systems poses a significant challenge due to the state space explosion problem which arises in the case of large PBNs. The only viable way is to use statistical methods. In the literature, the two-state Markov chain approach and the Skart method have been proposed for the analysis of large PBNs. However, the sample size required by both methods is often huge in the case of large PBNs and generating them is expensive in terms of computation time. Parallelising the sample generation is an ideal way to solve this issue. In this paper, we consider combining the Gelman & Rubin method with either the two-state Markov chain approach or the Skart method for parallelisation. The first method can be used to run multiple independent Markov chains in parallel and to control their convergence to the steady-state while the other two methods can be used to determine the sample size required for computing the steady-state probability of states of interest. Experimental results show that our proposed combinations can reduce time cost of computing stead-state probabilities of large PBNs significantly. [less ▲] Detailed reference viewed: 173 (9 UL)![]() Yuan, Qixia ![]() ![]() in Science China Information Sciences (2016), 59(8), 0801011-08010116 Detailed reference viewed: 189 (26 UL)![]() Mizera, Andrzej ![]() ![]() ![]() Poster (2016) Detailed reference viewed: 87 (7 UL)![]() Mizera, Andrzej ![]() ![]() ![]() in Proceedings of 14th International Conference on Computational Methods in Systems Biology (2016) Detailed reference viewed: 143 (5 UL)![]() Mizera, Andrzej ![]() ![]() ![]() in Proceedings of 14th International Conference on Computational Methods in Systems Biology (2016) Detailed reference viewed: 206 (10 UL)![]() Mizera, Andrzej ![]() ![]() ![]() in Proceedings of the 13th International Symposium on Automated Technology for Verification and Analysis (ATVA'15) (2015) Detailed reference viewed: 160 (10 UL)![]() ; Yuan, Qixia ![]() ![]() in Proceedings of the 7th Asia-Pacific Symposium on Internetware (2015) Boolean networks are an important formalism for modelling biological systems and have attracted much attention in recent years. An important direction in Boolean networks is to exhaustively find ... [more ▼] Boolean networks are an important formalism for modelling biological systems and have attracted much attention in recent years. An important direction in Boolean networks is to exhaustively find attractors, which represent steady states when a biological network evolves for a long term. In this paper, we propose a new approach to improve the efficiency of BDD-based attractor detection. Our approach includes a monolithic algorithm for small networks, an enumerative strategy to deal with large networks, and two heuristics on ordering BDD variables. We demonstrate the performance of our approach on a number of examples, and compare it with one existing technique in the literature. [less ▲] Detailed reference viewed: 140 (6 UL)![]() Mizera, Andrzej ![]() ![]() ![]() in Proceedings of 19th IEEE Conference on Engineering of Complex Computer Systems (2014) Detailed reference viewed: 148 (11 UL)![]() Yuan, Qixia ![]() ![]() ![]() in Transactions on Computational Systems Biology (2012), XIV Detailed reference viewed: 180 (16 UL)![]() Yuan, Qixia ![]() ![]() ![]() in Proceedings of the 3rd Workshop on Computational Models for Cell Processes (2011), EPTCS 67 Detailed reference viewed: 175 (13 UL) |
||