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 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:

  1. Perform randomChainLength random asynchronous transitions. After these transitions, the network state is expected to be located in an attractor with a high probability.

  2. 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.

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)

[Package BoolNet version 2.1.9 Index]