Identification of co-existing embeddings of a motif in multilayer networks
Identification of co-existing embeddings of a motif in multilayer networks
复制标题
DOI：
10.1145/3535508.3545528
复制
发表时间：
2022-08
期刊：
影响因子：
--
通讯作者：
Yuanfang Ren;Aisharjya Sarkar;Aysegül Bumin;Kejun Huang;P. Veltri;Alin Dobra;Tamer Kahveci
中科院分区：
文献类型：
--
作者：
Yuanfang Ren;Aisharjya Sarkar;Aysegül Bumin;Kejun Huang;P. Veltri;Alin Dobra;Tamer Kahveci
分子之间的相互作用，也称为生物网络，通常被建模为二元图，其中节点和边代表分子以及这些分子之间的相互作用，例如信号传输、基因调节和蛋白质-蛋白质相互作用。在这些网络中重复出现的子图模式（称为基序）描述了保守的生物功能。尽管传统的二元图提供了研究生物相互作用的简单模型，但随着相互作用拓扑在不同应激条件以及遗传变异下的改变和采用，它缺乏表达能力来提供细胞行为的整体视图。多层网络模型捕获了此类系统的单元功能的复杂性。与经典的二元网络模型不同，多层网络模型提供了识别不同条件下细胞中保守功能的机会。在本文中，我们介绍了多层网络中共存主题的问题。这些主题描述了网络层内（即细胞状况）以及网络不同层之间细胞功能的双重保守。我们提出了一种新算法来有效、准确地解决共存主题识别问题。我们对合成数据集和真实数据集的实验表明，我们的方法能够以接近 100% 的准确度识别我们测试的所有网络的所有共存主题，而竞争方法的准确度在 10% 到 95% 之间变化很大。此外，我们的方法的运行速度比二进制网络模型的最先进的主题识别方法至少快一个数量级。
Interactions among molecules, also known as biological networks, are often modeled as binary graphs, where nodes and edges represent the molecules and the interaction among those molecules, such as signal transmission, genes-regulation, and protein-protein interactions. Subgraph patterns which are recurring in these networks, called motifs, describe conserved biological functions. Although traditional binary graph provides a simple model to study biological interactions, it lacks the expressive power to provide a holistic view of cell behavior as the interaction topology alters and adopts under different stress conditions as well as genetic variations. Multilayer network model captures the complexity of cell functions for such systems. Unlike the classic binary network model, multilayer network model provides an opportunity to identify conserved functions in cell among varying conditions. In this paper, we introduce the problem of co-existing motifs in multilayer networks. These motifs describe the dual conservation of the functions of cells within a network layer (i.e., cell condition) as well as across different layers of networks. We propose a new algorithm to solve the co-existing motif identification problem efficiently and accurately. Our experiments on both synthetic and real datasets demonstrate that our method identifies all co-existing motifs at near 100 % accuracy for all networks we tested on, while competing method's accuracy varies greatly between 10 to 95 %. Furthermore, our method runs at least an order of magnitude faster than state of the art motif identification methods for binary network models.