title: An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks.
abstract: Biological networks, such as genetic regulatory networks, often contain positive and negative feedback loops that settle down to dynamically stable patterns. Identifying these patterns, the so-called attractors, can provide important insights for biologists to understand the molecular mechanisms underlying many coordinated cellular processes such as cellular division, differentiation, and homeostasis. Both synchronous and asynchronous Boolean networks have been used to simulate genetic regulatory networks and identify their attractors. The common methods of computing attractors are that start with a randomly selected initial state and finish with exhaustive search of the state space of a network. However, the time complexity of these methods grows exponentially with respect to the number and length of attractors. Here, we build two algorithms to achieve the computation of attractors in synchronous and asynchronous Boolean networks. For the synchronous scenario, combing with iterative methods and reduced order binary decision diagrams (ROBDD), we propose an improved algorithm to compute attractors. For another algorithm, the attractors of synchronous Boolean networks are utilized in asynchronous Boolean translation functions to derive attractors of asynchronous scenario. The proposed algorithms are implemented in a procedure called geneFAtt. Compared to existing tools such as genYsis, geneFAtt is significantly [Formula: see text] faster in computing attractors for empirical experimental systems.
  
  
  BACKGROUND
  The software package is available at https://sites.google.com/site/desheng619/download.
authors.affiliation: School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China. desheng619@gmail.com
authors.forename: Desheng
authors.initials: D
authors.lastname: Zheng
authors.forename: Guowu
authors.initials: G
authors.lastname: Yang
authors.forename: Xiaoyu
authors.initials: X
authors.lastname: Li
authors.forename: Zhicai
authors.initials: Z
authors.lastname: Wang
authors.forename: Feng
authors.initials: F
authors.lastname: Liu
authors.forename: Lei
authors.initials: L
authors.lastname: He
mesh_terms: D000465:Algorithms; D000818:Animals; D003198:Computer Simulation; D005057:Eukaryotic Cells / Q000378:metabolism; D005786:Gene Expression Regulation; D053263:Gene Regulatory Networks; D006801:Humans; D008957:Models, Genetic; D012984:Software