CeFunMO: A centrality based method for discovering functional motifs with application in biological networks

被引：3
|
作者：
Kouhsar, Morteza [1 ]
Razaghi-Moghadam, Zahra [2 ]
Mousavian, Zaynab [1 ]
Masoudi-Nejad, Ali [1 ]
机构：
[1] Univ Tehran, Inst Biochem & Biophys, Lab Syst Biol & Bioinformat LBB, Tehran, Iran
[2] Univ Tehran, FNST, Tehran, Iran
来源：
COMPUTERS IN BIOLOGY AND MEDICINE | 2016年 / 76卷
关键词：
Biological network; Centrality; Functional motif; List-colored graph; Protein complex; TOOL;
D O I：
10.1016/j.compbiomed.2016.07.009
中图分类号：
Q [生物科学];
学科分类号：
07 ; 0710 ; 09 ;
摘要：
Detecting functional motifs in biological networks is one of the challenging problems in systems biology. Given a multiset of colors as query and a list-colored graph (an undirected graph with a set of colors assigned to each of its vertices), the problem is reduced to finding connected subgraphs, which best cover the multiset of query. To solve this NP-complete problem, we propose a new color-based centrality measure for list-colored graphs. Based on this newly-defined measure of centrality, a novel polynomial time algorithm is developed to discover functional motifs in list-colored graphs, using a greedy strategy. This algorithm, called CeFunMO, has superior running time and acceptable accuracy in comparison with other well-known algorithms, such as RANGI and GraMoFoNe. (C) 2016 Elsevier Ltd. All rights reserved.
引用
收藏
页码：154 / 159
页数：6
相关论文
共 10 条
  • [1] Application of Fractal Theory on Motifs Counting in Biological Networks
    Joveini, Mahdi Barat Zadeh
    Sadri, Javad
    IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2018, 15 (02) : 613 - 623
  • [2] The MSS of Complex Networks with Centrality Based Preference and Its Application to Biomolecular Networks
    Wu, Lin
    Tang, Lingkai
    Li, Min
    Wang, Jianxin
    Wu, Fang-Xiang
    2016 IEEE INTERNATIONAL CONFERENCE ON BIOINFORMATICS AND BIOMEDICINE (BIBM), 2016, : 229 - 234
  • [3] Application of dynamic expansion tree for finding large network motifs in biological networks
    Patra, Sabyasachi
    Mohapatra, Anjali
    PEERJ, 2019, 7
  • [4] Functional 5′ UTR motif discovery with LESMoN: Local Enrichment of Sequence Motifs in biological Networks
    Lavallee-Adam, Mathieu
    Cloutier, Philippe
    Coulombe, Benoit
    Blanchette, Mathieu
    NUCLEIC ACIDS RESEARCH, 2017, 45 (18) : 10415 - 10427
  • [5] A Centrality Estimation Method Based on Hidden Markov Model in Social Delay Tolerant Networks
    Huang, Yongfeng
    Dong, Yongqiang
    Zhang, Sanfeng
    Wu, Guoxin
    2013 22ND WIRELESS AND OPTICAL COMMUNICATIONS CONFERENCE (WOCC 2013), 2013, : 333 - 337
  • [6] Identification of Protein Complexes Based on Core-Attachment Structure and Combination of Centrality Measures and Biological Properties in PPI Weighted Networks
    Abdolkarim Elahi
    Seyed Morteza Babamir
    The Protein Journal, 2020, 39 : 681 - 702
  • [7] Identification of Protein Complexes Based on Core-Attachment Structure and Combination of Centrality Measures and Biological Properties in PPI Weighted Networks
    Elahi, Abdolkarim
    Babamir, Seyed Morteza
    PROTEIN JOURNAL, 2020, 39 (06) : 681 - 702
  • [8] Meta-path Based Prioritization of Functional Drug Actions with Multi-Level Biological Networks
    Yoon, Seyeol
    Lee, Doheon
    SCIENTIFIC REPORTS, 2019, 9 (1)
  • [9] GBNSS: A Method Based on Graph Neural Networks (GNNs) for Global Biological Network Similarity Search
    Wang, Yi
    Zhan, Feng
    Huang, Cuiyu
    Huang, Yiran
    APPLIED SCIENCES-BASEL, 2024, 14 (21):
  • [10] A seed expansion-based method to identify essential proteins by integrating protein-protein interaction sub-networks and multiple biological characteristics
    Zhao, He
    Liu, Guixia
    Cao, Xintian
    BMC BIOINFORMATICS, 2023, 24 (01)
1