A genetic-based approach for discovering pathways in protein-protein interaction networks

摘要

This paper introduces an approach of using the genetic algorithm for orienting protein-protein interaction networks (PPIs) and discovering pathways. Biological pathways such as metabolic or signaling ones play an important role in understanding cell activities and evolution. A cost-effective method to discover such pathways is analyzing accumulated information about protein-protein interactions, which are usually given in forms of undirected networks or graphs. Previous findings show that orienting protein interactions can improve pathway discovery. However, assigning orientation for protein interactions is a combinatorial optimization problem which has been proved to be NP-hard, making it critical to develop efficient algorithms. For our proposal, we first study the mathematical model of the problem. Then, based on this model, a genetic algorithm is designed to find the solution for the problem. We conducted multiple runs on the data of yeast PPI networks to test the best option for the problem. The preliminary results were compared with the results of the random search algorithm, which was shown to the best in dealing with this problem, in terms of the run time, fitness function values, especially the ratio of gold standard pathways. The findings show that our genetic-based approach addressed this problem better than the random search algorithm did.