Algorithms for Finding Small Attractors in Boolean Networks

Shuqin Zhang, Morihiro Hayashida, Tatsuya Akutsu, Wai-Ki Ching, Michael Kwok-Po NgEURASIP J. Bioinform. Syst. Biol 2007 · DOI

TL;DR

This paper introduces novel algorithms for efficiently identifying "attractors" in Boolean networks, which model gene regulatory systems. By developing gene-ordering and feedback vertex set-based approaches, the authors significantly improve upon existing methods, offering theoretical guarantees on average-case performance and demonstrating practical speedups, particularly for scale-free biological networks.

What Problem Does This Paper Address?

Biological systems, like gene regulatory networks, are incredibly complex. To understand their behavior, scientists use mathematical models. Boolean networks are a simplified yet powerful model where genes are represented as nodes that are either "on" (expressed) or "off" (unexpressed). These genes interact through logical rules, and the network's state evolves over time. A key aspect of this evolution is the emergence of "attractors" – stable states or cycles that the network eventually settles into, regardless of its initial condition. These attractors are thought to represent fundamental cellular states like differentiation or cell cycles.

The challenge lies in efficiently finding these attractors, especially "singleton attractors" (stable states) and "small attractors" (cycles with short periods), which are believed to be particularly biologically relevant. Exhaustively checking all possible states of a Boolean network (which grows exponentially with the number of genes) is computationally infeasible for even moderately sized networks. While previous work has shown that finding attractors can be NP-hard, this paper aims to develop algorithms that are fast in practice and have theoretical guarantees on their average-case performance.

Methods

The paper proposes several algorithms, primarily building upon the concept of gene ordering and feedback vertex sets (FVS).

  • Gene Ordering: Instead of processing genes in an arbitrary order, the algorithms reorder genes based on criteria like their outdegree (number of genes they influence) or a breadth-first search (BFS) traversal of the network graph. The intuition is that by prioritizing genes that influence many others or are "earlier" in a network traversal, we can determine the state of more genes more quickly, pruning the search space.
  • Feedback Vertex Set (FVS): For networks with cycles, a feedback vertex set is a subset of nodes whose removal breaks all cycles, making the remaining graph acyclic. The paper uses a greedy algorithm to find an FVS and then applies attractor-finding algorithms to the resulting acyclic structure. This leverages the property that acyclic networks have unique singleton attractors that can be found efficiently.
  • Basic Recursive Algorithm: A foundational recursive algorithm is presented, which explores potential attractors by extending partial solutions (assignments of gene states) one gene at a time.
  • Modified Algorithms: The basic recursive and gene-ordering algorithms are adapted to find cyclic attractors with a specific period p by checking for v(t+p) = v(t) instead of v(t+1) = v(t).

The authors provide theoretical analysis of the average-case time complexity for these algorithms, particularly under the assumption that Boolean networks are generated uniformly at random.

Datasets

The paper does not introduce new datasets. Instead, it uses randomly generated Boolean networks with varying numbers of genes (n) and maximum indegrees (K) for theoretical analysis and computational experiments. They also conduct experiments on scale-free networks, which are known to better represent many real biological networks, generated with specific power-law outdegree and Poisson indegree distributions.

Key Insights and Ideas

  • Gene ordering is crucial for efficiency: Prioritizing genes based on their influence (outdegree) or network position (BFS) significantly reduces the search space compared to arbitrary ordering.
  • FVS simplifies cyclic networks: Decomposing cyclic networks into acyclic components using FVS allows for more efficient analysis, leveraging the tractability of acyclic networks.
  • Scale-free networks behave differently: The proposed algorithms perform substantially faster on scale-free networks than on random networks, suggesting that network topology plays a critical role in algorithm performance. This is attributed to the higher prevalence of high-degree nodes in scale-free networks, which the ordering heuristics can exploit more effectively.
  • Theoretical guarantees matter: The paper provides average-case time complexity analyses, offering a theoretical basis for the observed practical speedups.
  • NP-hardness proof is simplified: A clear and concise proof for the NP-hardness of finding attractors with the shortest period is presented, which is valuable for understanding the fundamental limits of these problems.

Key Results

  • Significant speedups: The proposed algorithms, particularly the FVS + Outdegree approach, demonstrate substantial improvements in computational time compared to a naive approach. For instance, the outdegree-based ordering algorithm for singleton attractors is shown to work in O(1.19^n) time for K=2, a significant improvement over the naive O(2^n).
  • Empirical validation: Computational experiments on random networks show that the FVS + Outdegree algorithm is the fastest in practice.
  • Scale-free network advantage: Experiments on scale-free networks reveal even greater speedups, with average case complexities like O(1.09^n) for the outdegree-based algorithm, compared to O(1.19^n) for random networks.
  • Theoretical analysis aligns with practice: The theoretical average-case time complexities generally align with the empirical results, providing confidence in the algorithms' performance.

Limitations and Future Work

  • Theoretical analysis for scale-free networks: The paper acknowledges that theoretical analysis for scale-free networks is lacking and suggests it as a future research direction.
  • Practicality for large networks: While faster than naive methods, the algorithms still have exponential time complexity in the worst case, limiting their direct application to very large networks (hundreds or thousands of genes).
  • Comparison with constraint programming: The authors note that constraint programming-based methods (like those by Devloo et al.) might be more efficient in practice for some cases, but lack theoretical complexity guarantees.
  • Generalization to other models: The techniques developed for Boolean networks could potentially be extended to analyze continuous biological network models.
  • Finding attractors with arbitrary periods: The current modification for small attractors assumes the period is known. Extending this to find attractors with any period up to a bound P is discussed but noted as potentially impractical.

Summary updated

BibTeX
@article{zhang2007algorithms,
  author = {Shuqin Zhang and Morihiro Hayashida and Tatsuya Akutsu and Wai-Ki Ching and Michael Kwok-Po Ng},
  title = {{Algorithms for Finding Small Attractors in Boolean Networks}},
  journal = {EURASIP J. Bioinform. Syst. Biol.},
  year = {2007},
  doi = {10.1155/2007/20180},
}
Figure