SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

This article is part of the series Genetic Regulatory Networks.

Open Access Research Article

Inference of a Probabilistic Boolean Network from a Single Observed Temporal Sequence

Stephen Marshall1*, Le Yu1, Yufei Xiao2 and Edward R Dougherty234

Author Affiliations

1 Department of Electronic and Electrical Engineering, Faculty of Engineering, University of Strathclyde, Glasgow, G1 1XW, UK

2 Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843-3128, USA

3 Computational Biology Division, Translational Genomics Research Institute, Phoenix, AZ 85004, USA

4 Department of Pathology, University of Texas M. D. Anderson Cancer Center, Houston, TX 77030, USA

For all author emails, please log on.

EURASIP Journal on Bioinformatics and Systems Biology 2007, 2007:32454  doi:10.1155/2007/32454

The electronic version of this article is the complete one and can be found online at: http://bsb.eurasipjournals.com/content/2007/1/32454

Received:10 July 2006
Revisions received:29 January 2007
Accepted:26 February 2007
Published:7 May 2007

© 2007 Stephen Marshall et al.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

The inference of gene regulatory networks is a key issue for genomic signal processing. This paper addresses the inference of probabilistic Boolean networks (PBNs) from observed temporal sequences of network states. Since a PBN is composed of a finite number of Boolean networks, a basic observation is that the characteristics of a single Boolean network without perturbation may be determined by its pairwise transitions. Because the network function is fixed and there are no perturbations, a given state will always be followed by a unique state at the succeeding time point. Thus, a transition counting matrix compiled over a data sequence will be sparse and contain only one entry per line. If the network also has perturbations, with small perturbation probability, then the transition counting matrix would have some insignificant nonzero entries replacing some (or all) of the zeros. If a data sequence is sufficiently long to adequately populate the matrix, then determination of the functions and inputs underlying the model is straightforward. The difficulty comes when the transition counting matrix consists of data derived from more than one Boolean network. We address the PBN inference procedure in several steps: (1) separate the data sequence into "pure" subsequences corresponding to constituent Boolean networks; (2) given a subsequence, infer a Boolean network; and (3) infer the probabilities of perturbation, the probability of there being a switch between constituent Boolean networks, and the selection probabilities governing which network is to be selected given a switch. Capturing the full dynamic behavior of probabilistic Boolean networks, be they binary or multivalued, will require the use of temporal data, and a great deal of it. This should not be surprising given the complexity of the model and the number of parameters, both transitional and static, that must be estimated. In addition to providing an inference algorithm, this paper demonstrates that the data requirement is much smaller if one does not wish to infer the switching, perturbation, and selection probabilities, and that constituent-network connectivity can be discovered with decent accuracy for relatively small time-course sequences.

