Analysis of protein-protein interaction networks by means of annotated graph mining algorithms

This thesis discusses solutions to several open problems in Protein-Protein Interaction (PPI) networks with the aid of Knowledge Discovery. PPI networks are usually represented as undirected graphs, with nodes corresponding to proteins and edges representing interactions among protein pairs. A large amount of available PPI data and noise within it has made the knowledge discovery process a necessary central part for the network analysis. We define Knowledge Discovery as a process of extracting informative knowledge from the huge amount of data. Much success has been achieved when the input data is represented as a set of independent instances and their attributes. But, in the context of PPI networks, there is interesting knowledge to be mined from the relationships between instances (proteins). The resulting research area is called ``Graph Mining''. Here, the input data is modeled as a graph and the output could be any type of knowledge. In this thesis, we propose several graph mining algorithms to examine structural characteristics of PPI networks and link them to the information useful for biologists, such as function or disease.