Taming Asynchrony for Attractor Detection in Large Boolean Networks

Andrzej Mizera; Jun Pang; Hongyang Qu; Qixia Yuan

doi:10.1109/TCBB.2018.2850901

Taming Asynchrony for Attractor Detection in Large Boolean Networks

Andrzej Mizera, Jun Pang, Hongyang Qu, Qixia Yuan^*

^*Corresponding author for this work

Nutrition, Microbiome and Immunity

Research output: Contribution to journal › Conference article › peer-review

33 Citations (Scopus)

Abstract

Boolean networks is a well-established formalism for modelling biological systems. A vital challenge for analyzing a Boolean network is to identify all the attractors. This becomes more challenging for large asynchronous Boolean networks, due to the asynchronous scheme. Existing methods are prohibited due to the well-known state-space explosion problem in large Boolean networks. In this paper, we tackle this challenge by proposing a SCC-based decomposition method. We prove the correctness of our proposed method and demonstrate its efficiency with two real-life biological networks.

Original language	English
Article number	8398459
Pages (from-to)	31-42
Number of pages	12
Journal	IEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume	16
Issue number	1
DOIs	https://doi.org/10.1109/TCBB.2018.2850901
Publication status	Published - 1 Jan 2019

Keywords

Asynchronous Boolean networks
attractor detection
binary decision diagram
gene regulatory networks
strongly connected components

Access to Document

10.1109/TCBB.2018.2850901

Cite this

@article{8dacb735bdce4cc3874e878e518799dc,

title = "Taming Asynchrony for Attractor Detection in Large Boolean Networks",

abstract = "Boolean networks is a well-established formalism for modelling biological systems. A vital challenge for analyzing a Boolean network is to identify all the attractors. This becomes more challenging for large asynchronous Boolean networks, due to the asynchronous scheme. Existing methods are prohibited due to the well-known state-space explosion problem in large Boolean networks. In this paper, we tackle this challenge by proposing a SCC-based decomposition method. We prove the correctness of our proposed method and demonstrate its efficiency with two real-life biological networks.",

keywords = "Asynchronous Boolean networks, attractor detection, binary decision diagram, gene regulatory networks, strongly connected components",

author = "Andrzej Mizera and Jun Pang and Hongyang Qu and Qixia Yuan",

note = "Funding Information: Qixia Yuan is supported by the National Research Fund, Luxembourg (grant 7814267). This work is also partially supported by the research project SEC-PBN (funded by the University of Luxembourg) and the ANR-FNR project AlgoReCell (INTER/ ANR/15/11191283). Andrzej Mizera contributed to this work while holding a postdoctoral researcher position at the Computer Science and Communications Research Unit, University of Luxembourg. Publisher Copyright: {\textcopyright} 2004-2012 IEEE.",

year = "2019",

month = jan,

day = "1",

doi = "10.1109/TCBB.2018.2850901",

language = "English",

volume = "16",

pages = "31--42",

journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",

issn = "1545-5963",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "1",

}

TY - JOUR

T1 - Taming Asynchrony for Attractor Detection in Large Boolean Networks

AU - Mizera, Andrzej

AU - Pang, Jun

AU - Qu, Hongyang

AU - Yuan, Qixia

N1 - Funding Information: Qixia Yuan is supported by the National Research Fund, Luxembourg (grant 7814267). This work is also partially supported by the research project SEC-PBN (funded by the University of Luxembourg) and the ANR-FNR project AlgoReCell (INTER/ ANR/15/11191283). Andrzej Mizera contributed to this work while holding a postdoctoral researcher position at the Computer Science and Communications Research Unit, University of Luxembourg. Publisher Copyright: © 2004-2012 IEEE.

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Boolean networks is a well-established formalism for modelling biological systems. A vital challenge for analyzing a Boolean network is to identify all the attractors. This becomes more challenging for large asynchronous Boolean networks, due to the asynchronous scheme. Existing methods are prohibited due to the well-known state-space explosion problem in large Boolean networks. In this paper, we tackle this challenge by proposing a SCC-based decomposition method. We prove the correctness of our proposed method and demonstrate its efficiency with two real-life biological networks.

AB - Boolean networks is a well-established formalism for modelling biological systems. A vital challenge for analyzing a Boolean network is to identify all the attractors. This becomes more challenging for large asynchronous Boolean networks, due to the asynchronous scheme. Existing methods are prohibited due to the well-known state-space explosion problem in large Boolean networks. In this paper, we tackle this challenge by proposing a SCC-based decomposition method. We prove the correctness of our proposed method and demonstrate its efficiency with two real-life biological networks.

KW - Asynchronous Boolean networks

KW - attractor detection

KW - binary decision diagram

KW - gene regulatory networks

KW - strongly connected components

UR - http://www.scopus.com/inward/record.url?scp=85049132883&partnerID=8YFLogxK

U2 - 10.1109/TCBB.2018.2850901

DO - 10.1109/TCBB.2018.2850901

M3 - Conference article

C2 - 29994682

AN - SCOPUS:85049132883

SN - 1545-5963

VL - 16

SP - 31

EP - 42

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

IS - 1

M1 - 8398459

ER -

Taming Asynchrony for Attractor Detection in Large Boolean Networks

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this