Research Article


  1. ER Dougherty, A Datta, C Sima, Research issues in genomic signal processing. IEEE Signal Processing Magazine 22(6), 46–68 (2005)

  2. T Akutsu, S Miyano, S Kuhara, Identification of genetic networks from a small number of gene expression patterns under the Boolean network model. Proceedings of the 4th Pacific Symposium on Biocomputing (PSB '99), Mauna Lani, Hawaii, USA, January 1999, 17–28

  3. H Lähdesmäki, I Shmulevich, O Yli-Harja, On learning gene regulatory networks under the Boolean network model. Machine Learning 52(1-2), 147–167 (2003)

  4. S Liang, S Fuhrman, R Somogyi, REVEAL, a general reverse engineering algorithm for inference of genetic network architectures. Proceedings of the 3rd Pacific Symposium on Biocomputing (PSB '98), Maui, Hawaii, USA, January 1998, 18–29

  5. R Pal, I Ivanov, A Datta, ML Bittner, ER Dougherty, Generating Boolean networks with a prescribed attractor structure. Bioinformatics 21(21), 4021–4025 (2005). PubMed Abstract | Publisher Full Text OpenURL

  6. X Zhou, X Wang, ER Dougherty, Construction of genomic networks using mutual-information clustering and reversible-jump Markov-chain-Monte-Carlo predictor design. Signal Processing 83(4), 745–761 (2003). Publisher Full Text OpenURL

  7. RF Hashimoto, S Kim, I Shmulevich, W Zhang, ML Bittner, ER Dougherty, Growing genetic regulatory networks from seed genes. Bioinformatics 20(8), 1241–1247 (2004). PubMed Abstract | Publisher Full Text OpenURL

  8. X Zhou, X Wang, R Pal, I Ivanov, ML Bittner, ER Dougherty, A Bayesian connectivity-based approach to constructing probabilistic gene regulatory networks. Bioinformatics 20(17), 2918–2927 (2004). PubMed Abstract | Publisher Full Text OpenURL

  9. ER Dougherty, Y Xiao, Design of probabilistic Boolean networks under the requirement of contextual data consistency. IEEE Transactions on Signal Processing 54(9), 3603–3613 (2006)

  10. D Pe'er, A Regev, G Elidan, N Friedman, Inferring subnetworks from perturbed expression profiles. Bioinformatics 17(supplement 1), S215–S224 (2001). PubMed Abstract | Publisher Full Text OpenURL

  11. D Husmeier, Sensitivity and specificity of inferring genetic regulatory interactions from microarray experiments with dynamic Bayesian networks. Bioinformatics 19(17), 2271–2282 (2003). PubMed Abstract | Publisher Full Text OpenURL

  12. JM Peña, J Björkegren, J Tegnér, Growing Bayesian network models of gene networks from seed genes. Bioinformatics 21(supplement 2), ii224–ii229 (2005). PubMed Abstract | Publisher Full Text OpenURL

  13. H Lähdesmäki, S Hautaniemi, I Shmulevich, O Yli-Harja, Relationships between probabilistic Boolean networks and dynamic Bayesian networks as models of gene regulatory networks. Signal Processing 86(4), 814–834 (2006). PubMed Abstract | Publisher Full Text | PubMed Central Full Text OpenURL

  14. SA Kauffman, Metabolic stability and epigenesis in randomly constructed genetic nets. Journal of Theoretical Biology 22(3), 437–467 (1969). PubMed Abstract | Publisher Full Text OpenURL

  15. SA Kauffman, Homeostasis and differentiation in random genetic control networks. Nature 224(5215), 177–178 (1969). PubMed Abstract | Publisher Full Text OpenURL

  16. SA Kauffman, The Origins of Order: Self-Organization and Selection in Evolution (Oxford University Press, New York, NY, USA, 1993)

  17. S Huang, Gene expression profiling, genetic networks, and cellular states: an integrating concept for tumorigenesis and drug discovery. Journal of Molecular Medicine 77(6), 469–480 (1999). PubMed Abstract | Publisher Full Text OpenURL

  18. I Shmulevich, ER Dougherty, S Kim, W Zhang, Probabilistic Boolean networks: a rule-based uncertainty model for gene regulatory networks. Bioinformatics 18(2), 261–274 (2002). PubMed Abstract | Publisher Full Text OpenURL

  19. S Kim, H Li, ER Dougherty, et al. Can Markov chain models mimic biological regulation? Journal of Biological Systems 10(4), 337–357 (2002). Publisher Full Text OpenURL

  20. I Shmulevich, ER Dougherty, W Zhang, From Boolean to probabilistic Boolean networks as models of genetic regulatory networks. Proceedings of the IEEE 90(11), 1778–1792 (2002). Publisher Full Text OpenURL

  21. I Shmulevich, ER Dougherty, Modeling genetic regulatory networks with probabilistic Boolean networks. in Genomic Signal Processing and Statistics, EURASIP Book Series on Signal Processing and Communication, Hindawi, New York, NY, USA, 2005, ed. by Dougherty ER, Shmulevich I, Chen J, Wang ZJ, pp. 241–279 (2005)

  22. A Datta, A Choudhary, ML Bittner, ER Dougherty, External control in Markovian genetic regulatory networks. Machine Learning 52(1-2), 169–191 (2003)

  23. R Pal, A Datta, ML Bittner, ER Dougherty, Intervention in context-sensitive probabilistic Boolean networks. Bioinformatics 21(7), 1211–1218 (2005). PubMed Abstract | Publisher Full Text OpenURL

  24. R Pal, A Datta, ER Dougherty, Optimal infinite-horizon control for probabilistic Boolean networks. IEEE Transactions on Signal Processing 54(6, part 2), 2375–2387 (2006)

  25. A Datta, R Pal, ER Dougherty, Intervention in probabilistic gene regulatory networks. Current Bioinformatics 1(2), 167–184 (2006). Publisher Full Text OpenURL

  26. R Albert, HG Othmer, The topology of the regulatory interactions predicts the expression pattern of the segment polarity genes in Drosophila melanogaster. Journal of Theoretical Biology 223(1), 1–18 (2003). PubMed Abstract | Publisher Full Text OpenURL

  27. G Langholz, A Kandel, JL Mott, Foundations of Digital Logic Design (World Scientific, River Edge, NJ, USA, 1998)

  28. I Ivanov, ER Dougherty, Modeling genetic regulatory networks: continuous or discrete? Journal of Biological Systems 14(2), 219–229 (2006). Publisher Full Text OpenURL

  29. I Ivanov, ER Dougherty, Reduction mappings between probabilistic Boolean networks. EURASIP Journal on Applied Signal Processing 2004(1), 125–131 (2004). Publisher Full Text OpenURL

  30. W-K Ching, MK Ng, ES Fung, T Akutsu, On construction of stochastic genetic networks based on gene expression sequences. International Journal of Neural Systems 15(4), 297–310 (2005). PubMed Abstract | Publisher Full Text OpenURL

  31. MK Ng, S-Q Zhang, W-K Ching, T Akutsu, A control model for Markovian genetic regulatory networks. Transactions on Computational Systems Biology V, Lecture Notes in Computer Science, 36–48 (2006)