Querying graphs in protein-protein interactions networks using feedback vertex set.

Area of Science:

• Bioinformatics
• Computational Biology
• Network Science

Background:

• Protein-protein interaction (PPI) networks are crucial for understanding biological processes.
• Interpreting large-scale PPI data requires efficient retrieval of known substructures.
• Algorithmic challenges, including NP-hard problems, hinder the analysis of complex graph patterns in PPI networks.

Purpose of the Study:

• To develop a novel, fixed-parameter tractable (FPT) algorithm for querying general graph patterns within PPI networks.
• To provide a practical alternative to existing methods that are limited to tree or path structures.
• To address the computational complexity of graph pattern matching in biological networks.

Main Methods:

• The study employs dynamic programming combined with the color-coding technique.
• A novel approach using feedback vertex sets and node duplication transforms graph queries into tree-like structures.
• The algorithm's complexity is parameterized by the size of the feedback vertex set of the query graph.

Main Results:

• The proposed algorithm is FPT for querying graphs with a bounded feedback vertex set size.
• It offers an alternative parameterization to treewidth for graph querying in PPI networks.
• A Python implementation successfully validated the algorithm's performance on real-world human PPI data, retrieving graph patterns efficiently.

Conclusions:

• The developed algorithm provides an effective and computationally tractable method for identifying complex graph structures in PPI networks.
• This approach expands the scope of queryable patterns beyond simple paths and trees.
• The practical implementation demonstrates the utility of feedback vertex set parameterization for biological network analysis.