Algorithms for Analysis, Inference, and Control of Boolean Networks

The following sections are included:

• Preface
• Contents

The Boolean network (BN) is a mathematical model of genetic networks and is based on Boolean functions. Boolean functions are functions on the Boolean domain that consists of Boolean values, 0 and 1. Boolean functions also give a foundation of computer science because signals in computers are represented by 0 and 1. Among various aspects of BNs, this book focuses on algorithms for BNs. Computational complexity is a very important factor of algorithms. And, in this book, we employ algorithms and techniques for the Boolean satisfiability problem, integer linear programming, and graphs. Therefore, in this chapter, we review definitions and fundamental properties on Boolean functions, computational complexity, the Boolean satisfiability problem, integer linear programming, and graphs. Readers familiar with these topics can skip this chapter.

The Boolean network (BN) is a mathematical model of genetic networks. It has a long history beginning from studies by Kauffman in 1960s [Kauffman (1969a,b)] and extensive studies have been done. In this chapter, we review the definition of the BN, important concepts, and some of their basic mathematical properties.

In this chapter and the following two chapters, we consider the problem of detection of attractors. As discussed in Chapter 2, extensive studies have been done on the length and distribution of attractors in the NK model, motivated by a possible correspondence between attractors and cell types. Since Boolean models of various biological systems have been constructed, it is also important to detect and/or enumerate attractors in a given BN.

Attractors can be enumerated once we have a state transition diagram. To this end, it is enough to enumerate cycles in the diagram since attractors correspond to cycles. For example, three cycles in Fig. 2.2 correspond to attractors. Enumeration of cycles can be done by identifying strongly connected components, which can be done in time linear to the size of the diagram by using the technique called depth first search, assuming that each elementary operation on n-bit words can be done in a constant time (which may not be appropriate in this case). However, the state transition diagram consists of 2ⁿ nodes and 2ⁿ edges. Therefore, this approach would require Ω(2ⁿ) time. If n is not large (e.g., n < 30), it may be possible to apply this direct approach to enumerate all attractors. However, if n is large, it is impossible to store and analyze the state transition diagram. Therefore, we need more efficient methods.

In this chapter, we focus on BNs with maximum indegree K and present algorithms for detection of a singleton attractor and enumeration of singleton and periodic attractors with short periods.

In Chapter 3, we have seen several algorithms for detecting and/or enumerating singleton and periodic attractors. However, unless there is any constraint on the maximum indegree, the worst case time complexity is at least O(2ⁿ). Therefore, it is reasonable to ask whether it is possible to develop an O((2 − δ)ⁿ) time algorithm when there is no constraint on the maximum indegree, where δ > 0 is some constant. It seems quite difficult to develop such an algorithm. However, it is possible if there exist some constraint on types of Boolean functions or the network structure. This chapter presents such algorithms for detection of a singleton attractor.

In Chapter 4, we have seen several algorithms for Singleton Attractor Detection with special classes of BNs. It is reasonable to try to extend the techniques in those algorithms to Periodic Attractor Detection. However, it is quite difficult to develop o(2ⁿ) time algorithms for Periodic Attractor Detection with long periods. Although we have not given a formal proof, it seems that (the decision problem version of) detection of a long periodic attractor is PSPACE-complete because the reachability problem on BNs is known to be PSPACE-complete [Barrett et al. (2006)]. Therefore, we focus on Periodic Attractor Detection with short periods in this chapter.

In 1990s, DNA microarray and DNA chip technologies were developed, which enabled us to observe time series data of expression of several thousands (or more) of genes to some extent. Recently, the next generation DNA sequencing technology can also be used for the same purpose. Motivated by these innovations, extensive studies have been done on inference of gene regulatory networks from gene expression time series data. The BN model has also been employed for solving this inference problem. In this chapter, we review some fundamental algorithms for inferring a BN from Boolean time series data and fundamental results on the number of expression data that are required to uniquely identify the underlying BN. Although time series data can be obtained as mentioned above, it is difficult to get a lot of time series data and time series data usually contain large noise. Instead, it is much easier to obtain gene expression data in steady states, which may correspond to attractors. Therefore, some studies have been done on inference of gene regulatory networks from attractors. In the latter sections of this chapter, we review some of theoretical results on this problem.

