Modeling and alignment of biological networks

Many complex systems can be conveniently represented using networks. The most prominent examples are: biological networks, social, informational, physical and transportation networks. There are many different types of biological networks, but perhaps the most interesting of them are protein-protein interaction (PPI) networks. Proteins rarely function alone, instead they cooperate together to form complex networks of protein-protein interactions, which make our cells work. In PPI networks, nodes correspond to proteins and edges correspond to physical or functional interactions between them. Recent advancements in high-throughput experimental biotechnology for detecting protein interactions lead to the plethora of PPI network data, stimulating the development of computational techniques for biological network analyses.;Perhaps two of the most fundamental problems in biological network analyses are modeling and alignment. We introduce a novel model for PPI (and thus gene) network evolution that produces well-fitting network models for currently available PPI network data. The model integrates geometric graph properties with evolutionary dynamics of PPI network evolution. In geometric graphs nodes reside in some metric space and a pair of nodes corresponds to an edge if they are within some distance cutoff. The geometric graph framework is very rich and flexible, and we demonstrate how it can be used for analysis of a different type of a biological network---the brain functional networks. We demonstrate that for some types of cognitive tasks these networks exhibit geometric structure in addition to their "small-world" topology.;Since the discovery of DNA, sequence alignment has revolutionized our understanding of biology, evolution and disease. Network alignment is likely to have a similar impact. However, due to an underlying subgraph isomorphism problem, network alignment is computationally hard and therefore heuristic algorithms must be devised. We present two heuristic algorithms: GRAph ALigner (GRAAL) and Matching-based GRAph ALigner (M-GRAAL) which are currently the most efficient algorithms for network alignment. Both methods can use solely network topology and hence align any types of networks, not just biological ones. GRAAL algorithm is a seed-and-extend approach that uses solely topological cost-function to build the alignment. The unique feature of M-GRAAL algorithm is that to construct the alignment it can automatically process and integrate any number and type of similarity measures between nodes in the network, including, but not limited to, any topological network similarity measure, sequence similarity, functional similarity, and structural similarity. We use the alignments constructed by GRAAL and M-GRAAL to transfer knowledge from annotated to unannotated regions of networks in yeast, human and several bacterial species. Furthermore, with the help of GRAAL and M-GRAAL algorithms we demonstrate that solely topological network comparison can be used to reconstruct phylogenetic relationships between species.;We believe that our results demonstrate that high-quality topological alignments can yield new and pivotal insights into biological function and evolution. The importance of our work is that it gives researchers working in the field of complex network analysis two vital tools---well-fitting network models and algorithms capable of aligning huge and complex networks of any type.