Logic Programming for Boolean Networks

1 Introduction

Analysis of static and dynamic behavior of systems has become more and more important recently in various domains including systems biology. The Boolean network (BN) was proposed as a mathematical model of genetic networks and complex adaptive systems [Kauffman, 1969; 1993], and has been used as a discrete model of gene regulatory, signal transduction and protein interaction networks. The BN offers a simple yet powerful tool based on Boolean logic, and has a network structure consisting of nodes that correspond to genes or proteins. Each node in a BN takes a value of 1 or 0, meaning that the gene is or is not expressed. The value of a node at a time step is determined according to a regulation rule that is a Boolean function of the values of its input nodes at the previous time step. Computational properties and physical behaviors of the BN have been well studied in several fields including biology, physics, and bioinformatics, e.g., [Kauffman, 1993; Harvey and Bossomaier, 1997; Shmulevich et al., 2002; Gershenson, 2002; Irons, 2006; Akutsu et al., 2007; Garg et al., 2008; Remy and Ruet, 2008].

The stable states and dynamics of BNs are characterized by their attractors, which play an essential role in biological systems. The number and length of attractors of a random BN

have been analyzed computationally [Kauffman, 1993; Irons, 2006], yet not much work has been done from the viewpoint of logical inference systems. Recently, detection of attractors has been investigated in bioinformatics, and several studies connect attractor computation with various techniques based on advances of Propositional Satisfiability (SAT) and Answer Set Programming (ASP). These works can be classified into two types: those simulating dynamic behaviors of systems as trajectories of a series of inference [Fayruzov et al., 2009; Dubrova and Teslenko, 2010] or those computing attractors with the shortest length (i.e., point attractors) [Tamura and Akutsu, 2009; Melkman et al., 2010]. Those algorithms can be used for computing attractors of synchronous BNs, which are the simplest model of BNs.

In this paper, we formalize BNs as logic programs, and give a novel characterization of their attractors based on the semantics of logic programs. In contrast to the previous approaches that translate individual BN-related problems into equivalent theories, we will provide a direct encoding of BNs into logic programs and give a semantical characterization of BNs so that any BN-related problem can be analyzed based on this semantics. Then, several theoretical results and computational tools of logic programming can easily be transferred to BNs. In particular, point attractors of both synchronous and asynchronous Boolean networks are naturally characterized as supported models of logic programs [Apt et al., 1988], enabling us to apply SAT techniques to compute them. Thus, this work opens an integrated way to apply AI techniques to various computational problems of BNs.

On the other hand, from the viewpoint of logic programming, this work not only shows an important application of logic programming to systems biology and dynamic domains, but opens a new research direction toward a dynamic semantics of logic programs. In fact, most existing semantics regard a program as a static specification or an axiom set of a problem, and do not regard each rule as a transition function of a dynamic system. Considering the dynamic semantics in this work, physical behaviors that have been studied for BNs can be transferred to analyze dynamics of logic programs.

In the rest of this paper, Section 2 reviews the BN. Section 3 considers synchronous BNs and characterizes their attractors in terms of the semantics of corresponding logic programs. Section 4 represents asynchronous BNs and their attractors. Sections 5 and 6 discuss related and future work.

2 Boolean Networks

A Boolean network (BN) is a pair N = (V, F), where V = {v1, . . . , vn} is a finite set of nodes (or genes) and F = {f1, . . . , fn} is a corresponding set of Boolean functions (called regulation functions). Let vt i represent the state of vi at time t, which takes the value of either 1 (expressed) or 0 (not expressed). A vector (or state) v(t) = (vt1 , . . . , vtn ) is the overall expression level of all nodes in N at time step t. Note that there are 2n possible states for each time step. The state of a node vi at the next time step t + 1 is determined by vt+1 i = fi(vt i1 , . . . , vt ik ), where vi1 , . . . , vik are the set of input nodes of vi that are the genes directly connected to (or regulating) vi, and the number k is called the indegree of vi. When the indegree of vi is 0, no update is done at any time step. A BN is usually represented by a graph with two types of edges, which are positive and negative, in which v1 -→ v2 means that vt1 positively takes part in the regulation function for vt+1 2 and v1 --| v2 means that vt1 negatively takes part in the regulation function for vt+1 2 . An example of a BN is N1 = (V1, F1), where V1 = {p, q, r} and F1 is as follows.

