Evolution of the yeast protein interaction networkHong Qin†, Henry H. S. Lu‡, Wei B. Wu§, and Wen-Hsiung Li†¶†Department of Ecology and Evolution, University of Chicago, 1101 East 57th Street, Chicago, IL 60637;‡Institute of Statistics, National Chiao TungUniversity, 1001 Ta Hsueh Road, Hsinchu, Taiwan 30050, Republic of China; and§Department of Statistics, University of Chicago, 5734 SouthUniversity Avenue, Chicago, IL 60637Contributed by Wen-Hsiung Li, August 29, 2003To study the evolution of the yeast protein interaction network,we first classified yeast proteins by their evolutionary histories intoisotemporal categories, then analyzed the interaction tendencieswithin and between the categories, and finally reconstructed themain growth path. We found that two proteins tend to interactwith each other if they are in the same or similar categories, buttended to avoid each other otherwise, and that network evolutionmirrors the universal tree of life. These observations suggestsynergistic selection during network evolution and provide in-sights into the hierarchical modularity of cellular networks.Biological networks are the basis of cellular functions (1, 2).Understanding network evolution may shed light on thehierarchical modularity, scale-free property, and various uses ofthe building blocks of biological networks (3–12). The yeastprotein interaction network is one of the best annotated complexnetworks to date (13–17). Previous studies on the evolution ofthis network focused either on gene duplication and molecularevolution at the protein level (9, 10) or on the global statisticalproperties (12). Neither approach can delineate the networkevolutionary path, and there is no other comparable proteininteraction data for the system-level comparison approach (5).Therefore, uncovering the growth patterns and the evolutionarypath of the protein interaction network is a serious challenge (3,4, 6, 7, 9, 12).Parts of the present yeast protein interaction network wouldhave been inherited from the last common ancestor of the threedomains of life: Eubacteria, Archaea, and Eukaryotes. Thus, ananalysis of the evolution of the yeast protein interaction networkmay provide new insights into the origin of eukaryotic cells(18–21), which has been a controversial issue.A key question in the evolution of biological complexity (6, 7,9, 12, 21, 22) is, how have integrated biological systems evolved?Darwinists (21, 23) proposed natural selection as the drivingforce of evolution. However, the striking similarities betweenbiological and nonbiological complexities have led to the argu-ment that a set of universal (or ahistorical) rules account for theformation of all complexities (22, 24, 25). The yeast proteininteraction network is an example of a complex biological systemand contributes to the complexity at the cellular level (26). Byanalyzing the growth pattern and reconstructing the evolution-ary path of the yeast protein interaction network, we can addresswhether or not network growth is contingent on evolutionaryhistory, which is the key disagreement between the Darwinianview and the universality view (22, 23, 27).In this article, we studied how the yeast protein interactionnetwork has evolved. We used graph theory to model the yeastprotein interaction network. Each yeast protein is a node in thegraph. Each pairwise interaction is a link between two nodes.Evolution of the yeast protein interaction network can then beinferred by analyzing the growth pattern of the graph. Weclassified all of the nodes (proteins) into isotemporal categoriesbased on each protein’s orthologous hits in several groups ofgenomes that are informative for yeast’s evolutionary history.This scheme gives each protein a binary (b) value representingits evolutionary history. Proteins from the same isotemporalcategory share similar evolutionary histories. We then analyzedthe interaction patterns within and between these isotemporalcategories. Finally, we inferred the main path of the networkevolution from six major isotemporal categories.Materials and MethodsData Collection. Genomic information of Saccharomyces cerevisiaewas downloaded from the Saccharomyces Genome Database(ftp:兾兾genome-ftp.stanford.edu兾pub兾yeast兾data㛭download) onAugust 13, 2002. Protein interaction data were obtained from theComprehensive Yeast Genome Database at the Munich Infor-mation Center for Protein Sequences (MIPS) (http:兾兾mips.gsf.de兾proj兾yeast兾CYGD兾db兾index.html) (28, 29) on May28, 2002, and from the reliable subsets of data from high-throughput screens (30). We excluded self-interactions and thoseinvolving mitochondrion proteins. The combined data set con-tains 6,633 interaction pairs. Orthologous analyses of the anno-tated ORFs in the yeast genome were parsed out from theclusters of orthologous groups (COGs) of proteins (ftp:兾兾ftp.ncbi.nih.gov兾pub兾COG) (31, 32) and the published ortholo-gous analysis from the Bork group at the European MolecularBiology Laboratory (EMBL) (30). Mitochondrion genes and afew inconsistent orthologous assignments were removed fromthe analysis.Data Analysis. Protein interaction networks were treated asundirected graphs in adjacency list format (33). Permutations ofthe networks were carried out in the Chiba City Linux cluster inthe Mathematics and Computer Science Division of ArgonneNational Laboratory (www.mcs.anl.gov兾chiba). Presentation ofthe network was performed by the programPAJEK (http:兾兾vlado.fmf.uni-lj.si兾pub兾networks兾pajek) (34). Distance matrix-based analyses were conducted in theR environment for statis-tical computing and graphics (www.r-project.org) (35). Theneighbor-joining (NJ) tree was generated byPAUP* (http:兾兾paup.csit.fsu.edu) and presented by the programTREEVIEW(http:兾兾taxonomy.zoology.gla.ac.uk兾rod兾treeview.html) (36).Statistical Analysis of Interaction and Traversal Patterns. To evaluatethe interaction tendencies within and between isotemporalcategories, we measured the deviation of each observed inter-action frequency from its random expectation (37). The ob-served interaction frequency between categories i and j, F(i,j)obs,iscompared with the mean interaction frequency, F(i,j)mean, of a seriesof null models in which all proteins have the same connectivities,but their interaction partners are randomly chosen (37) [termedthe Maslov–Sneppen 2002 (MS02) null models]. To describe thedeviations of the observed interaction