LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules
Abstract Background Cross-species analysis of protein-protein interaction (PPI) networks provides an effective means of detecting conserved interaction patterns. Identifying such conserved substructures between PPI networks of different species increases our understanding of the principles deriving...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2019-12-01
|
| Series: | BMC Genomics |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s12864-019-6271-3 |
| _version_ | 1818666347832279040 |
|---|---|
| author | Sawal Maskey Young-Rae Cho |
| author_facet | Sawal Maskey Young-Rae Cho |
| author_sort | Sawal Maskey |
| collection | DOAJ |
| description | Abstract Background Cross-species analysis of protein-protein interaction (PPI) networks provides an effective means of detecting conserved interaction patterns. Identifying such conserved substructures between PPI networks of different species increases our understanding of the principles deriving evolution of cellular organizations and their functions in a system level. In recent years, network alignment techniques have been applied to genome-scale PPI networks to predict evolutionary conserved modules. Although a wide variety of network alignment algorithms have been introduced, developing a scalable local network alignment algorithm with high accuracy is still challenging. Results We present a novel pairwise local network alignment algorithm, called LePrimAlign, to predict conserved modules between PPI networks of three different species. The proposed algorithm exploits the results of a pairwise global alignment algorithm with many-to-many node mapping. It also applies the concept of graph entropy to detect initial cluster pairs from two networks. Finally, the initial clusters are expanded to increase the local alignment score that is formulated by a combination of intra-network and inter-network scores. The performance comparison with state-of-the-art approaches demonstrates that the proposed algorithm outperforms in terms of accuracy of identified protein complexes and quality of alignments. Conclusion The proposed method produces local network alignment of higher accuracy in predicting conserved modules even with large biological networks at a reduced computational cost. |
| first_indexed | 2024-12-17T06:03:06Z |
| format | Article |
| id | doaj.art-de1ebf14d4e8423eaea04af15bbc91cf |
| institution | Directory Open Access Journal |
| issn | 1471-2164 |
| language | English |
| last_indexed | 2024-12-17T06:03:06Z |
| publishDate | 2019-12-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Genomics |
| spelling | doaj.art-de1ebf14d4e8423eaea04af15bbc91cf2022-12-21T22:00:49ZengBMCBMC Genomics1471-21642019-12-0120S911210.1186/s12864-019-6271-3LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modulesSawal Maskey0Young-Rae Cho1Department of Computer Science, Baylor UniversityDepartment of Computer Science, Baylor UniversityAbstract Background Cross-species analysis of protein-protein interaction (PPI) networks provides an effective means of detecting conserved interaction patterns. Identifying such conserved substructures between PPI networks of different species increases our understanding of the principles deriving evolution of cellular organizations and their functions in a system level. In recent years, network alignment techniques have been applied to genome-scale PPI networks to predict evolutionary conserved modules. Although a wide variety of network alignment algorithms have been introduced, developing a scalable local network alignment algorithm with high accuracy is still challenging. Results We present a novel pairwise local network alignment algorithm, called LePrimAlign, to predict conserved modules between PPI networks of three different species. The proposed algorithm exploits the results of a pairwise global alignment algorithm with many-to-many node mapping. It also applies the concept of graph entropy to detect initial cluster pairs from two networks. Finally, the initial clusters are expanded to increase the local alignment score that is formulated by a combination of intra-network and inter-network scores. The performance comparison with state-of-the-art approaches demonstrates that the proposed algorithm outperforms in terms of accuracy of identified protein complexes and quality of alignments. Conclusion The proposed method produces local network alignment of higher accuracy in predicting conserved modules even with large biological networks at a reduced computational cost.https://doi.org/10.1186/s12864-019-6271-3Network alignmentLocal network alignmentPPI networksProtein-protein interactionsConserved modulesProtein complex prediction |
| spellingShingle | Sawal Maskey Young-Rae Cho LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules BMC Genomics Network alignment Local network alignment PPI networks Protein-protein interactions Conserved modules Protein complex prediction |
| title | LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules |
| title_full | LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules |
| title_fullStr | LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules |
| title_full_unstemmed | LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules |
| title_short | LePrimAlign: local entropy-based alignment of PPI networks to predict conserved modules |
| title_sort | leprimalign local entropy based alignment of ppi networks to predict conserved modules |
| topic | Network alignment Local network alignment PPI networks Protein-protein interactions Conserved modules Protein complex prediction |
| url | https://doi.org/10.1186/s12864-019-6271-3 |
| work_keys_str_mv | AT sawalmaskey leprimalignlocalentropybasedalignmentofppinetworkstopredictconservedmodules AT youngraecho leprimalignlocalentropybasedalignmentofppinetworkstopredictconservedmodules |