The state of each gene can be updated either synchronously or asynchronously. In a synchronous BN (SBN), the states of all genes are updated simultaneously, while in an asynchronous BN (ABN) not all nodes are necessarily updated at a time. Each update of nodes in a BN N changes its state to another. A consecutive sequence of states obtained by state transitions is called a trajectory of N. State transition in an SBN is deterministic, and a trajectory starting from any state is uniquely determined. On the other hand, it is nondeterministic in an ABN. Let w ∈ {0, 1}n be a state, and R(w) be the states reachable in all trajectories starting fromw. Then, a set of states S is an attractor if R(w) = S holds for every w ∈ S [Garg et al., 2008]. If any trajectory from a node in an attractor S composes a single loop, w0, . . . , wp-1, wp(= w0), where p = |S| (1 ≤ p ≤ 2n), S is called a point attractor (or singleton attractor) when p = 1, and is called a cycle attractor when p > 1. The set of states that reach the same attractor is called its basin of attraction [Kauffman, 1993]. For example, when the BN N1 is synchronous, starting from the initial state v(0) = (0, 1, 1), the trajectory becomes (0, 1, 1), (1, 0, 1), (0, 1, 0), (1, 0, 1), . . ., and (1, 0, 1) → (0, 1, 0) → (1, 0, 1) is a cycle attractor (Figure 1 below). N1 has another, point attractor (0, 0, 1) (Figure 1 above) whose basin of attraction is {(1, 1, 1), (1, 1, 0), (1, 0, 0), (0, 0, 0), (0, 0, 1)}.

Note that any state in an SBN deterministically belongs to the basin of attraction of only one attractor, which is either a cycle attractor or a point attractor. Several interpretations of attractors have been reported in the literature [Kauffman, 1993; Shmulevich et al., 2002]; for example, each attractor represents a cell type, a type of memory, or a cellular state such as proliferation, apoptosis and differentiation.

3 Synchnorous BNs

In this section, we characterize synchronous BNs based on the semantics of logic programming. Our concern is to express regulation functions as rules of logic programs. To this end, we examine the appropriateness of existing semantics for logic programs.

3.1 Normal Logic Programs

We consider a first-order language and denote the Herbrand base (the set of all ground atoms) as A. A (normal) logic program (NLP) is a set of rules of the form

where A and Ai's are atoms (n ≥ m ≥ 0). For any rule R of the form (2), the atom A is called the head of R and is denoted as h(R), and the conjunction to the right of ← is called the body of R and we represent the positive and negative literals in the body as b+(R) = {A1, . . . ,Am} and b-(R) = {Am+1, . . . ,An}, respectively. Let ground(P) be the set of ground instances of all rules in an NLP P. An (Herbrand) interpretation I is a subset of A, and is called an (Herbrand) model of P if I satisfies all ground rules from P, that is, for any rule R ∈ ground(P), b+(R) ⊆ I and b-(R) ∩ I = ∅ imply h(R) ∈ I.

One of the most important criteria that any model theoretic semantics of logic programming should satisfy is the "supportedness". An Herbrand model I ⊆ A of an NLP P is a supported model [Apt et al., 1988] of P if for any ground atom A ∈ I, there exists a rule R ∈ ground(P) such that (a) h(R) = A, (b) b+(R) ⊆ I, and (c) b-(R) ∩ I = ∅. On the other hand, an Herbrand model I is a stable model [Gelfond and Lifschitz, 1988] of P if I is the least model of the program P I = {(h(R) ← ∧B∈b+ (R) B) | R ∈ ground(P), b-(R) ∩ I = ∅}. It is known that every stable model is a supported model [Marek and Subrahmanian, 1992]. For example, {p ← p, q ← ¬p}, has the supported models {p} and {q}, but only the latter is its stable model.

