GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures.
Biological applications, from genomics to ecology, deal with graphs that represents the structure of interactions. Analyzing such data requires searching for subgraphs in collections of graphs. This task is computationally expensive. Even though multicore architectures, from commodity computers to m...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2013-01-01
|
| Series: | PLoS ONE |
| Online Access: | http://europepmc.org/articles/PMC3805575?pdf=render |
| _version_ | 1828372856542593024 |
|---|---|
| author | Rosalba Giugno Vincenzo Bonnici Nicola Bombieri Alfredo Pulvirenti Alfredo Ferro Dennis Shasha |
| author_facet | Rosalba Giugno Vincenzo Bonnici Nicola Bombieri Alfredo Pulvirenti Alfredo Ferro Dennis Shasha |
| author_sort | Rosalba Giugno |
| collection | DOAJ |
| description | Biological applications, from genomics to ecology, deal with graphs that represents the structure of interactions. Analyzing such data requires searching for subgraphs in collections of graphs. This task is computationally expensive. Even though multicore architectures, from commodity computers to more advanced symmetric multiprocessing (SMP), offer scalable computing power, currently published software implementations for indexing and graph matching are fundamentally sequential. As a consequence, such software implementations (i) do not fully exploit available parallel computing power and (ii) they do not scale with respect to the size of graphs in the database. We present GRAPES, software for parallel searching on databases of large biological graphs. GRAPES implements a parallel version of well-established graph searching algorithms, and introduces new strategies which naturally lead to a faster parallel searching system especially for large graphs. GRAPES decomposes graphs into subcomponents that can be efficiently searched in parallel. We show the performance of GRAPES on representative biological datasets containing antiviral chemical compounds, DNA, RNA, proteins, protein contact maps and protein interactions networks. |
| first_indexed | 2024-04-14T07:10:13Z |
| format | Article |
| id | doaj.art-39d283f8c29f44ac9124fc7f4e370070 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-04-14T07:10:13Z |
| publishDate | 2013-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-39d283f8c29f44ac9124fc7f4e3700702022-12-22T02:06:27ZengPublic Library of Science (PLoS)PLoS ONE1932-62032013-01-01810e7691110.1371/journal.pone.0076911GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures.Rosalba GiugnoVincenzo BonniciNicola BombieriAlfredo PulvirentiAlfredo FerroDennis ShashaBiological applications, from genomics to ecology, deal with graphs that represents the structure of interactions. Analyzing such data requires searching for subgraphs in collections of graphs. This task is computationally expensive. Even though multicore architectures, from commodity computers to more advanced symmetric multiprocessing (SMP), offer scalable computing power, currently published software implementations for indexing and graph matching are fundamentally sequential. As a consequence, such software implementations (i) do not fully exploit available parallel computing power and (ii) they do not scale with respect to the size of graphs in the database. We present GRAPES, software for parallel searching on databases of large biological graphs. GRAPES implements a parallel version of well-established graph searching algorithms, and introduces new strategies which naturally lead to a faster parallel searching system especially for large graphs. GRAPES decomposes graphs into subcomponents that can be efficiently searched in parallel. We show the performance of GRAPES on representative biological datasets containing antiviral chemical compounds, DNA, RNA, proteins, protein contact maps and protein interactions networks.http://europepmc.org/articles/PMC3805575?pdf=render |
| spellingShingle | Rosalba Giugno Vincenzo Bonnici Nicola Bombieri Alfredo Pulvirenti Alfredo Ferro Dennis Shasha GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures. PLoS ONE |
| title | GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures. |
| title_full | GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures. |
| title_fullStr | GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures. |
| title_full_unstemmed | GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures. |
| title_short | GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures. |
| title_sort | grapes a software for parallel searching on biological graphs targeting multi core architectures |
| url | http://europepmc.org/articles/PMC3805575?pdf=render |
| work_keys_str_mv | AT rosalbagiugno grapesasoftwareforparallelsearchingonbiologicalgraphstargetingmulticorearchitectures AT vincenzobonnici grapesasoftwareforparallelsearchingonbiologicalgraphstargetingmulticorearchitectures AT nicolabombieri grapesasoftwareforparallelsearchingonbiologicalgraphstargetingmulticorearchitectures AT alfredopulvirenti grapesasoftwareforparallelsearchingonbiologicalgraphstargetingmulticorearchitectures AT alfredoferro grapesasoftwareforparallelsearchingonbiologicalgraphstargetingmulticorearchitectures AT dennisshasha grapesasoftwareforparallelsearchingonbiologicalgraphstargetingmulticorearchitectures |