One of the major goals of systems biology is to develop control theory for biological systems [Kitano (2002, 2004)]. Such a development is important both from a theoretical viewpoint and from a practical viewpoint. From a theoretical viewpoint, biological systems are complex and contain highly non-linear components and thus existing methods in control theory cannot be directly applied to control of biological systems. From a practical viewpoint, control of cells may be useful for systems-based drug discovery and cancer treatment [Kitano (2002, 2004)]. Therefore, it is an important and interesting challenge to develop theory and methods for control of biological systems. Since BNs are highly non-linear systems, it is reasonable to try to develop methods for control of BNs. In this chapter, we describe algorithms and complexity results on control of BNs.

In this chapter, we consider two other important problems on BNs, predecessor detection and minimum observer detection for attractors, both of which are related to BN Control. The problem of predecessor detection is, given a BN and its state, to find its predecessor, a state that transits into the given state. This problem can be used as a pre-process of BN Control because if the desired state does not have a predecessor, there is no control sequence for driving the BN to this state. It may also be useful to identify the basin of attraction for a given attractor by enumerating predecessor states recursively [Wuensche (2000)]. Observability is an important concept in control theory and is a dual of controllability. A system with observer nodes is called observable if the system's complete internal state at any given time step can be reconstructed from time-series data of observer nodes. Although extensive studies have been done on the observability of BN and related models using semi-tensor product [Cheng et al. (2009, 2011); Laschov et al. (2013); Wu et al. (2017); Zhang and Zhang (2013)], it is also known that many nodes are required to observe previous states in a BN [Li et al, (2015)]. Therefore, in this chapter, we consider the problem of finding a minimum set of nodes using which given attractors are discriminated. Since attractors are often regarded as cell types, this problem has a potential application in finding marker genes for discriminating cell types.

We have seen discrete and combinatorial approaches for analysis and control of BNs so far. On the other hand, many studies have also been done by using algebraic approaches. Extensive studies have been especially done using the semi-tensor product (STP) [Cheng (2009); Cheng et al. (2009, 2011, 2012)], which is a generalization of the conventional matrix product. In this chapter, we review the STP and some fundamental results on STP-based analysis of BNs.

BNs have been mainly used for modeling and analyzing genetic networks. However, BNs have also been used for modeling and analyzing other types of biological networks. In this chapter, we describe BN-based modeling and analysis of metabolic networks.

The Boolean network (with synchronous update) is a deterministic model: one regulation rule (one Boolean function) is assigned to each node and thus the next state of the network is uniquely determined from the current state. However, real biological networks do not necessarily work deterministically due to factors such as environment noise, intrinsic stochasticity of biological systems, and unknown mechanisms. Therefore, various stochastic extensions of the BN have been proposed. Among them, the Probabilistic Boolean Network (PBN) is the most extensively studied model [Shmulevich et al. (2002); Shmulevich and Dougherty (2010)]. In this chapter, we describe the definition of PBN and its basic properties.

In Chapter 6, we have seen that a BN with bounded indegree can always be identified if enough number of samples are given. It is reasonable to try to get similar results for a PBN. However, it is much harder to uniquely determine a PBN from samples because PBN is a probabilistic system. In this Chapter, we describe a practical method for inference of a PBN and theoretical methods for identification of a PBN and its variant. Furthermore, it will be shown that there are cases in which it is impossible to uniquely determine a PBN that is consistent with given samples even if all possible samples are given.

In Chapter 7, control of BNs was discussed. Historically, studies on control of PBNs precede those on BNs [Datta et al. (2003)]. In this chapter, we describe a basic version of the control problem on the PBN, a dynamic programming algorithm for the problem, and a result showing computational hardness of the problem.

The following sections are included:

• Bibliography
• Index