Exact Identification of the Structure of a Probabilistic Boolean Network from Samples

Xiaoqing Cheng; Tomoya Mori; Yushan Qiu; Wai-Ki Ching; Tatsuya Akutsu

doi:10.1109/TCBB.2015.2505310

Exact Identification of the Structure of a Probabilistic Boolean Network from Samples

IEEE/ACM Trans Comput Biol Bioinform. 2016 Nov-Dec;13(6):1107-1116. doi: 10.1109/TCBB.2015.2505310. Epub 2015 Dec 3.

Authors

Xiaoqing Cheng, Tomoya Mori, Yushan Qiu, Wai-Ki Ching, Tatsuya Akutsu

PMID: 26661790
DOI: 10.1109/TCBB.2015.2505310

Abstract

We study the number of samples required to uniquely determine the structure of a probabilistic Boolean network (PBN), where PBNs are probabilistic extensions of Boolean networks. We show via theoretical analysis and computational analysis that the structure of a PBN can be exactly identified with high probability from a relatively small number of samples for interesting classes of PBNs of bounded indegree. On the other hand, we also show that there exist classes of PBNs for which it is impossible to uniquely determine the structure of a PBN from samples.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Computer Simulation
Data Interpretation, Statistical*
Gene Expression Regulation / physiology*
Models, Biological*
Models, Statistical*
Proteome / metabolism*
Sample Size
Signal Transduction / physiology*

Substances

Proteome