<p>Individual proteins, and small collections of proteins, have been extensively studied for at least two hundred years. Today, more than 350 genomes have been completely sequenced and the proteomes of these genomes have been at least partially mapped. The inventory of protein coding genes is the first step toward understanding the cellular machinery. Recent studies have generated a comprehensive data set for the physical interactions between the proteins of <i>Saccharomyces cerevisiae</i>, in addition to some less extensive proteome interaction maps of higher eukaryotes. Hence, it is now becoming feasible to investigate important questions regarding the evolution of protein-protein networks. For instance, what is the evolutionary relationship between proteins that interact, directly or indirectly? Do interacting proteins co-evolve? Are they often derived from each other? In order to perform such proteome-wide investigations, a top-down view is necessary. This is provided by network (or graph) theory.</p><p>The proteins of the cell may be viewed as a community of individual molecules which together form a society of proteins (nodes), a network, where the proteins have various kinds of relationships (edges) to each other. There are several different types of protein networks, for instance the two networks studied here, namely metabolic networks and protein-protein interaction networks. The metabolic network is a representation of metabolism, which is defined as the sum of the reactions that take place inside the cell. These reactions often occur through the catalytic activity of enzymes, representing the nodes, connected to each other through substrate/product edges. The indirect interactions of metabolic enzymes are clearly different in nature from the direct physical interactions, which are fundamental to most biological processes, which constitute the edges in protein-protein interaction networks.</p><p>This thesis describes three investigations into the evolution of metabolic and protein-protein interaction networks. We present a comparative study of the importance of retrograde evolution, the scenario that pathways assemble backward compared to the direction of the pathway, and patchwork evolution, where enzymes evolve from a broad to narrow substrate specificity. Shifting focus toward network topology, a suggested mechanism for the evolution of biological networks, preferential attachment, is investigated in the context of metabolism. Early in the investigation of biological networks it seemed clear that the networks often display a particular, 'scale-free', topology. This topology is characterized by many nodes with few interaction partners and a few nodes (hubs) with a large number of interaction partners. While the second paper describes the evidence for preferential attachment in metabolic networks, the final paper describes the characteristics of the hubs in the physical interaction network of <i>S. cerevisiae</i>.</p>

Individual proteins, and small collections of proteins, have been extensively studied for at least two hundred years. Today, more than 350 genomes have been completely sequenced and the proteomes of these genomes have been at least partially mapped. The inventory of protein coding genes is the first step toward understanding the cellular machinery. Recent studies have generated a comprehensive data set for the physical interactions between the proteins of Saccharomyces cerevisiae, in addition to some less extensive proteome interaction maps of higher eukaryotes. Hence, it is now becoming feasible to investigate important questions regarding the evolution of protein-protein networks. For instance, what is the evolutionary relationship between proteins that interact, directly or indirectly? Do interacting proteins co-evolve? Are they often derived from each other? In order to perform such proteome-wide investigations, a top-down view is necessary. This is provided by network (or graph) theory. The proteins of the cell may be viewed as a community of individual molecules which together form a society of proteins (nodes), a network, where the proteins have various kinds of relationships (edges) to each other. There are several different types of protein networks, for instance the two networks studied here, namely metabolic networks and protein-protein interaction networks. The metabolic network is a representation of metabolism, which is defined as the sum of the reactions that take place inside the cell. These reactions often occur through the catalytic activity of enzymes, representing the nodes, connected to each other through substrate/product edges. The indirect interactions of metabolic enzymes are clearly different in nature from the direct physical interactions, which are fundamental to most biological processes, which constitute the edges in protein-protein interaction networks. This thesis describes three investigations into the evolution of metabolic and protein-protein interaction networks. We present a comparative study of the importance of retrograde evolution, the scenario that pathways assemble backward compared to the direction of the pathway, and patchwork evolution, where enzymes evolve from a broad to narrow substrate specificity. Shifting focus toward network topology, a suggested mechanism for the evolution of biological networks, preferential attachment, is investigated in the context of metabolism. Early in the investigation of biological networks it seemed clear that the networks often display a particular, 'scale-free', topology. This topology is characterized by many nodes with few interaction partners and a few nodes (hubs) with a large number of interaction partners. While the second paper describes the evidence for preferential attachment in metabolic networks, the final paper describes the characteristics of the hubs in the physical interaction network of S. cerevisiae.