Comparison of Networks Across Species CS374 Fall 06 Lecture 12, 10/26/06 Lecturer: Chuan Sheng Foo Scribe: Frank Chan 1 Comparison of Networks Across Species Based on the following papers: 1. Sharan R, Suthram S, Kelley RM, Kuhn T, McCuine S, Uetz P, Sittler T, Karp RM, Ideker T. Conserved patterns of protein interaction in multiple species. Proc Natl Acad Sci U S A. 2005 Feb 8;102(6):1974-9. 2. Flannick J, Novak A, Srinivasan BS, McAdams HH, Batzoglou S. Graemlin: general and robust alignment of multiple large interaction networks. Genome Res. 2006 Sep;16(9):1169-81. 1. Introduction Whole genome sequencing of diverse organisms has become widespread and sequence information has thus far outpaced our ability to annotate and characterize the vast number of new genetic networks. Obviously, genes do not exist in a vacuum and these information is only relevant insofar we understanding the interaction and pathways that these genes constitute. However, only a handful of organisms are experimentally tractable and it is generally agreed that drawing direct one-to-one functional inference between orthologs risks leaving out important biological nuances that may be key to the understanding of the species. Therefore, methods to compare networks across species promise to deliver insights beyond the raw genomic sequence of a given species. 2. Background Evolutionary conservation is an important concept that is fundamental to comparative genomics. This concept is based upon the idea that despite the great diversity observed between species, there is a shared, underlying body of developmental and regulatory logic. This reflects the biological constraints that requires keeping many aspects unchanged, generally both on the sequence level and the function level. It is generally accepted in biology, therefore, that sequence conservation implies functional conservation. By the same token, network conservation also implies functional conservation. Network comparisons allow us to identify conserved, functional modules. In cases where some information is available in another organism but not in the organism of interest, it allows query for a module in a way similar to what BLAST can do for sequence comparisons. Other relevant aspects of biology, such as the function or interactions between modules or proteins can also be predicted and or validated, when information is available in both systems. Although some of these analyses are not the sole domain of network comparisons, network comparisons brings improvement to protein function/interaction predictions and can handle comparisons that involve multiple protein interacting players that is not possible with existing techniques. Before we tackle other more technical aspects of network comparisons, it is important to define certain concepts. Common to most approaches, network comparisons are concerned with protein(-protein) interaction (PPI) networks. Just like any other networks, it is most intuitive to represent the properties as inter-connected nodes. For PPI, each protein is represented by nodes and protein-protein interactions are thereforeComparison of Networks Across Species CS374 Fall 06 Lecture 12, 10/26/06 Lecturer: Chuan Sheng Foo Scribe: Frank Chan 2 edges that connect the proteins. While the interpretation of the distance and quality of the interactions differ between different algorithms, both the length and the quality (e.g., width) of the edges can represent other aspects of the interaction between nodes. The goal of network comparison is, therefore, identify elements of networks that are similar between two species. If all the interactions of a given species are represented by one such PPI network graph, what network comparison algorithms attempt to do is to find conserved sub-graphs that are present, given all the graphs from each species for comparison. This “similarity” can be further broken into conservation based on protein sequence similarity (node similarity) and interaction similarity (network topology similarity). Algorithmically, a basic network comparison scheme must take available independently generated networks; apply alignment algorithm; and evaluate the network alignment with a scoring function. In addition, since all network comparisons are essentially pairwise comparisons, when attempting to align multiple networks, the algorithm must devise a method to either collapse the interactions between species into a single quantity; or progressively add networks into a generalized comparison. Implicit among all these network comparison algorithms is the objective to identify true positive interactions in the background of all logically possible interactions. Therefore, the scoring function in both algorithms discussed in the papers employ a comparison scheme between an algorithm-specific model that would ideally capture true biological interactions; and a random model that captures random interactions. Also, as potential network complexity (based on the number of possible interactions) increases exponentially with increasing number of nodes, all practical implementation of network comparison employs some form of heuristic solution to avoid the NP-complete problem.Comparison of Networks Across Species CS374 Fall 06 Lecture 12, 10/26/06 Lecturer: Chuan Sheng Foo Scribe: Frank Chan 3 3. Research presented on the papers Sharan et al. appeared in 2005 and summarizes the results obtained from aligning the PPI networks of C. elegans, D. melanogaster and S. cerevisiae. The general pipeline consists of identifying protein groups and the interactions; making an alignment based upon conserved interactions (edges); and then applying the scoring functions though searching the sub-networks for conserved paths and clusters. This pipeline is implemented in a package called NetworkBLAST. To enrich the dataset for real biological interactions, the authors assign a confidence value to each protein interaction using a logistic regression model based on: (i) the number of times an interaction between the proteins was experimentally observed; (ii) the Pearson correlation coefficient of expression measurements for the corresponding genes; and (iii) the proteins’ small world clustering coefficient. For the number of observations, the authors used the number of references for a given interaction for yeast, and data from a large-scale interaction study for both worm and fly. For
View Full Document
Unlocking...