A multi-objective method for discovery of pathways in protein-protein interaction networks

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. In the previous report [1], we solved the problem of finding pathways in the protein-protein interaction networks using genetic algorithms. Our proposed algorithm was also compared with the ones of other authors and proved to be better. However, our algorithm gave out only one goal, which was maximizing the weight function of the interactive network, while ignoring the number of standard pathways in the network. Through exper-iments, we have realized that weight functions with high value do not always give the high number of standard pathways. As a result, this report introduces multi-objective generic algorithms to deal with two targets at the same time: Maximizing the weight and function, as well as calculating the number of standard pathways in the interaction network. To extend the previous report, we first studied the mathematical model of the interaction network orientation problem with multi-objective characteristic. Based on such model, we designed a multi-objective genetic algorithm to find the solutions for the problem. Many experimental runs were carried out on the yeasts protein interaction network data set to find the best answer. Results from Multi-Objective Genetic Algorithm (MOGA), when compared with those of our previous proposed GA algorithms (SOGA - Single-Objective Genetic Algorithm), turn out to better solve the problem.