The following operational semantics of NLPs has been given in [Apt et al., 1988]. Given an NLP P and an interpretation I, the immediate consequence operator (or TP operator) TP : 2A → 2A is defined as TP(I) = {h(R) | R ∈ ground(P), b+(R) ⊆ I, b-(R) ∩ I = ∅}. Then, I is a model of P iff I is a pre-fixed point of TP , i.e., TP(I) ⊆ I. By definition, I is supported iff I ⊆ TP (I). Hence, I is a supported model of P iff I is a fixpoint of TP , i.e., TP(I) = I. Moreover, I is a model of Comp(P), which is the Clark's completion of P, iff TP(I) = I. This means that the supported models of P are precisely the models of Comp(P ).

We next show that the TP operator is useful to characterize attractors of synchronous BNs. As a related concept, the sequence of applications of the TP operator is considered by Blair et al. [1997]: For an Herbrand interpretation I, the orbit of I with respect to P is the sequence 〈TP k (I)〉k∈ω where TP 0 (I) = I and TP k+1 (I) = TP (TP k (I)) for k = 0, 1, . . ..

3.2 Characterizing Trajectories and Attractors

Our idea here is to express the regulation functions of a BN as rules of an NLP. To this end, we need to transform a Boolean function fi for a node vi in disjunctive normal form (DNF). Since this is always possible, in the following we assume that any regulation function is a DNF formula. Suppose a synchronous BN N = (V, F). For each node vi ∈ V , suppose its regulation function fi ∈ F is given as a DNF formula

where vi,j,k ∈ V and nj ≥ mj ≥ 0 for j = 1, . . . , li. Note that j can be 0 for a node vi, that is, vi has no input nodes. In this case, vi is called a constant node, and the indegree of a constant node is 0. Since there is no regulation function for a constant node, it stays in a constant state, i.e., always expresses or never expresses. Let VC ⊆ V be the constant nodes of N. Notice that VC is fixed and is smaller than V .

Now, for each fi ∈ F, let ρT (fi) be the rule set defined as either of the following sets:

where s(t) is the successor of t, i.e., t+1, and each vi ∈ V is now used as a predicate and Bi,j (t) is the formula obtained by replacing every vt i,j,k appearing in Bt i,j with vi,j,k(t). Then the NLP for N is given as PT (N) = ⋃vi∈V ρT (fi).

Let V (t) = {vi(t) | vi ∈ V }. Given a state v(t) = (vt1 , . . . , vtn ) at time step t, the interpretation Iv(t) ⊆ V (t) is defined as Iv(t) = {vi(t) ∈ V (t) | vt i = 1}. Then,

For example, for the BNN1 (1), the NLP PT (N1) is

p(s(t)) ← q(t), q(s(t)) ← p(t) ∧ r(t), r(s(t)) ←¬p(t). Now, given the initial state v(0) = (0, 1, 1), the orbit of Iv(0) with respect to PT (N1) is {q(0), r(0)}, {p(s(0))} ∪ {r(sk (0)) | k ≥ 1}, {q(s(s(0)))}∪{r(sk (0)) | (k = 1)∨(k ≥ 3)}, {p(s(s(s(0))))} ∪ {r(sk (0)) | k ≥ 1}, . . .. Then, the sequence 〈Iv(sk (0))〉k∈ω is {q(0), r(0)}, {p(s(0)), r(s(0))}, {q(s(s(0)))}, {p(s(s(s(0)))), r(s(s(s(0))))}, . . ., which simulates the trajectory of N1 from v(0).

Since each Iv(t) only contains atoms that are true at time step t, it turns out that the time argument can be omitted from each rule in ρT (fi). For each fi ∈ F given as (3), let ρ(fi) be the set of propositional rules obtained by deleting the time arguments (t) and s(t) from all literals appearing in ρT (fi), and define P(N) = ⋃vi∈V ρ(fi). Also, for any state v(t), put I t = {vi ∈ V | vt i = 1}.

