An Efficient Algorithm for Computing Attractors of Synchronous And Asynchronous Boolean Networks |
| |
| Authors: | Desheng Zheng Guowu Yang Xiaoyu Li Zhicai Wang Feng Liu Lei He |
| |
| Affiliation: | 1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, Sichuan, China.; 2. Departmnent of Electronic Engineering, University of California Los Angeles, Los Angeles, California, United States of America.; 3. Department of Pathology and Laboratory Medicine, David Geffen University of Califonia Los Angeles School of Medicine, Los Angeles, California, United States of America.; Rutgers University, United States of America, |
| |
| 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 faster in computing attractors for empirical experimental systems.AvailabilityThe software package is available at https://sites.google.com/site/desheng619/download. |
| |
| Keywords: | |
|
|
