×

zbMATH — the first resource for mathematics

High-dimensional structure learning of binary pairwise Markov networks: a comparative numerical study. (English) Zbl 07135456
Summary: Learning the undirected graph structure of a Markov network from data is a problem that has received a lot of attention during the last few decades. As a result of the general applicability of the model class, a myriad of methods have been developed in parallel in several research fields. Recently, as the size of the considered systems has increased, the focus of new methods has been shifted towards the high-dimensional domain. In particular, introduction of the pseudo-likelihood function has pushed the limits of score-based methods which were originally based on the likelihood function. At the same time, methods based on simple pairwise tests have been developed to meet the challenges arising from increasingly large data sets in computational biology. Apart from being applicable to high-dimensional problems, methods based on the pseudo-likelihood and pairwise tests are fundamentally very different. To compare the accuracy of the different types of methods, an extensive numerical study is performed on data generated by binary pairwise Markov networks. A parallelizable Gibbs sampler, based on restricted Boltzmann machines, is proposed as a tool to efficiently sample from sparse high-dimensional networks. The results of the study show that pairwise methods can be more accurate than pseudo-likelihood methods in settings often encountered in high-dimensional structure learning applications.
MSC:
62 Statistics
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alanis-Lobato, G., CNM - a Matlab toolbox for the construction of artificial complex networks (2014), https://se.mathworks.com/matlabcentral/fileexchange/45734-cnm
[2] Barabási, A.-L.; Albert, R., Emergence of scaling in random networks, Science, 286, 5439, 509-512 (1999) · Zbl 1226.05223
[3] Barber, R. F.; Drton, M., High-dimensional Ising model selection with Bayesian information criteria, Electron. J. Stat., 9, 1, 567-607 (2015) · Zbl 1309.62050
[4] Besag, J., Statistical analysis of non-lattice data, J. R. Stat. Soc. Ser. D. Stat., 24, 179-195 (1975)
[5] Butte, A. J.; Kohane, I. S., Mutual information relevance networks: Functional genomic clustering using pairwise entropy measurements, Pac. Symp. Biocomput., 5, 415-426 (2000)
[6] de Oliveira, S. H.; Shi, J.; Deane, C. M., Comparing co-evolution methods and their application to template-free protein structure prediction, Bioinformatics, 33, 3, 373-381 (2016)
[7] Ekeberg, M.; Hartonen, T.; Aurell, E., Fast pseudolikelihood maximization for direct-coupling analysis of protein structure from many homologous amino-acid sequences, J. Comput. Phys., 276, 341-356 (2014) · Zbl 1349.92108
[8] Ekeberg, M.; Lövkvist, C.; Lan, Y.; Weigt, M.; Aurell, E., Improved contact prediction in proteins: Using pseudolikelihoods to infer Potts models, Phys. Rev. E, 87, 012707 (2013)
[9] Faith, J. J.; Hayete, B.; Thaden, J. T.; Mogno, I.; Wierzbowski, J.; Cottarel, G.; Kasif, S.; Collins, J. J.; Gardner, T. S., Large-scale mapping and validation of Escherichia coli transcriptional regulation from a compendium of expression profiles, PLoS Biol., 5, 1, Article e8 pp. (2007)
[10] Fan, R.-E.; Chang, K.-W.; Hsieh, C.-J.; Wang, X.-R.; Lin, C.-J., LIBLINEAR: A library for large linear classification, J. Mach. Learn. Res., 9, 1871-1874 (2008) · Zbl 1225.68175
[11] Feizi, S.; Marbach, D.; Medard, M.; Kellis, M., Network deconvolution as a general method to distinguish direct dependencies in networks, Nature Biotechnol., 31, 8, 726-733 (2013)
[12] Hoerl, A. E.; Kennard, R. W., Ridge regression: Biased estimation for nonorthogonal problems, Technometrics, 12, 1, 55-67 (1970) · Zbl 0202.17205
[13] Höfling, H.; Tibshirani, R., Estimation of sparse binary pairwise Markov networks using pseudo-likelihoods, J. Mach. Learn. Res., 10, 883-906 (2009) · Zbl 1245.62121
[14] Hyvärinen, A., Consistency of pseudolikelihood estimation of fully visible Boltzmann machines, Neural Comput., 18, 10, 2283-2292 (2006) · Zbl 1114.68055
[15] Koller, D.; Friedman, N., Probabilistic Graphical Models: Principles and Techniques (2009), MIT Press
[16] Lee, S.-I.; Ganapathi, V.; Koller, D., Efficient structure learning of Markov networks using ℓ1-regularization, (Advances in Neural Information Processing Systems 19 (2006)), 817-824
[17] Margolin, A. A.; Nemenman, I.; Basso, K.; Wiggins, C.; Stolovitzky, G.; Favera, R. D.; Califano, A., ARACNE: An algorithm for the reconstruction of gene regulatory networks in a mammalian cellular context, BMC Bioinformatics, 7, Suppl 1, S7 (2006)
[19] Meinshausen, N.; Bühlmann, P., High-dimensional graphs and variable selection with the Lasso, Ann. Statist., 34, 3, 1436-1462 (2006) · Zbl 1113.62082
[20] Puranen, S.; Pesonen, M.; Pensar, J.; Xu, Y. Y.; Lees, J. A.; Bentley, S. D.; Croucher, N. J.; Corander, J., SuperDCA for genome-wide epistasis analysis, Microb. Genom., 4, 6, 1-12 (2018)
[21] Ravikumar, P.; Wainwright, M. J.; Lafferty, J. D., High-dimensional Ising model selection using ℓ1-regularized logistic regression, Ann. Statist., 38, 1287-1319 (2010) · Zbl 1189.62115
[22] Schmidt, M., Graphical Model Structure Learning with L1-Regularization (2010), University of British Columbia, (Ph.D. thesis)
[23] Schmidt, M., L1General - Matlab code for solving L1-regularization problems (2010), https://www.cs.ubc.ca/ schmidtm/Software/L1General.html
[24] Skwark, M. J.; Croucher, N. J.; Puranen, S.; Chewapreecha, C.; Pesonen, M.; Xu, Y. Y.; Turner, P.; Harris, S. R.; Beres, S. B.; Musser, J. M.; Parkhill, J.; Bentley, S. D.; Aurell, E.; Corander, J., Interacting network of resistence, virulence and core machinery genes identified by genome-wide epistasis analysis, PLoS Genet., 13, 2, Article e1006508 pp. (2017)
[25] Watts, D. J.; Strogatz, S. H., Collective dynamics of small-world networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139
[26] Whittaker, J., Graphical models in applied multivariate statistics (1990), Wiley: Wiley Chichester · Zbl 0732.62056
[28] Xu, Y.; Puranen, S.; Corander, J.; Kabashima, Y., Inverse finite-size scaling for high-dimensional significance analysis, Phys. Rev. E, 97, 6, 062112 (2018)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.