Theorem 3.2 Let N be a synchronous BN, and v(t) any state. Then, the orbit of I t with respect to P(N) is precisely the trajectory of N starting from v(t).

Theorem 3.2 implies that every attractor can be obtained as an attracting cycle in an orbit of some initial state v(0), and in particular that a point attractor is given as a fixed point in such an orbit. For example, for N1, the propositional NLP P(N1) is now defined as

Then, given the initial state v(0) = (0, 1, 1), the orbit of I 0 with respect to P(N1) is {q, r}, {p, r}, {q}, {p, r}, . . ., which is exactly the trajectory of N1 from v(0), indicating that the repeat {p, r} → {q} → {p, r} corresponds to the cycle attractor of N1. Similarly, starting from (1, 1, 1), the orbit of {p, q, r} reaches the fixed point {r}, which corresponds to the point attractor (0, 0, 1) of N1.

3.3 Computing Point Attractors

To detect all attractors of a BN based on Theorem 3.2, we need to prepare Iv(0) for each initial state v(0), but there are 2n such possible initial states. Here, we show that detection of all point attractors of a BN can be characterized without specifying the set of initial states.

In the following, we will identify a state v(t) with an interpretation I t at a point attractor, and denote it as I whenever the time step is not important.

Theorem 3.3 Let N = (V, F ) be a synchronous BN. Then, I is a point attractor of N iff I is a supported model of P(N).

The proof of Theorem 3.3 can be established as follows: (i) By Theorem 3.2 and the definition of point attractors, I is a point attractor of N iff I = TP(N)(I) holds; (ii) I = TP(N)(I) iff I is a supported model of P(N) (see Section 3.1). Theorem 3.3 precisely characterizes the set of all point attractors of a BN in terms of one propositional program. As mentioned earlier, all supported models of an NLP P(N) can be enumerated as the models of its completion Comp(P(N)), which is given as follows.

Then, using a SAT solver, computation of point attractors can be automated by computing the models of the formula (5) 1 without testing for each initial state one by one. In Comp(P(N)), each completed formula for a non-constant node vi represents the logical equivalence between the state of vi and its previous state. On the other hand, the additional rule (vi ← vi) in ρ(fi) for each constant node vi ∈ VC preserves the truth value of vi in an initial state v(0) through the orbit of Iv(0). This rule becomes the formula (vi ↔ vi) in Comp(P (N)), and can be equivalently removed from (5).

1 The same translation from a synchronous BN into SAT has been directly suggested in [Tamura and Akutsu, 2009] without getting through the semantics of logic programming.

The rule (vi ← vi) for each vi ∈ VC thus prevents the derivation of ¬vi in Comp(P(N)), and is actually indispensable in obtaining the supported models as the next example shows.

Example 3.1 Consider the next BN N2 = ({p, q, r}, F2):

In N2, q is a constant node. Let P2 be the set of rules:

The supported model of P2 is {p, r}, which corresponds to the point attractor (1, 0, 1). However, another point attractor (1, 1, 0) cannot be obtained from P2, since {p, q} is not a supported model of P2. We see that {p, q} is a supported model of P (N2) = P2 ∪ { q ← q }.

In Example 3.1, P(N2) has no stable model. In fact, any tautological rule can be ignored in the stable model semantics. It is known that, I is a stable model of an NLP P iff I is a supported model of both P and some P ′ ⊆ P such that P ′ does not have any loop in its positive dependency graph 2 [Lin and Zhao, 2004]. For example, in P(N1) (4), the rules Q = {p ← q, q ← p∧r } have a loop in the positive dependency graph. Then, P(N1)′ = P (N1) \ Q = { r ← ¬p } has the unique supported model {r}, which is the stable model of P(N1). For P2 (7), {p, r} is not a supported model of P ′2 = P2 \ {p ← p}, and is not a stable model of P2. We now define a similar property for BNs: an attractor is called nonself-dependent if any its expressing node does not depend on itself in the positive dependency graph. We characterize this by the stable model semantics for NLPs with choice rules 3 [Simon et al., 2002]. Intuitively, the choice rule (0{p}1 ← ) represents that p is or is not contained in each stable model.

