Institute of Information Science, Academia Sinica

Advances in biological high-throughput technology have led to an increased amount of available data on various biological interactions. Recently, these high-throughput approaches have enabled researchers to identify the role of each protein or gene. The central objective is generally to deduce how sub-systems and whole organisms work through exploring the interaction networks, in which a node is a protein or gene and an edge mimics an interaction. In this talk, I will introduce two algorithm we recently developed.

First, as the graph clusters in a PPI network can be considered as protein complexes or functional modules, we propose a functional modules identification algorithm based on Markov graph clustering algorithm (MCL). The challenge here is that protein complexes and functional modules may exhibit overlapping characteristics, while most traditional graph partitioning algorithms only produce non-overlapped clusters or clusters with very small overlaps.

Second, genes and proteins might form a linear signaling pathway. We propose the use of k shortest path algorithm to evaluate the importance of the relationship between nodes. We develop a single-source k shortest path algorithm while most k shortest algorithms focused on the single-pair problem. We moreover introduce diversity into k paths, resulting in more functionally consistent pathways.