CUFID-query: accurate network querying through random walk based network flow estimation
Abstract Background Functional modules in biological networks consist of numerous biomolecules and their complicated interactions. Recent studies have shown that biomolecules in a functional module tend to have similar interaction patterns and that such modules are often conserved across biological...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2017-12-01
|
| Series: | BMC Bioinformatics |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s12859-017-1899-y |
| _version_ | 1819080542358863872 |
|---|---|
| author | Hyundoo Jeong Xiaoning Qian Byung-Jun Yoon |
| author_facet | Hyundoo Jeong Xiaoning Qian Byung-Jun Yoon |
| author_sort | Hyundoo Jeong |
| collection | DOAJ |
| description | Abstract Background Functional modules in biological networks consist of numerous biomolecules and their complicated interactions. Recent studies have shown that biomolecules in a functional module tend to have similar interaction patterns and that such modules are often conserved across biological networks of different species. As a result, such conserved functional modules can be identified through comparative analysis of biological networks. Results In this work, we propose a novel network querying algorithm based on the CUFID (Comparative network analysis Using the steady-state network Flow to IDentify orthologous proteins) framework combined with an efficient seed-and-extension approach. The proposed algorithm, CUFID-query, can accurately detect conserved functional modules as small subnetworks in the target network that are expected to perform similar functions to the given query functional module. The CUFID framework was recently developed for probabilistic pairwise global comparison of biological networks, and it has been applied to pairwise global network alignment, where the framework was shown to yield accurate network alignment results. In the proposed CUFID-query algorithm, we adopt the CUFID framework and extend it for local network alignment, specifically to solve network querying problems. First, in the seed selection phase, the proposed method utilizes the CUFID framework to compare the query and the target networks and to predict the probabilistic node-to-node correspondence between the networks. Next, the algorithm selects and greedily extends the seed in the target network by iteratively adding nodes that have frequent interactions with other nodes in the seed network, in a way that the conductance of the extended network is maximally reduced. Finally, CUFID-query removes irrelevant nodes from the querying results based on the personalized PageRank vector for the induced network that includes the fully extended network and its neighboring nodes. Conclusions Through extensive performance evaluation based on biological networks with known functional modules, we show that CUFID-query outperforms the existing state-of-the-art algorithms in terms of prediction accuracy and biological significance of the predictions. |
| first_indexed | 2024-12-21T19:46:32Z |
| format | Article |
| id | doaj.art-a35f6016f6ba48e795ae80fbfe8db8be |
| institution | Directory Open Access Journal |
| issn | 1471-2105 |
| language | English |
| last_indexed | 2024-12-21T19:46:32Z |
| publishDate | 2017-12-01 |
| publisher | BMC |
| record_format | Article |
| series | BMC Bioinformatics |
| spelling | doaj.art-a35f6016f6ba48e795ae80fbfe8db8be2022-12-21T18:52:18ZengBMCBMC Bioinformatics1471-21052017-12-0118S1413314610.1186/s12859-017-1899-yCUFID-query: accurate network querying through random walk based network flow estimationHyundoo Jeong0Xiaoning Qian1Byung-Jun Yoon2Department of Electrical and Computer Engineering, Texas A&M UniversityDepartment of Electrical and Computer Engineering, Texas A&M UniversityDepartment of Electrical and Computer Engineering, Texas A&M UniversityAbstract Background Functional modules in biological networks consist of numerous biomolecules and their complicated interactions. Recent studies have shown that biomolecules in a functional module tend to have similar interaction patterns and that such modules are often conserved across biological networks of different species. As a result, such conserved functional modules can be identified through comparative analysis of biological networks. Results In this work, we propose a novel network querying algorithm based on the CUFID (Comparative network analysis Using the steady-state network Flow to IDentify orthologous proteins) framework combined with an efficient seed-and-extension approach. The proposed algorithm, CUFID-query, can accurately detect conserved functional modules as small subnetworks in the target network that are expected to perform similar functions to the given query functional module. The CUFID framework was recently developed for probabilistic pairwise global comparison of biological networks, and it has been applied to pairwise global network alignment, where the framework was shown to yield accurate network alignment results. In the proposed CUFID-query algorithm, we adopt the CUFID framework and extend it for local network alignment, specifically to solve network querying problems. First, in the seed selection phase, the proposed method utilizes the CUFID framework to compare the query and the target networks and to predict the probabilistic node-to-node correspondence between the networks. Next, the algorithm selects and greedily extends the seed in the target network by iteratively adding nodes that have frequent interactions with other nodes in the seed network, in a way that the conductance of the extended network is maximally reduced. Finally, CUFID-query removes irrelevant nodes from the querying results based on the personalized PageRank vector for the induced network that includes the fully extended network and its neighboring nodes. Conclusions Through extensive performance evaluation based on biological networks with known functional modules, we show that CUFID-query outperforms the existing state-of-the-art algorithms in terms of prediction accuracy and biological significance of the predictions.http://link.springer.com/article/10.1186/s12859-017-1899-yComparative network analysisNetwork queryingRandom walk |
| spellingShingle | Hyundoo Jeong Xiaoning Qian Byung-Jun Yoon CUFID-query: accurate network querying through random walk based network flow estimation BMC Bioinformatics Comparative network analysis Network querying Random walk |
| title | CUFID-query: accurate network querying through random walk based network flow estimation |
| title_full | CUFID-query: accurate network querying through random walk based network flow estimation |
| title_fullStr | CUFID-query: accurate network querying through random walk based network flow estimation |
| title_full_unstemmed | CUFID-query: accurate network querying through random walk based network flow estimation |
| title_short | CUFID-query: accurate network querying through random walk based network flow estimation |
| title_sort | cufid query accurate network querying through random walk based network flow estimation |
| topic | Comparative network analysis Network querying Random walk |
| url | http://link.springer.com/article/10.1186/s12859-017-1899-y |
| work_keys_str_mv | AT hyundoojeong cufidqueryaccuratenetworkqueryingthroughrandomwalkbasednetworkflowestimation AT xiaoningqian cufidqueryaccuratenetworkqueryingthroughrandomwalkbasednetworkflowestimation AT byungjunyoon cufidqueryaccuratenetworkqueryingthroughrandomwalkbasednetworkflowestimation |