GRAPES-DD: exploiting decision diagrams for index-driven search in biological graph databases

Area of Science:

• Computational Biology
• Graph Theory
• Data Structures

Background:

• Graphs are crucial for representing biomedical and biological relationships.
• Subgraph searching in graphs is computationally intensive (NP-complete).
• Efficient indexing is key for fast subgraph searching in large datasets.

Purpose of the Study:

• To improve the efficiency of subgraph searching in biological graphs.
• To address the large index size issue of existing methods like GRAPES.
• To introduce a novel indexing strategy using Decision Diagrams.

Main Methods:

• Proposed GRAPES-DD, a modification of the GRAPES algorithm.
• Replaced the GRAPES indexing structure with Decision Diagrams.
• Evaluated GRAPES-DD on biomedical and synthetic graph datasets.

Main Results:

• GRAPES-DD substantially reduced memory utilization compared to GRAPES.
• Search time was not negatively impacted by the use of Decision Diagrams.
• Demonstrated effective subgraph searching with reduced index size.

Conclusions:

• Decision Diagrams offer a novel and promising approach for biological graph searching.
• Compactly encoding sets and manipulating them efficiently reduces computational load.
• GRAPES-DD makes indexing large biological graph collections more feasible.