Pathway discovery in metabolic networks by subgraph extraction

Area of Science:

• Computational biology
• Bioinformatics
• Systems biology

Background:

• Subgraph extraction identifies biological pathways from networks using query items like genes or proteins.
• This technique applies to diverse data types including gene expression and phylogenetic profiles.
• The study focuses on adapting these methods for metabolic networks, noting their general applicability to other biological networks.

Purpose of the Study:

• To investigate and compare different subgraph extraction approaches for biological pathways.
• To identify the most effective strategy for extracting relevant pathways from metabolic networks.

Main Methods:

• Comparative evaluation of seven subgraph extraction algorithms.
• Utilized 71 known metabolic pathways from Saccharomyces cerevisiae and a MetaCyc metabolic network.
• Developed and tested a novel hybrid strategy combining random walk graph reduction and shortest paths algorithms.

Main Results:

• The novel hybrid strategy demonstrated superior performance compared to other methods.
• This hybrid approach achieved approximately 77% accuracy in recovering reference metabolic pathways.
• The network analysis tool set (NeAT) includes most evaluated algorithms, with kWalks available under GPL3.

Conclusions:

• The developed hybrid subgraph extraction method is highly effective for identifying metabolic pathways.
• This approach offers a significant improvement in pathway recovery accuracy.
• The generalizability of these methods allows for application across various biological network types.