Cited By
View all- Toyoda M(2019)Bayesian selection probability estimation for probabilistic Boolean networksAsian Journal of Control10.1002/asjc.216621:6(2513-2520)Online publication date: 1-Jul-2019
Exact Identification of the Structure of a Probabilistic Boolean Network from Samples
Pages 1107 - 1116
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.
References
[1]
S. A. Kauffman, "Metabolic stability and epigenesis in randomly constructed genetic nets," J. Theor. Biol., vol. 22, no. 3, pp. 437-467, 1969.
[2]
S. A. Kauffman, The Origins of Order: Self-Organization and Selection in Evolution. New York, NY, USA: Oxford Univ. Press, 1993.
[3]
B. Samuelsson and C. Troein, "Superpolynomial growth in the number of attractors in Kauffman networks," Phys. Rev. Lett., vol. 90, p. 098701, 2003.
[4]
B. Drossel, T. Mihaljev, and F. Greil, "Number and length of attractors in a critical Kauffman model with connectivity one," Phys. Rev. Lett., vol. 94, p. 088701, 2005.
[5]
P. Krawitz and I. Shmulevich, "Basin entropy in Boolean network ensembles," Phys. Rev. Lett., vol. 98, p. 158701, 2007.
[6]
C. Seshadhri, Y. Vorobeychik, J. R. Mayo, R. C. Armstrong, and J. R. Ruthruff, "Influence and dynamic behavior in random Boolean networks," Phys. Rev. Lett., vol. 107, p. 108701, 2011.
[7]
S. Squires, E. Ott, and M. Girvan, "Dynamical instability in Boolean networks as a percolation problem," Phys. Rev. Lett., vol. 109, p. 085701, 2012.
[8]
S. Liang, S. Fuhrman, and R. Somogyi, "REVEAL, a general reverse engineering algorithm for inference of genetic network architectures," in Proc. Pacific Symp. Biocomput., 1998, pp. 18-29.
[9]
T. Akutsu, S. Miyano, and S. Kuhara, "Identification of genetic networks from a small number of gene expression patterns under the Boolean network model," in Proc. Pacific Symp. Biocomput., 1999, pp. 17-28.
[10]
R. Laubenbacher and B. Stigler, "A computational algebra approach to the reverse engineering of gene regulatory networks," J. Theor. Biol., vol. 229, pp. 523-537, 2004.
[11]
T. J. Perkins and M. T. Hallett, "A trade-off between sample complexity and computational complexity in learning Boolean networks from time-series data," IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 7, no. 1, pp. 118-128, Jan. 2010.
[12]
P. Vera-Licona1, A. S. Jarrah, L. D. Garcia-Puente, J. McGee, and R Laubenbacher, "An algebra-based method for inferring gene regulatory networks." BMC Syst. Biol., vol. 8, p. 37, 2014.
[13]
E. N. Miranda and N. Parga, "Noise effects in the Kauffman model," Europhys. Lett., vol. 10, pp. 293-298, 1989.
[14]
T. Akutsu, S. Miyano, and S. Kuhara, "Inferring qualitative relations in genetic networks and metabolic pathways," Bioinf., vol. 16, pp. 727-734, 2000.
[15]
T. P. Peixoto, "Redundancy and error resilience in Boolean networks," Phys. Rev. Lett., vol. 104, p. 048701, 2010.
[16]
I. Shmulevich, E. R. Dougherty, S. Kim, and W. Zhang, "Probabilistic Boolean networks: A rule-based uncertainty model for gene regulatory networks," Bioinformatics, vol. 18, pp. 261-274, 2001.
[17]
I. Shmulevich and E. R. Dougherty, Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks. Philadelphia, PA, USA: SIAM, 2010.
[18]
Y. Xiao, "A tutorial on analysis and simulation of boolean gene regulatory network models," Current Genomics, vol. 10, no. 7, pp. 511-525, 2009.
[19]
P. Trairatphisan, A. Mizera, J. Pang, A. A. Tantar, J. Schneider, and T. Sauter, "Recent development and biomedical applications of probabilistic Boolean networks," Cell Commun. Signal., vol. 11, p. 46, 2013.
[20]
A. Datta, A. Choudhary, M. L. Bittner, and E. R. Dougherty, "External control in Markovian genetic regulatory networks," Mach. Learn., vol. 52, pp. 169-191, 2003.
[21]
W-K. Ching, S. Zhang, M. Ng, and T. Akutsu, "An approximation method for solving the steady-state probability distribution of probabilistic Boolean networks," Bioinf., vol. 23, pp. 1511-1518, 2007.
[22]
B. Faryabi, G. Vahedi, A. Datta, J. F. Chamberland, and E. R. Dougherty, "Recent advances in intervention in markovian regulatory networks," Current Genomics, vol. 10, pp. 463-477, 2009.
[23]
K. Kobayashi and K. Hiraishi, "An integer programming approach to optimal control problems in context-sensitive probabilistic Boolean networks," Automatica, vol. 47, pp. 1260-1264, 2011.
[24]
S. Marshall, L. Yu, Y. Xiao, and E. R. Dougherty, "Inference of a probabilistic Boolean network from a single observed temporal sequence," EURASIP J. Bioinf. Syst. Biol., vol. 2007, p. 32454, 2007.
[25]
N. Friedman and Z. Yakhini, "On the sample complexity of learning Bayesian networks," in Proc. 20th Conf. Uncertainty Artif. Intell., 1996, pp. 274-282.
[26]
S. Dasgupta, "The sample complexity of learning fixed-structure Bayesian networks," Mach. Learn., vol. 29, nos. 2-3, pp. 165-180, 1997.
[27]
S. E. Harris, B. K. Sawhill, A. Wuensche, and S. Kauffman, "A model of transcriptional regulatory networks based on biases in the observed regulation rules," Complexity, vol. 7, pp. 23-40, 2002.
[28]
C. Müssel, M. Hopfensitz, and H. Kestler, "BoolNet-an R package for generation, reconstruction and analysis of Boolean networks," Bioinf., vol. 26, no. 10, pp. 1378-1380, 2010.
[29]
R. Pal, A. Datta, M. L. Bittner, and E. R. Dougherty, "Intervention in context-sensitive probabilistic Boolean networks," Bioinf., vol. 21, pp. 1211-1218, 2005.
[30]
A. Saadatpour and R. Albert, "Boolean modeling of biological regulatory networks: A methodology tutorial," Methods, vol. 62, no. 1, pp. 3-12, 2013.
[31]
M. Flöttmann, T. Scharp, and E. Klipp, "A stochastic model of epigenetic dynamics in somatic cell reprogramming," Front. Physiol., vol. 3, p. 216, 2012.
[32]
T. Mori, M. Flöttmann, M. Krantz, T. Akutsu, and E. Klipp, "Stochastic simulation of Boolean rxncon models: Towards quantitative analysis of large signaling networks," BMC Syst. Biol., vol. 9, p. 45, 2015.
[33]
B. Faryabi, G. Vahedi, J-F. Chamberland, A. Datta, and E. R. Dougherty, "Optimal constrained stationary intervention in gene regulatory networks," EURASIP J. Bioinform. Syst. Biol., vol. 2008, p. 620767, 2008.
[34]
X. Qian and E. R. Dougherty, "On the long-run sensitivity of probabilistic Boolean networks," J. Theoret. Biol., vol. 257, pp. 560-577, 2009.
[35]
P. Trairatphisan, A. Mizera, J. Pang, A. A. Tantar, and T. Sauter, "optPBN: An optimisation toolbox for probabilistic Boolean networks," PLoS ONE, vol. 9, no. 7, p. e105913, 2014.
[36]
R. Li, M. Yang, and T. Chua, "State feedback stabilization for probabilistic Boolean networks," Automatica, vol. 50, pp. 1272-1278, 2014.
Recommendations
Construction of Probabilistic Boolean Network for Credit Default Data
CSO '14: Proceedings of the 2014 Seventh International Joint Conference on Computational Sciences and OptimizationIn this article, we consider the problem of construction of Probabilistic Boolean Networks (PBNs). Previous works have shown that Boolean Networks (BNs) and PBNs have many potential applications in modeling genetic regulatory networks and credit default ...
Mappings between probabilistic boolean networks
Special issue: Genomic signal processingProbabilistic Boolean Networks (PBNs) comprise a graphical model based on uncertain rule-based dependencies between nodes and have been proposed as a model for genetic regulatory networks. As with any algebraic structure, the characterization of ...
Bisimulations of Probabilistic Boolean Networks
A probabilistic Boolean network (PBN) is a collection of Boolean networks endowed with a probability structure describing the likelihood with which a constituent network is active at each time step. This paper proposes a definition of bisimulation for PBNs. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2016.
Publisher
IEEE Computer Society Press
Washington, DC, United States
Publication History
Published: 01 November 2016
Published in TCBB Volume 13, Issue 6
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 32Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 20 Nov 2024
Other Metrics
Citations
Cited By
View all- Toyoda M(2019)Bayesian selection probability estimation for probabilistic Boolean networksAsian Journal of Control10.1002/asjc.216621:6(2513-2520)Online publication date: 1-Jul-2019
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in