getAttractors {BoolNet} | R Documentation |
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
network |
A network structure of class |
type |
If If See Details for more information on the algorithms. |
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 If If If |
startStates |
The value of |
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 |
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 |
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 |
randomChainLength |
If |
avoidSelfLoops |
If |
geneProbabilities |
If |
maxAttractorLength |
If |
returnTable |
Specifies whether a transition table is included in the returned |
Details
Depending on the type of network and the chosen parameters, different search algorithms are started.
For BooleanNetwork
networks, there are three different modes of attractor search:
- 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.
- 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
startStates
. - 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
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. - 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
maxAttractorLength
states (e.g. all steady states formaxAttractorLength=1
) , but does not find any larger attractors. As for the exhaustive SAT-based method, no transition table is returned. - 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
startStates
:Perform
randomChainLength
random asynchronous transitions. After these transitions, the network state is expected to be located in an attractor with a high probability.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 SymbolicBooleanNetwork
networks, getAttractors
is simply a wrapper for simulateSymbolicModel
with preset parameters.
Printing the return value of getAttractors
using print
visualizes the identified attractors.
Value
For BooleanNetwork
networks, this returns a list of class AttractorInfo
with components
attractors |
A list of attractors. Each element is a 2-element list with the following components:
|
stateInfo |
A summary structure of class
The structure supports pretty printing using the |
For SymbolicBooleanNetwork
networks, getAttractors
redirects the call to simulateSymbolicModel
and returns an object of class SymbolicSimulation
containing the attractors and (if 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.
See Also
loadNetwork
, generateRandomNKNetwork
, simulateSymbolicModel
, plotAttractors
, attractorsToLaTeX
, getTransitionTable
, getBasinOfAttraction
, getAttractorSequence
, getStateSummary
, getPathToAttractor
, fixGenes
, generateState
Examples
## Not run:
# 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")
## End(Not run)