Biological pathway completion using network motifs and random walks on graphs

Enhancing our understanding of cellular processes will ultimately lead to the development of better therapeutic strategies. Completing incomplete biological pathways through utilizing probabilistic protein-protein interaction (PPI) networks is one approach towards establishing knowledge about cellular mechanisms. The existing complex/pathway membership methods are focused on uncovering candidate protein members from probabilistic PPI networks. In our previous work, we defined the pathway completion problem and developed a method that utilizes network motifs to complete incomplete biological pathways. Network motifs allow us to take into consideration the intrinsic local structures of pathways and identify the possible points of insertion of candidate proteins. However, our previous approach requires a complete and correct PPI network. In this paper, we extend our approach and use random walks on graphs to address the pathway completion problem with incomplete PPI networks. We evaluated our proposed method using three yeast probabilistic PPI networks and two yeast pathways from KEGG (Kyoto Encyclopedia of Genes and Genomes). Moreover, we compared the accuracy of our network motifs approach for pathway completion to the existing approach for pathway membership, which also utilizes random walks. Our experiments show that our new approach achieves similar or better accuracy. In addition, our method identifies the possible locations and connections of the candidate proteins in the incomplete pathway, which allows for more efficient experimental verification.