Software applications for biological networks analysis rely on graphs to model the structure interactions. A great part of them requires searching for subgraphs in a target graph or in collections of graphs. Even though very efficient algorithms have been defined to solve such a subgraph isomorphisms problem, the complexity of current real biological networks make their sequential execution time prohibitive. On the other hand, parallel architectures, from multi-core to many-core, have become pervasive to deal with the problem of the data size. Nevertheless, the sequential nature of the graph searching algorithms makes their implementation for parallel architectures very challenging. This paper presents three different parallel solutions for the graph searching problem. The first two target the exact search for multi-core CPUs and many-core GPUs, respectively. The third one targets the approximate search for GPUs, which handles node, edge, and node label mismatches. The paper shows how different techniques have been developed in all the solutions to reduce the search space complexity. The paper shows the performance of the proposed solutions on representative biological networks containing antiviral chemical compounds and protein interactions networks.

Parallel Searching on Biological Networks / Bombieri, Nicola; Bonnici, Vincenzo; Giugno, Rosalba. - (2019), pp. 307-314. ((Intervento presentato al convegno Proceedings - 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, 2019 tenutosi a Pavia, Italy nel 13-15 February 2019 [10.1109/EMPDP.2019.8671572].

Parallel Searching on Biological Networks

Bonnici, Vincenzo;
2019

Abstract

Software applications for biological networks analysis rely on graphs to model the structure interactions. A great part of them requires searching for subgraphs in a target graph or in collections of graphs. Even though very efficient algorithms have been defined to solve such a subgraph isomorphisms problem, the complexity of current real biological networks make their sequential execution time prohibitive. On the other hand, parallel architectures, from multi-core to many-core, have become pervasive to deal with the problem of the data size. Nevertheless, the sequential nature of the graph searching algorithms makes their implementation for parallel architectures very challenging. This paper presents three different parallel solutions for the graph searching problem. The first two target the exact search for multi-core CPUs and many-core GPUs, respectively. The third one targets the approximate search for GPUs, which handles node, edge, and node label mismatches. The paper shows how different techniques have been developed in all the solutions to reduce the search space complexity. The paper shows the performance of the proposed solutions on representative biological networks containing antiviral chemical compounds and protein interactions networks.
978-1-7281-1644-0
Parallel Searching on Biological Networks / Bombieri, Nicola; Bonnici, Vincenzo; Giugno, Rosalba. - (2019), pp. 307-314. ((Intervento presentato al convegno Proceedings - 27th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, 2019 tenutosi a Pavia, Italy nel 13-15 February 2019 [10.1109/EMPDP.2019.8671572].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11381/2901543
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact