An Efficient Algorithm for Learning Bayesian Networks from Data

• Autorzy: Dojer N.
• Języki publikacji: EN

Abstrakty

EN

We propose an algorithm for learning an optimal Bayesian network from data. Our method is addressed to biological applications, where usually datasets are small, and sets of random variables are large. Moreover, we assume that there is no need to examine the acyclicity of the graph. We provide polynomial bounds (with respect to the number of random variables) for time complexity of our algorithm for two generally used scoring criteria: Minimal Description Length and Bayesian- Dirichlet equivalence. Then we show how to adapt these criteria to work with continuous data and prove polynomial bounds for adapted scores. Finally, we briefly describe applications of proposed algorithm in computational biology.

Słowa kluczowe

EN

algorithm for learning; Bayesian networks

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 103, nr 1-4
• Strony: 53--67
• Opis fizyczny: Bibliogr. 28 poz., wykr.

Twórcy

autor

Dojer N.

• Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warszawa, Poland,

Bibliografia

• [1] Beer, M. A., Tavazoie, S.: Predicting gene expression from sequence, Cell, 117(2), Apr 2004, 185-198.
• [2] Bottcher, S. G.: Learning Bayesian networks with mixed variables, Proceedings of the Eighth International Workshop in Artificial Intelligence and Statistics, 2001.
• [3] Chen, X., Blanchette, M.: Prediction of tissue-specific cis-regulatory modules using Bayesian networks and regression trees., BMC Bioinformatics, 8 Suppl 10, 2007, S2.
• [4] Chickering, D. M.: Learning Bayesian networks is NP-complete, in: Learning from Data: Artificial Inteligence and Statistics V (D. Fisher, H.-J. Lenz, Eds.), Springer-Verlag, 1996, 121-130.
• [5] Chickering, D. M., Heckerman, D., Meek, C.: Large-Sample Learning of Bayesian Networks is NP-Hard, Journal of Machine Learning Research, 5, Oct 2004, 1287-1330.
• [6] Cooper, G. F., Herskovits, E.: A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, 9, 1992, 309-347.
• [7] Dabrowski, M., Dojer, N., Zawadzka, M., Mieczkowski, J., Kaminska, B.: Comparative analysis of cisregulation following stroke and seizures in subspaces of conserved eigensystems., BMC Syst Biol, 4, 2010, 86.
• [8] Dasgupta, S.: Learning polytrees, Proceedings of the 15th Annual Conference on Uncertainty in Artificial Intelligence (UAI-99), Morgan Kaufmann Publishers, San Francisco, CA, 1999.
• [9] Dojer, N.: Learning Bayesian Networks Does Not Have to Be NP-Hard, Proceedings of Mathematical Foundations of Computer Science 2006 (R. Kr´alovic, P. Urzyczyn, Eds.), Springer-Verlag, 2006, LNCS 4162.
• [10] Dojer, N., Gambin, A., Wilczyński, B., Tiuryn, J.: Applying Dynamic Bayesian Networks to Perturbed Gene Expression Data, BMC Bioinformatics, 7, 2006, 249.
• [11] Edwards, D., de Abreu, G. C. G., Labouriau, R.: Selecting high-dimensional mixed graphical models using minimal AIC or BIC forests., BMC Bioinformatics, 11, 2010, 18.
• [12] Friedman, N., Koller, D.: Being Bayesian About Network Structure. A Bayesian Approach to Structure Discovery in Bayesian Networks, Machine Learning, 50, 2003, 95-125.
• [13] Friedman, N., Murphy, K., Russell, S.: Learning the structure of dynamic probabilistic networks, Proceedings of the Fourteenth Conference on Uncertainty in Artificial Inteligence (G. F. Cooper, S. Moral, Eds.), 1998.
• [14] Heckerman, D., Geiger, D., Chickering, D. M.: Learning Bayesian Networks: The Combination of Knowledge and Statistical Data, Machine Learning, 20(3), Sep. 1995, 197-243.
• [15] Kel-Margoulis, O. V., Kel, A. E., Reuter, I., Deineko, I. V., Wingender, E.: TRANSCompel: a database on composite regulatory elements in eukaryotic genes., Nucleic Acids Res, 30(1), Jan 2002, 332-334.
• [16] Lam, W., Bacchus, F.: Learning Bayesian Belief Networks: An Approach Based on the MDL Principle, Computational Intelligence, 10(3), 1994, 269-293.
• [17] Meek, C.: Finding a path is harder than finding a tree, J. Artificial Intelligence Res., 15, 2001, 383-389.
• [18] Monti, S., Cooper, G. F.: Learning hybrid Bayesian networks from data, in: Learning in Graphical Models (M. I. Jordan, Ed.), MIT Press, Cambridge, MA, USA, 1999, 521-540.
• [19] Neapolitan, R. E.: Learning Bayesian Networks, Prentice Hall, 2003.
• [20] Niida, A., Smith, A. D., Imoto, S., Tsutsumi, S., Aburatani, H., Zhang, M. Q., Akiyama, T.: Integrative bioinformatics analysis of transcriptional regulatory programs in breast cancer cells., BMC Bioinformatics, 9, 2008, 404.
• [21] Ott, S., Imoto, S., Miyano, S.: Finding optimal models for small gene networks, Pac. Symp. Biocomput., 2004, 557-567.
• [22] Sandve, G. K., Abul, O., Drabls, F.: Compo: composite motif discovery using discrete models., BMC Bioinformatics, 9, 2008, 527.
• [23] Segal, E., Yelensky, R., Koller, D.: Genome-wide Discovery of Transcriptional Modules from DNA Sequence and Gene Expression, Bioinformatics, 19 Suppl 1, 2003, 273-282.
• [24] Shen, L., Liu, J., Wang, W.: GBNet: deciphering regulatory rules in the co-regulated genes using a Gibbs sampler enhanced Bayesian network approach., BMC Bioinformatics, 9, 2008, 395.
• [25] Teyssier, M., Koller, D.: Ordering-based Search: A Simple and Effective Algorithm for Learning Bayesian Networks, Proceedings of the Twenty-first Conference on Uncertainty in AI (UAI), Edinburgh, Scottland, UK, July 2005.
• [26] Tian, J.: A Branch-and-Bound Algorithm for MDL Learning Bayesian Networks, Proceedings of the Proceedings of the Sixteenth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-00), Morgan Kaufmann, San Francisco, CA, 2000.
• [27] Wilczyński, B., Dojer, N.: BNFinder: exact and efficient method for learning Bayesian networks., Bioinformatics, 25(2), Jan 2009, 286-287.
• [28] Yuan, Y., Guo, L., Shen, L., Liu, J. S.: Predicting gene expression from sequence: a reexamination., PloS Comput Biol, 3(11), Nov 2007, e243.