Method of the Joint Clustering in Network and Correlation Spaces
https://doi.org/10.18255/1818-1015-2020-2-180-193
Abstract
Network algorithms are often used to analyze and interpret the biological data. One of the widely used approaches is to solve the problem of identifying an active module, where a connected subnetwork of a biological network is selected which best reflects the difference between the two considered biological conditions. In this work this approach is extended to the case of a larger number of biological conditions and the problem of the joint clustering in network and correlation spaces is formulated.
To solve this problem, an iterative method is proposed at takes as the input graph G and matrix X, in which the rows correspond to the vertices of the graph. As the output, the algorithm produces a set of subgraphs of the graph G so that each subgraph is connected and the rows corresponding to its vertices have a high pairwise correlation. The efficiency of the method is confirmed by an experimental study on the simulated data.
Supporting agencies: Government of Russian Federation, grant 08-08.
About the Authors
Anastasiia N. Gainullina
ITMO University
Russian Federation
Russian Federation
PhD student
49 Kronverkskiy Prospekt, Saint Petersburg 197101
Anatoly A. Shalyto
ITMO University
Russian Federation
Russian Federation
Chief researcher, professor, Doctor of Sciences
49 Kronverkskiy Prospekt, Saint Petersburg 197101
Alexey A. Sergushichev
ITMO University
Russian Federation
Russian Federation
Associate professor, PhD
49 Kronverkskiy Prospekt, Saint Petersburg 197101
References
1. K. Mitra, A. R. Carvunis, S. K. Ramesh, and T. Ideker, “Integrative approaches for finding modular structure in biological networks”, Nat. Rev. Genet., vol. 14, no. 10, pp. 719–732, 2013.
2. E. J. Rossin et al., “Proteins encoded in genomic regions associated with immune-mediated disease physically interact and suggest underlying biology”, PLoS Genet., vol. 7, no. 1, e1001273, 2011.
3. A. K. Jha, S. C. Huang, A. Sergushichev, V. Lampropoulou, Y. Ivanova, E. Loginicheva, K. Chmielewski, K. M. Stewart, J. Ashall, B. Everts, E. J. Pearce, E. M. Driggers, and M. N. Artyomov, “Network integration of parallel metabolic and transcriptional data reveals metabolic modules that regulate macrophage polarization”, Immunity, vol. 42, no. 3, pp. 419–430, 2015.
4. M. D. Leiserson et al., “Pan-cancer network analysis identifies combinations of rare somatic mutations across pathways and protein complexes”, Nat. Genet., vol. 47, no. 2, pp. 106–114, 2015.
5. T. Ideker, O. Ozier, B. Schwikowski, and A. F. Siegel, “Discovering regulatory and signalling circuits in molecular interaction networks”, Bioinformatics (Oxford, England), vol. 18 Suppl 1, S233–S240, 2002.
6. M. T. Ditrich, G. W. Klau, A. Rosenwald, T. Dandekar, and T. Müller, “Identifying functional modules in protein-protein interaction networks: an integrated exact approach.”, Bioinformatics (Oxford, England), vol. 24, no. 13, pp. i223–31, 2008, issn: 1367-4811. doi: 10.1093/bioinformatics/btn161.
7. M. N. Artyomov, A. Sergushichev, and J. D. Schilling, “Integrating immunometabolism and macrophage diversity”, Semin. Immunol., vol. 28, no. 5, pp. 417–424, Oct. 2016.
8. A. A. Loboda, M. N. Artyomov, and A. A. Sergushichev, “Solving Generalized Maximum-Weight Connected Subgraph Problem for Network Enrichment Analysis”, in Algorithms in Bioinformatics: 16th International Workshop, WABI 2016, Aarhus, Denmark, August 22-24, 2016. Proceedings. Cham: Springer International Publishing, 2016, pp. 210–221, isbn: 978-3-319-43681-4.
9. E.´Alvarez-Miranda and M. Sinnl, “A Relax-and-Cut framework for large-scale maximum weight connected subgraph problems”, Computers & Operations Research, vol. 87, pp. 63–82, 2017.
10. P. Langfelder and S. Horvath, “WGCNA: an R package for weighted correlation network analysis”, BMC Bioinformatics, vol. 9, p. 559, 2008.
Review
For citations:
Gainullina A.N., Shalyto A.A., Sergushichev A.A. Method of the Joint Clustering in Network and Correlation Spaces. Modeling and Analysis of Information Systems. 2020;27(2):180-193. (In Russ.) https://doi.org/10.18255/1818-1015-2020-2-180-193
Views:
975
Email this article 