Orienting Conflicted Graph Edges Using Genetic Algorithms to Discover Pathways in Protein-Protein Interaction...

Area of Science:

• Computational Biology
• Bioinformatics
• Systems Biology

Background:

• Biological pathways are crucial for understanding cellular functions and predicting real-world issues.
• Reconstructing these pathways is challenging due to the undirected nature of protein interactions versus directed pathways.
• The edge orientation problem in protein-protein interaction networks is NP-hard, hindering effective algorithm development.

Purpose of the Study:

• To develop an effective algorithm for rebuilding biologically important pathways in weighted protein-protein interaction networks.
• To address the challenge of orienting undirected protein interactions to represent directed biological pathways.
• To improve the accuracy and efficiency of pathway reconstruction in yeast species.

Main Methods:

• Proposed a pseudo-guided multi-objective genetic algorithm (PGMOGA) to assign orientation to edges in a weighted protein interaction network.
• Extended previous research by developing mathematical models for single-objective and multi-objective functions.
• Compared PGMOGA against four state-of-the-art approaches: ROLS, SOGA, MOGA, and MRS.

Main Results:

• The PGMOGA algorithm successfully rebuilt pathways by assigning orientation to network edges.
• Performance comparison, based on general and path-specific metrics, demonstrated the superiority of the proposed PGMOGA.
• Results indicate that the PGMOGA approach yields better pathway reconstruction outcomes compared to existing methods.

Conclusions:

• The PGMOGA is an effective computational technique for reconstructing biological pathways from protein-protein interaction data.
• This work contributes to overcoming the NP-hard edge orientation problem in bioinformatics.
• The findings suggest PGMOGA as a promising tool for analyzing complex biological networks and advancing systems biology research.