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

Advanced computational techniques of the current era help to identify proteins from the complex biological network that interact with each other and with the cell's environment. Biological pathways are a chain of molecular actions that leads to a new molecular product creation or alters the cellular state. These pathways are helpful in the predication of many real-world issues. Rebuilding these pathways is a challenging task due to the fact that protein interactions are undirected, whereas pathways are directed. To discover these pathways in protein-protein interaction data from specified source and target, it is essential to orient protein interactions. Unfortunately, the edge orientation problem is NP-hard, which makes it challenging to develop effective algorithms. This work rebuilds biologically important pathways in a weighted network of protein interactions of yeast species. The proposed algorithm, pseudo-guided multi-objective genetic algorithm (PGMOGA) rebuilds pathways by assigning orientation to the edges of the weighted network. Extending the past research, mathematical modeling of single-objective and multi-objective functions is performed. The PGMOGA is compared with four state-of-the-art approaches, namely, random orientation plus local search (ROLS), single-objective genetic algorithm (SOGA), multi-objective genetic algorithm (MOGA), and multi random search (MRS). The comparison is based on three general and four path specific metrics. Results show that the current proposal performs better.

Automated summary

The current era's advanced computational techniques assist in identifying proteins that interact within complex biological networks and with the cell's environment. Biological pathways, chains of molecular actions resulting in new molecular product creation or altered cellular state, are helpful in predicting real-world issues. Rebuilding these pathways is challenging due to undirected protein interactions and directed pathways, requiring orientation for protein interactions in specific source and target data. The proposed pseudo-guided multi-objective genetic algorithm (PGMOGA) improves pathway reconstruction in a weighted network of yeast species' protein interactions, outperforming four state-of-the-art approaches through edge orientation assignment.