zbMATH — the first resource for mathematics

Exploiting causality in gene network reconstruction based on graph embedding. (English) Zbl 07224999
Summary: Gene network reconstruction is a bioinformatics task that aims at modelling the complex regulatory activities that may occur among genes. This task is typically solved by means of link prediction methods that analyze gene expression data. However, the reconstructed networks often suffer from a high amount of false positive edges, which are actually the result of indirect regulation activities due to the presence of common cause and common effect phenomena or, in other terms, due to the fact that the adopted inductive methods do not take into account possible causality phenomena. This issue is accentuated even more by the inherent presence of a high amount of noise in gene expression data. Existing methods for the identification of a transitive reduction of a network or for the removal of (possibly) redundant edges suffer from limitations in the structure of the network or in the nature/length of the indirect regulation, and often require additional pre-processing steps to handle specific peculiarities of the networks (e.g., cycles). Moreover, they are not able to consider possible community structures and possible similar roles of the genes in the network (e.g. hub nodes), which may change the tendency of nodes to be highly connected (and with which nodes) in the network. In this paper, we propose the method INLOCANDA, which learns an inductive predictive model for gene network reconstruction and overcomes all the mentioned limitations. In particular, INLOCANDA is able to (i) identify and exploit indirect relationships of arbitrary length to remove edges due to common cause and common effect phenomena; (ii) take into account possible community structures and possible similar roles by means of graph embedding. Experiments performed along multiple dimensions of analysis on benchmark, real networks of two organisms (E. coli and S. cerevisiae) show a higher accuracy with respect to the competitors, as well as a higher robustness to the presence of noise in the data, also when a huge amount of (possibly false positive) interactions is removed. Availability: http://www.di.uniba.it/~gianvitopio/systems/inlocanda/
68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI
[1] Aha, DW; Kibler, D.; Albert, MK, Instance-based learning algorithms, Machine Learning, 6, 1, 37-66 (1991)
[2] Aho, AV; Garey, MR; Ullman, JD, The transitive reduction of a directed graph, SIAM Journal on Computing, 1, 2, 131-137 (1972) · Zbl 0247.05128
[3] Atias, N.; Sharan, R., Comparative analysis of protein networks: Hard problems, practical solutions, Communications of the ACM, 55, 5, 88-97 (2012)
[4] Babu, MM; Luscombe, NM; Aravind, L.; Gerstein, M.; Teichmann, SA, Structure and evolution of transcriptional regulatory networks, Current Opinion in Structural Biology, 14, 3, 283-291 (2004)
[5] Belkin, M.; Niyogi, P.; Dietterich, TG; Becker, S.; Ghahramani, Z., Laplacian eigenmaps and spectral techniques for embedding and clustering, Advances in neural information processing systems 14, 585-591 (2002), Cambridge: MIT Press, Cambridge
[6] Berger, MF; Bulyk, ML, Universal protein-binding microarrays for the comprehensive characterization of the DNA-binding specificities of transcription factors, Nature Protocols, 4, 3, 393-411 (2009)
[7] Blockeel, H.; Raedt, LD; Ramon, J.; Shavlik, JW, Top-down induction of clustering trees, ICML 1998, 55-63 (1998), Burlington: Morgan Kaufmann, Burlington
[8] Böck, M.; Ogishima, S.; Tanaka, H.; Kramer, S.; Kaderali, L., Hub-centered gene network reconstruction using automatic relevance determination, PLOS ONE, 7, 5, 1-17 (2012)
[9] Bošnački, D.; Odenbrett, MR; Wijs, A.; Ligtenberg, W.; Hilbers, P., Efficient reconstruction of biological networks via transitive reduction on general purpose graphics processors, BMC Bioinformatics, 13, 1, 281 (2012)
[10] Bulyk, ML, Discovering DNA regulatory elements with bacteria, Nature Biotechnology, 23, 8, 942-944 (2005)
[11] Ceci, M.; Pio, G.; Kuzmanovski, V.; Dẑeroski, S., Semi-supervised multi-view learning for gene network reconstruction, PLOS ONE, 10, 12, 1-27 (2015)
[12] Cohen, W. W. (1995). Fast effective rule induction. In Proceedings of the twelfth international conference on international conference on machine learning, ICML’95 (pp. 115-123). San Francisco, CA: Morgan Kaufmann Publishers Inc.
[13] de Jong, H., Modeling and simulation of genetic regulatory systems: A literature review, Journal of Computational Biology, 9, 1, 67-103 (2002)
[14] Demšar, J., Statistical comparisons of classifiers over multiple data sets, Journal of Machine Learning Research, 7, 1-30 (2006) · Zbl 1222.68184
[15] Emmert-Streib, F.; Glazko, G.; De Matos Simoes, R., Statistical inference and reverse engineering of gene regulatory networks from observational expression data, Bioinformatics and Computational Biology, 3, 8 (2012)
[16] Gallagher, B.; Eliassi-Rad, T.; Giles, L.; Smith, M.; Yen, J.; Zhang, H., Leveraging label-independent features for classification in sparsely labeled networks: An empirical study, Advances in Social Network Mining and Analysis, 1-19 (2010), Berlin: Springer, Berlin
[17] Geistlinger, L., Csaba, G., Dirmeier, S., Küffner, R., & Zimmer, R. (2013). A comprehensive gene regulatory network for the diauxic shift in saccharomyces cerevisiae. Nucleic Acids Research, 41(18), 8452-8463. doi:10.1093/nar/gkt631.
[18] Grover, A., & Leskovec, J. (2016). Node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’16 (pp. 855-864). New York, NY: ACM.
[19] Hase, T.; Ghosh, S.; Yamanaka, R.; Kitano, H., Harnessing diversity towards the reconstructing of large scale gene regulatory networks, PLoS Computational Biology, 9, 11, e1003361 (2013)
[20] Hecker, M.; Lambeck, S.; Toepfer, S.; Van Someren, E.; Guthke, R., Gene regulatory network inference: Data integration in dynamic models—A review, Biosystems, 96, 1, 86-103 (2009)
[21] Hempel, S.; Koseska, A.; Nikoloski, Z.; Kurths, J., Unraveling gene regulatory networks from time-resolved gene expression data—A measures comparison study, BMC Bioinformatics, 12, 1, 292 (2011)
[22] Henderson, K., Gallagher, B., Li, L., Akoglu, L., Eliassi-Rad, T., Tong, H., & Faloutsos, C. (2011). It’s who you know: Graph mining using recursive structural features. In Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’11 (pp. 663-671). New York: ACM.
[23] Hsu, HT, An algorithm for finding a minimal equivalent graph of a digraph, Journal of ACM, 22, 1, 11-16 (1975) · Zbl 0316.05114
[24] Ibarguren, I.; Lasarguren, A.; Pérez, JM; Muguerza, J.; Gurrutxaga, I.; Arbelaitz, O., Bfpart: Best-first part, Information Sciences, 367-368, 927-952 (2016)
[25] Itani, S., Ohannessian, M., Sachs, K., Nolan, G.P., & Dahleh, M.A. (2008). Structure learning in causal cyclic networks. In Proceedings of the international conference on causality: objectives and assessment—Vol. 6, COA’08 (pp. 165-176) JMLR.org.
[26] Korb, KB; Nicholson, AE, Bayesian Artificial Intelligence (2010), Boca Raton, FL: CRC Press Inc, Boca Raton, FL
[27] Li, J.; Xie, D., Rack1, a versatile hub in cancer, Oncogene, 34, 15, 1890-1898 (2015)
[28] Lo, L.; Wong, M.; Lee, K.; Leung, K., Time delayed causal gene regulatory network inference with hidden common causes, PLOS ONE, 10, 9, 1-47 (2015)
[29] Lü, L.; Zhou, T., Link prediction in complex networks: A survey, Physica A: Statistical Mechanics and its Applications, 390, 6, 1150-1170 (2011)
[30] Marbach, D.; Costello, JC; Küffner, R.; Vega, NM; Prill, RJ; Camacho, DM; Allison, KR; Kellis, M.; Collins, JJ; Stolovitzky, G., Wisdom of crowds for robust gene network inference, Nature Methods, 9, 796-804 (2012)
[31] Margolin, A.; Nemenman, I.; Basso, K.; Wiggins, C.; Stolovitzky, G.; Favera, R.; Califano, A., Aracne: An algorithm for the reconstruction of gene regulatory networks in a mammalian cellular context, BMC Bioinformatics, 7, Suppl 1, S7 (2006)
[32] Markowetz, F.; Spang, R., Inferring cellular networks—A review, BMC Bioinformatics, 8, Suppl 6, S5 (2007)
[33] Mikolov, T., Chen, K., Corrado, G. S., & Dean, J. (2013). Efficient estimation of word representations in vector space. CoRR arXiv:1301.3781
[34] Omranian, N.; Eloundou-Mbebi, JMO; Mueller-Roeber, B.; Nikoloski, Z., Gene regulatory network inference using fused lasso on multiple data sets, Scientific Reports, 6, 20533 (2016)
[35] Park, PJ, ChIP-seq: Advantages and challenges of a maturing technology, Nature Reviews Genetics, 10, 10, 669-680 (2009)
[36] Pearl, J., Causality: Models, reasoning, and inference (2000), New York, NY: Cambridge University Press, New York, NY · Zbl 0959.68116
[37] Penfold, CA; Wild, DL, How to infer gene networks from expression profiles, revisited, Interface Focus, 1, 6, 857-870 (2011)
[38] Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining, KDD ’14 (pp. 701-710). New York, NY: ACM.
[39] Pinna, A.; Soranzo, N.; de la Fuente, A., From knockouts to networks: Establishing direct cause-effect relationships through graph analysis, PLoS ONE, 10, 5, e12912 (2010)
[40] Pio, G.; Ceci, M.; Malerba, D.; D’Elia, D., ComiRNet: A web-based system for the analysis of miRNA-gene regulatory networks, BMC Bioinformatics, 16, 9, S7 (2015)
[41] Pio, G.; Ceci, M.; Prisciandaro, F.; Malerba, D.; Yamamoto, A.; Kida, T.; Uno, T.; Kuboyama, T., LOCANDA: Exploiting causality in the reconstruction of gene regulatory networks, Discovery science 2017, Lecture notes in computer science, 283-297 (2017), Berlin: Springer, Berlin
[42] Roweis, ST; Saul, LK, Nonlinear dimensionality reduction by locally linear embedding, Science, 290, 5500, 2323-2326 (2000)
[43] Selvanathan, SP; Graham, GT; Erkizan, HV; Dirksen, U.; Natarajan, TG; Dakic, A.; Yu, S.; Liu, X.; Paulsen, MT; Ljungman, ME; Wu, CH; Lawlor, ER; Üren, A.; Toretsky, JA, Oncogenic fusion protein ews-fli1 is a network hub that regulates alternative splicing, Proceedings of the National Academy of Sciences, 112, 11, E1307-E1316 (2015)
[44] Tang, J., Qu, M., Wang, M., Zhang, M., Yan, J., & Mei, Q. (2015). Line: Large-scale information network embedding. In Proceedings of the 24th international conference on world wide web, WWW ’15 (pp. 1067-1077). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland.
[45] Tenenbaum, JB; Silva, VD; Langford, JC, A global geometric framework for nonlinear dimensionality reduction, Science, 290, 5500, 2319-2323 (2000)
[46] Thattai, M.; van Oudenaarden, A., Intrinsic noise in gene regulatory networks, Proceedings of the National Academy of Sciences, 98, 15, 8614-8619 (2001)
[47] Van den Bulcke, T.; Van Leemput, K.; Naudts, B.; van Remortel, P.; Ma, H.; Verschoren, A.; De Moor, B.; Marchal, K., SynTReN: A generator of synthetic gene expression data for design and analysis of structure learning algorithms, BMC Bioinformatics, 7, 43 (2006)
[48] Vilalta, R.; Drissi, Y., A perspective view and survey of meta-learning, Artificial Intelligence Review, 18, 2, 77-95 (2002)
[49] Yu, D.; Lim, J.; Wang, X.; Liang, F.; Xiao, G., Enhanced construction of gene regulatory networks using hub gene information, BMC Bioinformatics, 18, 1, 186 (2017)
[50] Zitnik, M.; Zupan, B., Data imputation in epistatic MAPs by network-guided matrix completion, Journal of Computational Biology, 22, 6, 595-608 (2015)
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.