An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks.
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 und...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2013-01-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC3621871?pdf=render |
| _version_ | 1828354396308635648 |
|---|---|
| author | Desheng Zheng Guowu Yang Xiaoyu Li Zhicai Wang Feng Liu Lei He |
| author_facet | Desheng Zheng Guowu Yang Xiaoyu Li Zhicai Wang Feng Liu Lei He |
| author_sort | Desheng Zheng |
| collection | DOAJ |
| description | 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.The software package is available at https://sites.google.com/site/desheng619/download. |
| first_indexed | 2024-04-14T02:24:26Z |
| format | Article |
| id | doaj.art-491e0f9aef294a99bbf16918339d2de6 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-04-14T02:24:26Z |
| publishDate | 2013-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-491e0f9aef294a99bbf16918339d2de62022-12-22T02:17:56ZengPublic Library of Science (PLoS)PLoS ONE1932-62032013-01-0184e6059310.1371/journal.pone.0060593An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks.Desheng ZhengGuowu YangXiaoyu LiZhicai WangFeng LiuLei HeBiological 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.The software package is available at https://sites.google.com/site/desheng619/download.http://europepmc.org/articles/PMC3621871?pdf=render |
| spellingShingle | Desheng Zheng Guowu Yang Xiaoyu Li Zhicai Wang Feng Liu Lei He An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. PLoS ONE |
| title | An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. |
| title_full | An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. |
| title_fullStr | An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. |
| title_full_unstemmed | An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. |
| title_short | An efficient algorithm for computing attractors of synchronous and asynchronous Boolean networks. |
| title_sort | efficient algorithm for computing attractors of synchronous and asynchronous boolean networks |
| url | http://europepmc.org/articles/PMC3621871?pdf=render |
| work_keys_str_mv | AT deshengzheng anefficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT guowuyang anefficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT xiaoyuli anefficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT zhicaiwang anefficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT fengliu anefficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT leihe anefficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT deshengzheng efficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT guowuyang efficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT xiaoyuli efficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT zhicaiwang efficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT fengliu efficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks AT leihe efficientalgorithmforcomputingattractorsofsynchronousandasynchronousbooleannetworks |