GRAPES: a software for parallel searching on biological graphs targeting multi-core architectures.

Area of Science:

• Bioinformatics
• Computational Biology
• Graph Theory Applications

Background:

• Biological data analysis, including genomics and ecology, frequently involves complex interaction networks represented as graphs.
• Searching for subgraphs within large graph databases is computationally intensive and crucial for understanding biological structures.
• Existing graph matching software is predominantly sequential, failing to leverage multicore architectures and hindering scalability with database size.

Purpose of the Study:

• To introduce GRAPES, a novel software solution for parallel subgraph searching in large biological graph databases.
• To enhance the efficiency and scalability of analyzing biological interaction data by exploiting parallel computing power.
• To address the limitations of sequential graph searching algorithms in handling large-scale biological datasets.

Main Methods:

• Implementation of parallel versions of established graph searching algorithms.
• Development of new parallelization strategies specifically designed for large graph datasets.
• Decomposition of large graphs into smaller, manageable subcomponents for efficient parallel searching.

Main Results:

• GRAPES demonstrates significantly faster parallel searching performance, particularly on large biological graphs.
• The software effectively utilizes multicore architectures, overcoming the scalability issues of sequential implementations.
• Performance was validated on diverse biological datasets, including chemical compounds, DNA, RNA, proteins, and interaction networks.

Conclusions:

• GRAPES provides a scalable and efficient solution for subgraph searching in large biological graph databases.
• The parallel approach significantly improves computational performance compared to traditional sequential methods.
• This advancement facilitates deeper analysis of complex biological interaction data across various domains.