Discovering large conserved functional components in global network alignment by graph matching

Zhu, Y; Li, Y; Liu, J; Qin, L; Yu, JX

Discovering large conserved functional components in global network alignment by graph matching

Zhu, Y Li, Y Liu, J Qin, L

Yu, JX

Permalink

Publisher:: BioMed Central
Publication Type:: Journal Article
Citation:: BMC Genomics, 2018, 19 (S7), pp. 41 - 102
Issue Date:: 2018-09

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published VersionAdobe PDF (3.08 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Zhu, Y	en_US
dc.contributor.author	Li, Y	en_US
dc.contributor.author	Liu, J	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.contributor.author	Yu, JX	en_US
dc.date.issued	2018-09	en_US
dc.identifier.citation	BMC Genomics, 2018, 19 (S7), pp. 41 - 102	en_US
dc.identifier.issn	1471-2164	en_US
dc.identifier.uri	http://hdl.handle.net/10453/131184
dc.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	en_US
dc.language	en	en_US
dc.publisher	BioMed Central	en_US
dc.relation.ispartof	BMC Genomics	en_US
dc.relation.isbasedon	10.1186/s12864-018-5027-9	en_US
dc.subject.classification	Bioinformatics	en_US
dc.title	Discovering large conserved functional components in global network alignment by graph matching	en_US
dc.type	Journal Article
utslib.citation.volume	S7	en_US
utslib.citation.volume	19	en_US
utslib.for	080301 Bioinformatics Software	en_US
utslib.for	06 Biological Sciences	en_US
utslib.for	08 Information and Computing Sciences	en_US
utslib.for	11 Medical and Health Sciences	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	open_access
pubs.consider-herdc	true	en_US
pubs.issue	S7	en_US
pubs.publication-status	Published	en_US
pubs.volume	19	en_US

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

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/131184