Publications
Detailed Information
PS-MCL: parallel shotgun coarsened Markov clustering of protein interaction networks
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Lim, Yongsub | - |
dc.contributor.author | Yu, Injae | - |
dc.contributor.author | Seo, Dongmin | - |
dc.contributor.author | Kang, U | - |
dc.contributor.author | Sael, Lee | - |
dc.date.accessioned | 2019-09-23T23:39:46Z | - |
dc.date.available | 2019-09-24T08:42:21Z | - |
dc.date.issued | 2019-07-24 | - |
dc.identifier.citation | BMC Bioinformatics, 20(Suppl 13):381 | ko_KR |
dc.identifier.issn | 1471-2105 | - |
dc.identifier.uri | https://hdl.handle.net/10371/160875 | - |
dc.description.abstract | Background
How can we obtain fast and high-quality clusters in genome scale bio-networks? Graph clustering is a powerful tool applied on bio-networks to solve various biological problems such as protein complexes detection, disease module detection, and gene function prediction. Especially, MCL (Markov Clustering) has been spotlighted due to its superior performance on bio-networks. MCL, however, is skewed towards finding a large number of very small clusters (size 1-3) and fails to detect many larger clusters (size 10+). To resolve this fragmentation problem, MLR-MCL (Multi-level Regularized MCL) has been developed. MLR-MCL still suffers from the fragmentation and, in cases, unrealistically large clusters are generated. Results In this paper, we propose PS-MCL (Parallel Shotgun Coarsened MCL), a parallel graph clustering method outperforming MLR-MCL in terms of running time and cluster quality. PS-MCL adopts an efficient coarsening scheme, called SC (Shotgun Coarsening), to improve graph coarsening in MLR-MCL. SC allows merging multiple nodes at a time, which leads to improvement in quality, time and space usage. Also, PS-MCL parallelizes main operations used in MLR-MCL which includes matrix multiplication. Conclusions Experiments show that PS-MCL dramatically alleviates the fragmentation problem, and outperforms MLR-MCL in quality and running time. We also show that the running time of PS-MCL is effectively reduced with parallelization. | ko_KR |
dc.description.sponsorship | Publication of this article has been funded by National Research Foundation of Korea grant funded by the Korea government (NRF-2018R1A5A1060031, NRF-2018R1A1A3A0407953) and by Korea Institute of Science and Technology Information (K-18-L03-C02). | ko_KR |
dc.language.iso | en | ko_KR |
dc.publisher | BioMed Central | ko_KR |
dc.subject | Graph clustering | ko_KR |
dc.subject | Markov clustering | ko_KR |
dc.subject | Parallel clustering | ko_KR |
dc.subject | Coarsening | ko_KR |
dc.subject | Non-overlapping clusters | ko_KR |
dc.subject | Protein complex finding | ko_KR |
dc.title | PS-MCL: parallel shotgun coarsened Markov clustering of protein interaction networks | ko_KR |
dc.type | Article | ko_KR |
dc.contributor.AlternativeAuthor | 임용섭 | - |
dc.contributor.AlternativeAuthor | 유인재 | - |
dc.contributor.AlternativeAuthor | 서동민 | - |
dc.contributor.AlternativeAuthor | 강우 | - |
dc.contributor.AlternativeAuthor | 이사엘 | - |
dc.identifier.doi | 10.1186/s12859-019-2856-8 | - |
dc.language.rfc3066 | en | - |
dc.rights.holder | The Author(s) | - |
dc.date.updated | 2019-07-28T03:40:12Z | - |
- Appears in Collections:
- Files in This Item:
Item View & Download Count
Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.