Метод совместной кластеризации в графовом и корреляционном пространствах
https://doi.org/10.18255/1818-1015-2020-2-180-193
Аннотация
Алгоритмы на графах часто используются для анализа и интерпретации биологических данных. Одним из широко используемых подходов является решение задачи поиска активного модуля, в которой в графе биологических взаимодействий выделяется связный подграф, лучше всего отражающий разницу между двумя рассматриваемыми биологическими состояниями. В настоящей работе этот подход расширяется на случай большего числа биологических состояний и формулируется задача совместной кластеризации в графовом и корреляционном пространстве.
Для решения этой задачи предлагается итеративный метод, принимающий на вход граф G и матрицу X, в которой строки соответствуют вершинам графа. На выходе алгоритм выдает набор подграфов графа G так, что каждый подграф является связным и строки, соответствующие его вершинам, обладают высокой попарной корреляцией.
Эффективность метода подтверждается экспериментальным исследованием на смоделированных данных.
При поддержке: Правительство Российской Федерации, субсидия 08-08.
Об авторах
Анастасия Наильевна Гайнуллина
Университет ИТМО
Россия
Россия
Аспирант
Кронверкский пр. 49, г. Санкт-Петербург, 197101
Анатолий Абрамович Шалыто
Университет ИТМО
Россия
Россия
Гл. науч. сотр., профессор, докт. техн. наук
Кронверкский пр. 49, г. Санкт-Петербург, 197101
Алексей Александрович Сергушичев
Университет ИТМО
Россия
Россия
Доцент, канд. техн. наук
Кронверкский пр. 49, г. Санкт-Петербург, 197101
Список литературы
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.
Рецензия
Для цитирования:
Гайнуллина А.Н., Шалыто А.А., Сергушичев А.А. Метод совместной кластеризации в графовом и корреляционном пространствах. Моделирование и анализ информационных систем. 2020;27(2):180-193. https://doi.org/10.18255/1818-1015-2020-2-180-193
For citation:
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
Просмотров:
937
Послать статью по эл. почте 