maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2020-2-180-193mais-1324Research ArticleComputing Methodologies and ApplicationsМетод совместной кластеризации в графовом и корреляционном пространствахMethod of the Joint Clustering in Network and Correlation Spaceshttps://orcid.org/0000-0003-3796-2337ГайнуллинаАнастасия НаильевнаGainullinaAnastasiia N.

Аспирант

Кронверкский пр. 49, г. Санкт-Петербург, 197101

PhD student

49 Kronverkskiy Prospekt, Saint Petersburg 197101

anastasiia.gainullina@gmail.comhttps://orcid.org/0000-0002-2723-2077ШалытоАнатолий АбрамовичShalytoAnatoly A.

Гл. науч. сотр., профессор, докт. техн. наук

Кронверкский пр. 49, г. Санкт-Петербург, 197101

Chief researcher, professor, Doctor of Sciences

49 Kronverkskiy Prospekt, Saint Petersburg 197101

shalyto@mail.ifmo.ruhttps://orcid.org/0000-0003-1159-7220СергушичевАлексей АлександровичSergushichevAlexey A.

Доцент, канд. техн. наук

Кронверкский пр. 49, г. Санкт-Петербург, 197101

Associate professor, PhD

49 Kronverkskiy Prospekt, Saint Petersburg 197101

alserg@itmo.ruУниверситет ИТМОРоссияITMO UniversityRussian Federation202024062020272180193Copyright © Гайнуллина А.Н., Шалыто А.А., Сергушичев А.А., 20202020Гайнуллина А.Н., Шалыто А.А., Сергушичев А.А.Gainullina A.N., Shalyto A.A., Sergushichev A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1324

Алгоритмы на графах часто используются для анализа и интерпретации биологических данных. Одним из широко используемых подходов является решение задачи поиска активного модуля, в которой в графе биологических взаимодействий выделяется связный подграф, лучше всего отражающий разницу между двумя рассматриваемыми биологическими состояниями. В настоящей работе этот подход расширяется на случай большего числа биологических состояний и формулируется задача совместной кластеризации в графовом и корреляционном пространстве.

Для решения этой задачи предлагается итеративный метод, принимающий на вход граф G и матрицу X, в которой строки соответствуют вершинам графа. На выходе алгоритм выдает набор подграфов графа G так, что каждый подграф является связным и строки, соответствующие его вершинам, обладают высокой попарной корреляцией.

Эффективность метода подтверждается экспериментальным исследованием на смоделированных данных.

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.

активный модулькластеризацияэкспрессия геновбиологические графыactive moduleclustringgene expressionbiological networksПравительство Российской Федерации, субсидия 08-08.Government of Russian Federation, grant 08-08.ReferencesK. 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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.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.P. Langfelder and S. Horvath, “WGCNA: an R package for weighted correlation network analysis”, BMC Bioinformatics, vol. 9, p. 559, 2008.P. Langfelder and S. Horvath, “WGCNA: an R package for weighted correlation network analysis”, BMC Bioinformatics, vol. 9, p. 559, 2008.

The authors declare that there are no conflicts of interest present.