Theorem 3.4 Let N = (V, F ) be a synchronous BN. Then, I is a non-self-dependent point attractor of N iff I is a stable model of P(N) ∪ {(0{v}1 ← ) | v ∈ VC}. 4

For Example 3.1, {p, r} is neither a stable model of P (N2) nor a stable model of P(N2) ∪ {q}, and hence is not a nonself-dependent point attractor of N2. On the other hand, the stable model {p, q} of P (N2) ∪ {q} is non-self-dependent.

3.4 FromNLPs to BNs

We now show a converse translation from NLPs to BNs. For this, we assume that the Herbrand base A is finite, and its elements can be numbered as A1, . . . ,An. Then, any interpretation I ⊆ A can be identified with the n-tuple ([A1]I, . . . , [An]I), where [Ai]I is the truth value of Ai in I, i.e., [Ai]I = 1 iff Ai ∈ I and [Ai]I = 0 iff Ai ̸∈ I.

2 The directed graph consisting of the positive edges in a BN N is exactly the positive dependency graph of P(N).

3 A choice rule is an instance of cardinality constraints [Simon et al., 2002], which is explained in Section 4.

4 Each rule of the form (vi ← vi) for any vi ∈ VC can be omitted from P(N) in the presence of choice rules in Theorem 3.4.

Given a propositional NLP P , construct the synchronous BN N(P) = (A, F(P)), where F(P) is defined as follows. For each A ∈ A, suppose the set of rules in P whose heads are A is given by {(A ← B1), . . . , (A ← Bk)}, where each Bj (1 ≤ j ≤ k) is a conjunction of literals. Then, the regulation function for A is defined as At+1 = (Bt1 ∨ · · · ∨ Btk ) when k ≥ 1, and is assigned 0 when k = 0 (A is set as a 0-node).

Theorem 3.5 Let P be a propositional NLP. Then, I is a supported model of P iff I is a point attractor of N(P).

An obvious merit of representation of BNs in terms of logic programming semantics (and vice versa) is that we can apply rich resources of NLPs to BNs (and vice versa). Such theories include complexity results, computational procedures, and several relations between two programs such as equivalence and generality. Here, we just apply a well-known complexity result for NLPs to BNs. Detection of a point attractor in a BN is known to be NP-hard [Milano and Roli, 1999], and this holds even for a BN with the maximum indegree 2 [Tamura and Akutsu, 2009]. To the best of our knowledge, however, the next results have never been stated in the literature, yet the problems are important to know whether some specific genes can be expressed or not in genetic networks.

Theorem 3.6 Let N = (V, F) be a synchronous BN, and v ∈ V any node in N. Deciding if v is expressed in some point attractor (resp. all point attractors) of N is NPcomplete (resp. co-NP-complete).

Theorem 3.6 is proved based on the complexity results for the supported model semantics [Marek and Truszczy´nski, 1991], and the (co-)NP-completeness also holds for the same inference problems of non-self-dependent attractors.

4 Asynchronous BNs

It has been argued in biology that asynchronous BNs (ABNs) are closer to real biological phenomena than synchronous BNs (SBNs), but due to their complexities to model and analyze, less studies have been done for ABNs compared with SBNs. In ABNs, different genes take different time to make the state transition from one expression level to another, and hence delay always occurs. To model asynchronicity, several update schemes have been proposed [Gershenson, 2002; Garg et al., 2008], and different updating schemes may lead to different attractors. Here, we assume that update of a state is done by nondeterministically choosing nodes to be updated at each time step. This update scheme is called generalized asynchronous in [Gershenson, 2002], and contains many other update schemes as its special cases.

Remember that any attractor of an SBN is either a point attractor or a cycle attractor. By contrast, in an ABN, there are attractors (called loose attractors [Harvey and Bossomaier, 1997] or complex loops [Garg et al., 2008]) which are neither cycle attractors nor point attractors.

