getAttractors: Identify attractors in a Boolean network
In BoolNet: Construction, Simulation and Analysis of Boolean Networks

getAttractors

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 `BooleanNetwork` or `SymbolicBooleanNetwork`. These networks can be read from files by `loadNetwork`, generated by `generateRandomNKNetwork`, or reconstructed by `reconstructNetwork`.
`type`	If `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 `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.
`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 `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 `method="exhaustive"`, but does not return the state transition graph. For `method="sat.exhaustive"`, an exhaustive attractor search is performed, while `method="sat.restricted"` only searches for attractors of a specified maximum length `maxAttractorLength`. If `method` is "random", `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 `method` is "chosen", `startStates` is interpreted as a list of binary vectors, each specifying one input state. Each vector must have `length(network$genes)` elements with 0 or 1 values. The algorithm identifies the attractors to which the supplied states lead. If `network` is of class `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 `method` is not supplied, the desired method is inferred from the type of `startStates`. By default, if neither `method` nor `startStates` are provided, an exhaustive search is performed.
`startStates`	The value of `startStates` depends on the chosen method. See `method` for more details.
`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 `fixGenes`.
`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 `fixGenes`.
`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 `getAttractors` are comparable, as the cycles may have been entered at different states in different runs of the algorithm.
`randomChainLength`	If `type="asynchronous"`, this parameter specifies the number of random transitions performed by the search to enter a potential attractor (see Details). Defaults to 10000.
`avoidSelfLoops`	If `type="asynchronous"` and `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.
`geneProbabilities`	If `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.
`maxAttractorLength`	If `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 `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.
`returnTable`	Specifies whether a transition table is included in the returned `AttractorInfo` structure. If `type="asynchronous"` or `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 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 for maxAttractorLength=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:

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.
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
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
basinSize: The number of states in the basin of attraction. Details on the states in the basin can be retrieved via getBasinOfAttraction.

stateInfo

A summary structure of class BooleanStateInfo containing information on the transition table. It has the following components:

initialStates: This element is only available if type="synchronous", method is "random" or "chosen", and returnTable=TRUE. This is a matrix describing the initial states that lead to the states in table after a state transition. If method is "exhaustive", this component is NULL. In this case, the initial states can be inferred, as all states are used. The format of the matrix is described in involvedStates.
table: This element is only available if type="synchronous" and 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.
attractorAssignment: This element is only available if type="synchronous" and returnTable=TRUE. It contains a vector that corresponds to the entries in table and describes the attractor index in attractors to which successive transitions from the described state finally lead.
stepsToAttractor: This element is only available if type="synchronous" and returnTable=TRUE. Referring to attractorAssignment, this is the number of transitions needed to reach the attractor.
genes: A list of names of the genes in network.
fixedGenes: Specifies the fixed genes as in the fixed component of network.

The structure supports pretty printing using the print method.

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.

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)

BoolNet documentation built on Oct. 2, 2023, 5:08 p.m.