| Understanding the nature of complex networks of protein-protein interactions (PPIs) is one of the most challenging tasks in modern computational biology. Because protein-protein interactions carry an important role in a large number of cellular functions, the topology of PPI networks shows structural patterns and regularities imposed by evolution. In order to understand the structure of PPI networks, and thus infer the nature of biological processes, it is necessary to develop models of PPI networks that would closely correspond to their real-world counterparts.;For the purposes of network analysis, PPI networks are presented as graphs, where each node corresponds to a unique protein and each edge corresponds to an interaction between two proteins. Random graph models have been used to model PPI networks and in this thesis, we propose a novel random graph model that takes into account evolutionary processes of gene duplication and mutation in an attempt to provide the best fit for PPI networks, while utilizing the basic concept of geometric graphs, which has been shown to be the best fitting model so far for eukariotic species.;In addition to network modeling, researchers need software tools in order to effectively perform different types of network analysis such as network comparison, alignment and clustering. While a large number of such software tools exists, researchers are limited by the number of models, methods and heuristics that existing software implements and furthermore restricted by the lack of automation which hinders practical applications for comprehensive network analysis. In this thesis, we introduce GraphCrunch 2 - a software tool to automate network model generation and analysis. It implements seven most popular random network models and compares them with the experimental data using commonly used network properties and more advanced, graphlet-based, heuristics. In addition, GraphCrunch 2 implements GRAphALigner (GRAAL) algorithm for purely topological network alignment, which can be applied to align any pair of networks, exposing regions of topological and functional similarities. Finally, GraphCrunch 2 implements k-medoids algorithm for clustering nodes in PPI network based solely on their topology. |