Example 4.1 Consider the BN N3 = ({p, q}, F3) in Figure 2 (left). The state transition diagram of N3 with the synchronous update is depicted as the thick lines in Figure 2 (right), while the asynchronous update has additional transitions written in the thin lines as well as self loops corresponding null updates (not shown in the figure). The label of an arc in a thin line represents the set of selected rules in that update. Any transition in a thick line uses the whole set {x1, x2}. Note that the next state of (0, 1) or (1, 0) is only itself whichever set of rules is chosen for update.

The two point attractors, (0, 1) and (1, 0), of N3 in the synchronous update are also point attractors in the asynchronous update. The cycle attractor (0, 0) → (1, 1) → (0, 0) in the synchronous update is not an attractor in the asynchronous update since there are transitions outgoing from this cycle. In fact, the states (0, 0) and (1, 1) are soon trapped by one of the point attractors by a sequential update.

We now show a translation of ABNs into logic programs. A cardinality constraint [Simon et al., 2002] is an expression of the form l{L1, . . . , Ln}u, where Li (1 ≤ i ≤ n) is a literal and l and u are integers such that 0 ≤ l ≤ u ≤ n. Intuitively, l{L1, . . . , Ln}u is satisfied by a set I of atoms if the number of the literals satisfied by I in {L1, . . . , Ln} is between the lower bound l and the upper bound u. Cardinality constraints are used in heads and bodies of rules as a basic construct in answer set programming (ASP).

Suppose an ABN N = (V, F) where each fi ∈ F is given by (3). For each vi ∈ V , we introduce a new predicate xi intending that xti = 1 represents that vi is chosen for update with fi at time step t. For N, we define the programP nd T (N) as the union of the rules (8) and (9) defined for each vi ∈ (V \ VC), the rules (10) defined for each constant node ci ∈ VC, and the rule (11):

where X(t) = {xi(t) | vi ∈ (V \ VC)} and 0 ≤ l ≤ u ≤ n′ for n′ = |V \ VC|.

Here, the Boolean function fi is used to update vi(t) if xi(t) is true by (8); otherwise (¬xi(t)), the value of vi is not updated by (9). The value of a constant node does not change by (10). In (11), the cardinality constraint l X(t) u represents that between l and u nodes can be updated at each time step, given two parameters l and u. When l = 0, null updates are allowed, i.e., updating no node at a time step. When l = 1, at least one non-constant node is chosen for update at each time step. In particular, l = u = 1 represents a sequential update [Harvey and Bossomaier, 1997; Garg et al., 2008], in which only one node is chosen for each update. When l = u = n′ , all non-constant nodes are updated simultaneously, hence an SBN is expressed as a special case of ABNs.

For the programP nd T (N), the TP operator for NLPs cannot be directly applied since a rule with a cardinality constraint in its head has a nondeterministic effect. 5 In our case, however, the cardinality constraint appears only at the rule (11), and then can be replaced with choice rules and integrity constraints. In the following, to simplify the discussion, we fix the parameters in (11) as l = 0 and u = n′ , that is, any number of nodes can be chosen for update at each time step. Then, (0X(t) n′ ← ) (11) can be replaced with

Under the supported model semantics, the rules (12) can be further translated into

Let P d T (N) be the union of the rules (8), (9), (10), and (13). Note that P d T (N) is an NLP. Now, given any state v(t) = (vt1 , . . . , vtn ), suppose Ix(t) ⊆ X(t) are selected at time step t. Then, the next state Iv(s(t)) is uniquely determined as:

Since each Iv(t) only mentions a state at time step t, we can drop the time argument from each literal of the form vi(t) or ci(t) in the rules (8), (9) and (10) of P d T (N) as in the case of SBNs. Moreover, dropping the time argument is also applied to the selection literal xi(t)'s in the rules (8), (9), and (13). Let P A(N) be the resulting propositional program.

