Mining functional subgraphs from cancer protein-protein interaction networks.
Mining functional subgraphs from cancer protein-protein interaction networks.
复制标题
DOI：
10.1186/1752-0509-6-s3-s2
复制
发表时间：
2012
影响因子：
--
通讯作者：
Guda C
中科院分区：
文献类型：
--
作者：
Shen R;Goonesekere NC;Guda C
蛋白质-蛋白质相互作用(PPI)网络携带有关蛋白质功能的重要信息。分析与包括癌症在内的特定疾病系统相关的PPI网络有助于我们理解疾病的复杂生物学。具体地说，识别跨PPI网络的相似和频繁出现的模式(网络主题)将为更好地理解疾病的生物学提供有用的线索。在这项研究中，我们开发了一种新的模式挖掘算法，该算法可以检测出现在多个癌症PPI网络中的癌症相关功能子图。我们使用来自Oncomine数据集的差异表达基因构建了九个癌症PPI网络。从这些网络中，我们发现了在所有网络中和不同规模级别出现的频繁模式。模式是抽象子图，其节点被节点集群ID替换。通过使用有效的规范标号和采用加权邻接矩阵，我们能够在多项式运行时间内进行图的同构测试。我们使用自下而上的模式增长方法来搜索模式，这使得我们可以随着模式大小的增长而有效地减少搜索空间。使用GO语义相似度对频繁常见模式的验证表明，在每个大小级别，发现的子图的得分始终高于随机生成的子图。我们使用基于文献的证据进一步研究了一组精选的子图与癌症的相关性。癌症PPI网络中存在频繁的常见模式，通过有效的模式挖掘算法可以发现这些常见模式。我们相信，这项工作将使我们能够识别癌症网络中功能相关和连贯的子图，这可以推进到实验验证，以进一步了解癌症的复杂生物学。
Protein-protein interaction (PPI) networks carry vital information about proteins' functions. Analysis of PPI networks associated with specific disease systems including cancer helps us in the understanding of the complex biology of diseases. Specifically, identification of similar and frequently occurring patterns (network motifs) across PPI networks will provide useful clues to better understand the biology of the diseases. In this study, we developed a novel pattern-mining algorithm that detects cancer associated functional subgraphs occurring in multiple cancer PPI networks. We constructed nine cancer PPI networks using differentially expressed genes from the Oncomine dataset. From these networks we discovered frequent patterns that occur in all networks and at different size levels. Patterns are abstracted subgraphs with their nodes replaced by node cluster IDs. By using effective canonical labeling and adopting weighted adjacency matrices, we are able to perform graph isomorphism test in polynomial running time. We use a bottom-up pattern growth approach to search for patterns, which allows us to effectively reduce the search space as pattern sizes grow. Validation of the frequent common patterns using GO semantic similarity showed that the discovered subgraphs scored consistently higher than the randomly generated subgraphs at each size level. We further investigated the cancer relevance of a select set of subgraphs using literature-based evidences. Frequent common patterns exist in cancer PPI networks, which can be found through effective pattern mining algorithms. We believe that this work would allow us to identify functionally relevant and coherent subgraphs in cancer networks, which can be advanced to experimental validation to further our understanding of the complex biology of cancer.