1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
\name{getAttractors}
\Rdversion{1.1}
\alias{getAttractors}
%- Also NEED an '\alias' for EACH other topic documented here.
\title{Identify attractors in a Boolean network}
\description{Identifies attractors (cycles) in a supplied Boolean network using synchronous or asynchronous state transitions}
\usage{
getAttractors(network,
type = c("synchronous","asynchronous"),
method = c("exhaustive",
"sat.exhaustive",
"sat.restricted",
"random",
"chosen"),
startStates = list(),
genesON = c(), genesOFF = c(),
canonical = TRUE,
randomChainLength = 10000,
avoidSelfLoops = TRUE,
geneProbabilities = NULL,
maxAttractorLength = Inf,
returnTable = TRUE)
}
\arguments{
\item{network}{
A network structure of class \code{BooleanNetwork} or \code{SymbolicBooleanNetwork}. These networks can be read from files by \code{\link{loadNetwork}}, generated by \code{\link{generateRandomNKNetwork}}, or reconstructed by \code{\link{reconstructNetwork}}.
}
\item{type}{
If \code{type="synchronous"}, synchronous state transitions are used, i.e. all genes are updated at the same time. Synchronous attractor search can be performed in an exhaustive manner or using a heuristic that starts from predefined states. For symbolic networks, only synchronous updates are possible.
If \code{type="asynchronous"}, asynchronous state transitions are performed, i.e. one (randomly chosen) gene is updated in each transition. Steady-state attractors are the same in asynchronous and synchronous networks, but the asynchronous search is also able to identify complex/loose attractors. Asynchronous search relies on a heuristic algorithm that starts from predefined states.
See Details for more information on the algorithms.
}
\item{method}{
The search method to be used. If "exhaustive", attractors are identified by exhaustive state space search, i.e. by calculating the sucessors of all 2^n states (where n is the number of genes that are not set to a fixed value). This kind of search is only available for synchronous attractor search, and the maximum number of genes allowed for exhaustive search is 29. Apart from the attractors, this method generates the full state transition graph.
If \code{method} is "sat.exhaustive" or "sat.restricted", attractors are identified using algorithms based on the satisfiability problem. This search type is also restricted to synchronous networks. It can be used to identify attractors in much larger networks than with \code{method="exhaustive"}, but does not return the state transition graph. For \code{method="sat.exhaustive"}, an exhaustive attractor search is performed, while \code{method="sat.restricted"} only searches for attractors of a specified maximum length \code{maxAttractorLength}.
If \code{method} is "random", \code{startStates} is interpreted as an integer value specifying the number of states to be generated randomly. The algorithm is then initialized with these random states and identifies the attractors to which these states lead.
If \code{method} is "chosen", \code{startStates} is interpreted as a list of binary vectors, each specifying one input state. Each vector must have \code{length(network$genes)} elements with 0 or 1 values. The algorithm identifies the attractors to which the supplied states lead. If \code{network} is of class \code{SymbolicBooleanNetwork} and makes use of more than one predecessor state, this can also be a list of matrices with the genes in the columns and multiple predecessor states in the rows.
If \code{method} is not supplied, the desired method is inferred from the type of \code{startStates}. By default, if neither \code{method} nor \code{startStates} are provided, an exhaustive search is performed.
}
\item{startStates}{
The value of \code{startStates} depends on the chosen method. See \code{method} for more details.
}
\item{genesON}{
A vector of genes whose values are fixed to 1, which reduces the complexity of the search. This is equivalent to a preceding call of \code{\link{fixGenes}}.
}
\item{genesOFF}{
A vector of genes whose values are fixed to 0, which reduces the complexity of the search. This is equivalent to a preceding call of \code{\link{fixGenes}}.
}
\item{canonical}{
If set to true, the states in the attractors are rearranged such that the state whose binary encoding
makes up the smallest number is the first element of the vector. This ensures that attractors found by different heuristic runs of \code{getAttractors} are comparable, as the cycles may have been entered at different states in different runs of the algorithm.
}
\item{randomChainLength}{
If \code{type="asynchronous"}, this parameter specifies the number of random transitions performed by the search to enter a potential attractor (see Details). Defaults to 10000.
}
\item{avoidSelfLoops}{
If \code{type="asynchronous"} and \code{avoidSelfLoops=TRUE}, the asynchronous attractor search only enters self loops (i.e. transitions that result in the same state) if none of the possible transitions can leave the state. This results in attractors with fewer edges. Otherwise, self loops are included in the attractors. By default, self loops are avoided.
}
\item{geneProbabilities}{
If \code{type="asynchronous"}, this allows to specify probabilities for the genes. By default, each gene has the same probability to be chosen for the next state transition. You can supply a vector of probabilities for each of the genes which sums up to one.
}
\item{maxAttractorLength}{If \code{method="sat.restricted"}, this required parameter specifies the maximum size of attractors (i.e. the number of states in the loop) to be searched. For \code{method="sat.exhaustive"}, this parameter is optional and specifies the maximum attractor length for the initial length-restricted search phase that is performed to speed up the subsequent exhaustive search. In this case, changing this value might bring performance benefits, but does not change the results.}
\item{returnTable}{
Specifies whether a transition table is included in the returned \code{AttractorInfo} structure. If \code{type="asynchronous"} or \code{method="sat"}, this parameter is ignored, as the corresponding algorithms never return a transition table.
}
}
\details{
Depending on the type of network and the chosen parameters, different search algorithms are started.
For \code{BooleanNetwork} networks, there are three different modes of attractor search:
\describe{
\item{Exhaustive synchronous state space search}{
In this mode, synchronous state transitions are carried out from each of the possible states until an attractor is reached. This identifies all synchronous attractors.
}
\item{Heuristic synchronous state space search}{
In contrast to exhaustive synchronous search, only a subset of the possible states is used. From these states, synchronous transitions are carried out until an attractor is reached. This subset is specified in \code{startStates}.
}
\item{Exhaustive synchronous SAT-based search}{
Here, the attractor search problem is formulated as a satisfiability problem and solved using Armin Biere's PicoSAT solver. The algorithm is a variant of the method by Dubrova and Teslenko which searches for a satisfying assignment of a chain constructed by unfolding the transition relation. Depending on \code{maxAttractorLength}, it additionally applies an initial size-restricted SAT-based search (see below) to increase overall search speed. This method is suitable for larger networks of up to several hundreds of genes and exhaustively identifies all attractors in these networks. In contrast to the state space search, it does not construct and return a state transition table.
}
\item{Size-restricted synchronous SAT-based search}{
Here, the SAT solver directly looks for satisfying assignments for loops of a specific size. This may be more efficient for large networks and is guaranteed to find all attractors that comprise up to \code{maxAttractorLength} states (e.g. all steady states for \code{maxAttractorLength=1}) , but does not find any larger attractors. As for the exhaustive SAT-based method, no transition table is returned.
}
\item{Heuristic asynchronous search}{
This algorithm uses asynchronous state transitions and is able to identify steady-state and complex/loose attractors (see Harvey and Bossomaier, Garg et al.). These attractors are sets of states from which all possible asynchronous transitions lead into a state that is member of the set as well.
The heuristic algorithm does the following for each of the input state specified by \code{startStates}:
\enumerate{
\item Perform \code{randomChainLength} random asynchronous transitions. After these transitions, the network state is expected to be located in an attractor with a high probability.
\item Calculate the forward reachable set of the current state. Then, compare this set to the forward reachable set of all states in the set. If all sets are equal, a complex attractor is found.
}
}
For \code{SymbolicBooleanNetwork} networks, \code{getAttractors} is simply a wrapper for \code{\link{simulateSymbolicModel}} with preset parameters.
}
Printing the return value of \code{getAttractors} using \code{\link{print}} visualizes the identified attractors.}
\value{
For \code{BooleanNetwork} networks, this returns a list of class \code{AttractorInfo} with components
\item{attractors}{A list of attractors. Each element is a 2-element list with the following components:
\describe{
\item{involvedStates}{A matrix containing the states that make up the attractor. Each column represents one state. The entries are decimal numbers that internally represent the states of the genes. The number of rows depends on the number of genes in the network: The first 32 genes are encoded in the first row, genes 33-64 are encoded in the second row, etc.}
\item{initialStates}{This element is only available if an asynchronous search was carried out and this is a complex attractor. In this case, it holds the encoded start states of the transitions in the complex attractor}
\item{nextStates}{This element is only available if an asynchronous search was carried out and this is a complex attractor. In this case, it holds the encoded successor states of the transitions in the complex attractor}
\item{basinSize}{The number of states in the basin of attraction. Details on the states in the basin can be retrieved via \code{\link{getBasinOfAttraction}}.}
}}
\item{stateInfo}{A summary structure of class \code{BooleanStateInfo} containing information on the transition table. It has the following components:
\describe{
\item{initialStates}{This element is only available if \code{type="synchronous"}, \code{method} is "random" or "chosen", and \code{returnTable=TRUE}. This is a matrix describing the initial states that lead to the states in \code{table} after a state transition. If \code{method} is "exhaustive", this component is \code{NULL}. In this case, the initial states can be inferred, as all states are used. The format of the matrix is described in \code{involvedStates}.}
\item{table}{This element is only available if \code{type="synchronous"} and \if{latex}{\cr}\code{returnTable=TRUE}. It holds result vector of the transition table as a matrix with one column for each state. These are encoded bit vectors in decimal numbers as described above.}
\item{attractorAssignment}{This element is only available if \code{type="synchronous"} and \code{returnTable=TRUE}. It contains a vector that corresponds to the entries in \code{table} and describes the attractor index in \code{attractors} to which successive transitions from the described state finally lead.}
\item{stepsToAttractor}{This element is only available if \code{type="synchronous"} and \code{returnTable=TRUE}. Referring to \code{attractorAssignment}, this is the number of transitions needed to reach the attractor.}
\item{genes}{A list of names of the genes in \code{network}.}
\item{fixedGenes}{Specifies the fixed genes as in the \code{fixed} component of \code{network}.}
}
The structure supports pretty printing using the \code{\link{print}} method.}
For \code{SymbolicBooleanNetwork} networks, \code{getAttractors} redirects the call to \code{\link{simulateSymbolicModel}} and returns an object of class \code{SymbolicSimulation} containing the attractors and (if \code{returnTable=TRUE}) the transition graph.
}
\references{
S. A. Kauffman (1969), Metabolic stability and epigenesis in randomly constructed nets. J. Theor. Biol. 22:437--467.
S. A. Kauffman (1993), The Origins of Order. Oxford University Press.
I. Harvey, T. Bossomaier (1997), Time out of joint: Attractors in asynchronous random Boolean networks. Proc. of the Fourth European Conference on
Artificial Life, 67--75.
A. Garg, A. Di Cara, I. Xenarios, L. Mendoza, G. De Micheli (2008), Synchronous versus asynchronous modeling of gene regulatory networks. Bioinformatics 24(17):1917--1925.
E. Dubrova, M. Teslenko (2011), A SAT-based algorithm for finding attractors in synchronous Boolean networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics 8(5):1393--1399.
A. Biere (2008), PicoSAT Essentials. Journal on Satisfiability, Boolean Modeling and Computation 4:75-97.
}
\seealso{
\code{\link{loadNetwork}}, \code{\link{generateRandomNKNetwork}}, \code{\link{simulateSymbolicModel}}, \code{\link{plotAttractors}}, \code{\link{attractorsToLaTeX}}, \code{\link{getTransitionTable}}, \code{\link{getBasinOfAttraction}}, \code{\link{getAttractorSequence}}, \code{\link{getStateSummary}}, \code{\link{getPathToAttractor}}, \code{\link{fixGenes}}, \code{\link{generateState}}
}
\examples{
# load example data
data(cellcycle)
# get all synchronous attractors by exhaustive search
attractors <- getAttractors(cellcycle)
# plot attractors side by side
par(mfrow=c(2, length(attractors$attractors)))
plotAttractors(attractors)
# finds the synchronous attractor with 7 states
attractors <- getAttractors(cellcycle, method="chosen",
startStates=list(rep(1, length(cellcycle$genes))))
plotAttractors(attractors)
# finds the attractor with 1 state
attractors <- getAttractors(cellcycle, method="chosen",
startStates=list(rep(0, length(cellcycle$genes))))
plotAttractors(attractors)
# also finds the attractor with 1 state by restricting the attractor length
attractors <- getAttractors(cellcycle, method="sat.restricted",
maxAttractorLength=1)
plotAttractors(attractors)
# identifies asynchronous attractors
attractors <- getAttractors(cellcycle, type="asynchronous", startStates=100)
plotAttractors(attractors, mode="graph")
}
% Add one or more standard keywords, see file 'KEYWORDS' in the
% R documentation directory.
\keyword{Boolean network
synchronous update
asynchronous update
symbolic Boolean network
attractor
cycle
basin}
|