Unlike Theorem 3.2 for SBNs, the propositional NLP P A(N) cannot precisely simulate the trajectories of an ABN N. However, point attractors of N can be identified by the deterministic immediate consequence operator with P A(N):

Proposition 4.2 Let N = (V, F) be an ABN. Then, I is a point attractor of N iff I = TP A(N)(I ∪ Y ) ∩ V for any set Y ⊆ {xi | vi ∈ V \ VC}.

Given a BN N = (V, F), we can interpret N as either a synchronous BN or an asynchronous BN. We denote it as N s if N is synchronous, and as N a if asynchronous. Now, we show the relationship between them as follows.

Proposition 4.3 I is a point attractor of N a iff I is a point attractor of N s .

Proposition 4.3 can be proved by the fact that, for each vi ∈ V , either (vi ← xi∧Bi,j ) for j = 1, . . . , li or (vi ← ¬xi∧vi) is selected. In the former case, the state of vi is not changed in N s because I is a point attractor of N a . In the latter case, the state of vi is not updated by (vi ← vi). Then I must be a point attractor of N s . The converse holds by Proposition 4.2.

Although a fact similar to Proposition 4.3 has already been stated in [Gershenson, 2002; Garg et al., 2008], we formally obtain the result by the semantics of BNs in this paper. Hence, computation of point attractors of an ABN N can be done by Theorem 3.3 via the translation P(N) for the SBN. This fact also justifies a reason why computation of point attractors is more important in SBNs than that of cycle attractors.

5 For a program P with cardinality constraints, we could use the nondeterministic consequence operator T nd P : 2A → 22A in [Marek et al., 2007] and define orbits as branching trees induced by T nd P .

5 Discussion

Computing Attractors and Stable States. Several methods have recently been proposed to compute attractors of synchronous BNs based on ASP and SAT techniques. In [Dubrova and Teslenko, 2010], attractors are searched on state transition diagrams of BNs with bounded model checking, in which the length of trajectories is incrementally varied. This computation process is repeated until an upper bound, and then each obtained trajectory is checked whether an attractor is included or not. In contrast, our Theorem 3.3 shows that only one propositional formula Comp(P(N)) is necessary to get all point attractors, but cycle attractors cannot be obtained in this way. 6 Particular focuses are put on point attractors in [Tamura and Akutsu, 2009; Melkman et al., 2010] based on more elaborate translations of BNs into SAT. Conversely, SAT is translated into BNs in [Milano and Roli, 1999; Tamura and Akutsu, 2009]. Fayruzov et al. [2009] use ASP for computing attractors, but their conflict resolution is different from the original BNs, and hence it is not clear how complex regulation functions can be expressed in their approach. ASP is also used to analyze biological networks that are not BNs: Gebser et al. [2008] detect inconsistencies in biological networks, and Ray et al. [2011] compute supported and stable models from reaction networks that respectively correspond to states with and without self-supporting loops.

In principle, each previous work translates a particular BNrelated problem into an equivalent computational problem at the meta-level. For example, [Fayruzov et al., 2009] translates at+1 = bt into activates(a, b, t) and defines several axioms for updates, e.g., (act(Y, T + 1) ← act(X, T) ∧ activates(X, Y, T) ∧ ¬conflict(Y, T) ∧ ¬mos act th(Y )). In contrast, we simply map the regulation functions directly to (a ← b), and then give the semantics of them. This work thus enables us to analyze any BN-related problem on the semantics of logic programs, and provide an integrated way to apply theories and techniques developed in logic programming to various computational problems in BNs.

Control of BNs. Akutsu et al. [2007] have defined the problem to find a control strategy of a BN, which leads to the given goal state from the given initial state. Some external control nodes are also given and their values are manipulated in [Akutsu et al., 2007] to achieve the goal state, which is somewhat similar to AI planning. Viewing a BN as an NLP, a related problem can be defined by modifying the decision problem in Theorem 3.6 to finding of initial states of constant nodes that realize expression of a target node v. This can be achieved by finding a supported model containing v.

Simulation and Equivalence of BNs. Blair et al. [1997] did a pioneer work to view logic programs as cellular automata (CAs), which are special cases of synchronous BNs considered in this paper, and pointed out the importance of orbits in capturing inferential behaviors of NLPs. However, their main concern is not on computational properties of attractors, but is on simulation of an orbit for an NLP by an orbit for some Horn program. As far as attractors are concerned, we can define equivalence between two BNs with control nodes, and can capture it by relativized equivalence under the supported model semantics [Truszczy´nski andWoltran, 2008].

6 We have tested our SAT-based approach to biological data in [Dubrova and Teslenko, 2010], and obtained better performance to get point attractors, e.g., all 7 point attractors for Drosophila melanogaster (52 nodes) are obtained within 0.05 sec by MiniSat2.

Positive and Negative Loops. It has been observed that (I) presence of positive loops in a BN is linked to multistability, i.e., existence of multiple point attractors involved in differentiation, and that (II) presence of negative loops is the source of periodic oscillations, i.e., existence of cycle attractors involved in homeostasis [Remy and Ruet, 2008]. Here, the sign of a loop is defined as the product of the signs of its edges. On the other hand, [You and Yuan, 1994] have shown that (I') existence of even loops in an NLP implies multiple stable models, and that (II') existence of odd loops implies presence of undefined literals. In (I'), however, even loops in NLPs are assumed to be non-zero, i.e., containing at least two negative edges. As the supported models of NLPs correspond to point attractors of BNs, by considering positive loops without negative edges, the property (I) of BNs can be transferred to NLPs, providing a necessary condition to have multiple supported models. In fact, supported models and stable models are not much different from each other, with only difference on the treatment of such positive loops [Lin and Zhao, 2004].

Relating the properties (II) of BNs and (II') of NLPs, cycle attractors in BNs are closely related to undefined literals in regular models [You and Yuan, 1994] as well as the stable class semantics [Baral and Subrahmanian, 1992]. For example, P4 = {p ← ¬p} has no supported model and the BN N(P4) has no point attractor by Theorem 3.5, but the orbit of I0 = ∅ or I1 = {p} with respect to P4 becomes I0, I1, I0, I1, . . ., and the cycle attractor (0) → (1) → (0) is found in it. Hence, viewing an NLP as a BN, we get more information from the program, and can get a meaning even when it is inconsistent under the supported or stable model semantics.

6 Conclusion

We have seen that there are so many common properties between BNs and NLPs. This comparison can be promoted by considering the similarity between the fixed points of BNs and the TP operator of NLPs. We have revived the notion of orbits in this paper, but have also shown that orbits themselves are not necessary to characterize point attractors of BNs. In fact, supported models of logic programs are useful for that, and this work opens an important application of the supported model semantics in which non-stable supported models play an important role. With the "attractor semantics", logic programs that are inconsistent under the supported or stable model semantics can have meanings as they have cycle attractors. Such semantics had ever been investigated in some work on logic programming [Baral and Subrahmanian, 1992; You and Yuan, 1994], but have not been focused on recently.

An obvious merit of NLPs compared with BNs is that firstorder representation is possible in NLPs. Then, we could consider first-order BNs to describe dynamics of systems with infinite domains or to have compact representation for common update patterns. In the research of BNs, probabilistic BNs [Shmulevich et al., 2002] have been investigated, in which multiple Boolean functions can be assigned to each node and one function is selected randomly each time. Alternatively, to express such nondeterminism in a non-stochastic way, we could consider disjunctive BNs to allow indefinite effects. Relating these extensions of BNs with probabilistic or disjunctive logic programming is also an interesting future topic. Finally, abductive and inductive logic programming could be applied to abduction and induction on BNs to infer missing nodes and missing regulation functions from observations and training examples, respectively.

Acknowledgments

This research is supported in part by the 2008-2011 JSPS Grant-in-Aid for Scientific Research (A) No. 20240016. The author would like to thank Tatsuya Akutsu, Chiaki Sakama and Takehide Soh for their useful discussions, and anonymous reviewers for their helpful comments.