Signal Path Extraction Based On Protein-protein Interaction Network

Signaling pathway is the way a group of proteins(Source node)and biochemical small molecules interact with each other to transduce signals from the signal receptor protein on the cell membrane generally to the proteins(Transcription factor,target)that bind to the DNAs in the nucleus to induce proper cellular response by activating and inhibiting a gene expression.Signaling pathways can be discovered by traversing protein-protein interaction network.Finding signaling pathways from protein-protein interaction network requires computationally intensive and time consuming network search.There have been several attempts to detect signaling pathways in protein-protein interaction network by applying various search methods such as depth first search,breadth first search and color coding method.In this paper,we propose a method to find the signaling pathway in a protein-protein interaction network.Our method considers the weights of points and reduces the network initially.Then we use the genetic algorithm(GA)or Simulated Annealing(SA)to extract the signaling pathways.First,take the source nodes as the center,perofrm greedy searching unil the target nodes are searched.Once a node in the protein-protein interaction network is searched,its weight is increased,and this weight is the node weight.Finally the nodes with lower node weights will be discarded.The nodes with higher node weights and the interaction between them will consititute a simpler network.Then source nodes and target nodes on this processed network will be grouped randomly,and a group of source nodes will be correspond to a group of target nodes.According to the group situations,GA or SA are used to determine the best group situation.After that,the network will be further simplified and we can extract the signaling pathway between the source nodes and the target nodes.Experiments show that our method can greatly reduce the scale of the protein-protein interaction network and simplify the network topology so that it can be calculated.We analyzed the performance on a protein-protein interaction network.