Discovering large conserved functional components in global network alignment by graph matching
Abstract Background Aligning protein-protein interaction (PPI) networks is very important to discover the functionally conserved sub-structures between different species. In recent years, the global PPI network alignment problem has been extensively studied aiming at finding the one-to-one alignment...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2018-09-01
|
| Series: | BMC Genomics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12864-018-5027-9 |
| _version_ | 1830443673287917568 |
|---|---|
| author | Yuanyuan Zhu Yuezhi Li Juan Liu Lu Qin Jeffrey Xu Yu |
| author_facet | Yuanyuan Zhu Yuezhi Li Juan Liu Lu Qin Jeffrey Xu Yu |
| author_sort | Yuanyuan Zhu |
| collection | DOAJ |
| description | Abstract Background Aligning protein-protein interaction (PPI) networks is very important to discover the functionally conserved sub-structures between different species. In recent years, the global PPI network alignment problem has been extensively studied aiming at finding the one-to-one alignment with the maximum matching score. However, finding large conserved components remains challenging due to its NP-hardness. Results We propose a new graph matching method GMAlign for global PPI network alignment. It first selects some pairs of important proteins as seeds, followed by a gradual expansion to obtain an initial matching, and then it refines the current result to obtain an optimal alignment result iteratively based on the vertex cover. We compare GMAlign with the state-of-the-art methods on the PPI network pairs obtained from the largest BioGRID dataset and validate its performance. The results show that our algorithm can produce larger size of alignment, and can find bigger and denser common connected subgraphs as well for the first time. Meanwhile, GMAlign can achieve high quality biological results, as measured by functional consistency and semantic similarity of the Gene Ontology terms. Moreover, we also show that GMAlign can achieve better results which are structurally and biologically meaningful in the detection of large conserved biological pathways between species. Conclusions GMAlign is a novel global network alignment tool to discover large conserved functional components between PPI networks. It also has many potential biological applications such as conserved pathway and protein complex discovery across species. The GMAlign software and datasets are avaialbile at https://github.com/yzlwhu/GMAlign. |
| first_indexed | 2024-12-21T06:01:33Z |
| format | Article |
| id | doaj.art-a49a5be9353145449a6a8cc3243bbc1d |
| institution | Directory Open Access Journal |
| issn | 1471-2164 |
| language | English |
| last_indexed | 2024-12-21T06:01:33Z |
| publishDate | 2018-09-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Genomics |
| spelling | doaj.art-a49a5be9353145449a6a8cc3243bbc1d2022-12-21T19:13:45ZengBMCBMC Genomics1471-21642018-09-0119S7415810.1186/s12864-018-5027-9Discovering large conserved functional components in global network alignment by graph matchingYuanyuan Zhu0Yuezhi Li1Juan Liu2Lu Qin3Jeffrey Xu Yu4School of Computer Science, Wuhan UniversitySchool of Computer Science, Wuhan UniversitySchool of Computer Science, Wuhan UniversityCentre of Quantum Computation and Intelligent Systems, University of TechnologyThe Chinese University of Hong KongAbstract Background Aligning protein-protein interaction (PPI) networks is very important to discover the functionally conserved sub-structures between different species. In recent years, the global PPI network alignment problem has been extensively studied aiming at finding the one-to-one alignment with the maximum matching score. However, finding large conserved components remains challenging due to its NP-hardness. Results We propose a new graph matching method GMAlign for global PPI network alignment. It first selects some pairs of important proteins as seeds, followed by a gradual expansion to obtain an initial matching, and then it refines the current result to obtain an optimal alignment result iteratively based on the vertex cover. We compare GMAlign with the state-of-the-art methods on the PPI network pairs obtained from the largest BioGRID dataset and validate its performance. The results show that our algorithm can produce larger size of alignment, and can find bigger and denser common connected subgraphs as well for the first time. Meanwhile, GMAlign can achieve high quality biological results, as measured by functional consistency and semantic similarity of the Gene Ontology terms. Moreover, we also show that GMAlign can achieve better results which are structurally and biologically meaningful in the detection of large conserved biological pathways between species. Conclusions GMAlign is a novel global network alignment tool to discover large conserved functional components between PPI networks. It also has many potential biological applications such as conserved pathway and protein complex discovery across species. The GMAlign software and datasets are avaialbile at https://github.com/yzlwhu/GMAlign.http://link.springer.com/article/10.1186/s12864-018-5027-9Protein-protein interaction networkGraph theoryGraph matching |
| spellingShingle | Yuanyuan Zhu Yuezhi Li Juan Liu Lu Qin Jeffrey Xu Yu Discovering large conserved functional components in global network alignment by graph matching BMC Genomics Protein-protein interaction network Graph theory Graph matching |
| title | Discovering large conserved functional components in global network alignment by graph matching |
| title_full | Discovering large conserved functional components in global network alignment by graph matching |
| title_fullStr | Discovering large conserved functional components in global network alignment by graph matching |
| title_full_unstemmed | Discovering large conserved functional components in global network alignment by graph matching |
| title_short | Discovering large conserved functional components in global network alignment by graph matching |
| title_sort | discovering large conserved functional components in global network alignment by graph matching |
| topic | Protein-protein interaction network Graph theory Graph matching |
| url | http://link.springer.com/article/10.1186/s12864-018-5027-9 |
| work_keys_str_mv | AT yuanyuanzhu discoveringlargeconservedfunctionalcomponentsinglobalnetworkalignmentbygraphmatching AT yuezhili discoveringlargeconservedfunctionalcomponentsinglobalnetworkalignmentbygraphmatching AT juanliu discoveringlargeconservedfunctionalcomponentsinglobalnetworkalignmentbygraphmatching AT luqin discoveringlargeconservedfunctionalcomponentsinglobalnetworkalignmentbygraphmatching AT jeffreyxuyu discoveringlargeconservedfunctionalcomponentsinglobalnetworkalignmentbygraphmatching |