Parallel Searching on Biological Networks
Authors:
- 1 February 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 307-314
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 manycore, 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 manycore 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.Keywords
This publication has 29 references indexed in Scilit:
- GRAPES: A Software for Parallel Searching on Biological Graphs Targeting Multi-Core ArchitecturesPLOS ONE, 2013
- A subgraph isomorphism algorithm and its application to biochemical dataBMC Bioinformatics, 2013
- The STRING database in 2011: functional interaction networks of proteins, globally integrated and scoredNucleic Acids Research, 2010
- AllDifferent-based filtering for subgraph isomorphismArtificial Intelligence, 2010
- SING: Subgraph search In Non-homogeneous GraphsBMC Bioinformatics, 2010
- Enhancing Graph Database Indexing by Suffix Tree Structure2010
- NetMatch: a Cytoscape plugin for searching biological networksBioinformatics, 2007
- 3D Complex: A Structural Classification of Protein ComplexesPLOS Computational Biology, 2006
- A (sub)graph isomorphism algorithm for matching large graphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Subgraph isomorphism detection in polynomial time on preprocessed model graphsLecture Notes in Computer Science, 1996