Biological NetworksCMSC 423 / BISCI 648aSuggested Reading•Paper Lists:•http://www.cs.umd.edu/class/fall2007/cmsc858l/•http://www.cs.umd.edu/class/fall2009/cmsc858l/papers.html•Reviews:1. Zhu, Gerstein, Snyder. Getting connected: analysis and principles of biological networks , Genes Dev 21:1010-1024, 2007.2. Shoemaker and Panchenko. Deciphering Protein-Protein Interactions. Part I. Experimental Techniques and Databases , PLoS Comp. Biol. 3(3):e42, 2007.3. Kelley, Sharan, Karp, Sittler, Root, Stockwell, Ideker. Conserved pathways within bacteria and yeast as revealed by global protein network alignment, Proc. Natl. Acad. Sci. USA 100:11394-11399, 2003.4. Sharan, Ulitsky, Shamir. Network-based prediction of protein function, Mol. Syst. Biol. 3, 2007.5. Milo, Shen-Orr, Itzkovitz, Kashtan, Chklovskii, Alon. Network motifs: simple building blocks of complex networks. Science 298:824-827, 2002.Types of Biological NetworksYeast transcription networkYeast Protein-Proteininteraction networkYeast Phosphorylation networkE. coli metabolic networkYeast SSL networkZhu et al, 2007.Transcription network, aka regulatory network:Transcription Factors = proteins that bind to DNA to activate or repress the nearby, downstream genes.generegulatesgenethe regulated gene might also be a transcription factorleads to a directed graphProtein-Protein interaction network:Proteins physically interactEdge {A,B}ABAssumption of binary interactions is imperfect.Sometimes several proteins must bind simultaneously for there to be any “interaction” (could be modeled as a hyperedge)Metabolic networkProteins are enzymes.They label the edges and their substrates are the nodes.Valine, Leucine, and Isoleucine biosynthesis (from KEGG)Yeast (aka Saccharomyces cerevisiae)interaction network (Two-hybrid)GRID (http://thebiogrid.org)8,742 edges3113 nodes (= proteins)(out of ~6,000 genes)ProteinExperimentalInteractionHuman interaction network (Two-hybrid)6,434 edges4,083 nodes (out of ~25,000 genes)“Why”&proteins&interact:AA→ BB→ CC→ DD→ EEBring chains of enzymes togetherABCSignal TransductionForm structuresABC“Tethered” Signal TransductionDFrom “Analysis of Biological Networks” Junker and Schreiber, edsHow do we extract biological insight from these graphs?1What role does each protein play in the cell?2How do we uncover the true graph from noisy samples?3How do we compare interaction graphs across species?4What are the characteristics of interaction graphs?Function Prediction1❖Proteins with known function + network topology → function assignment for unknown proteins.❖Guilt by association❖Simple: Majority Rule:???← Doesn’t take into account connections between neighborsOr annotations at distance > oneNeighboring Proteins More Likely to Share Function•(Yu et al., 2008)Predicting Missing Edges❖Completing Defective Cliques (Yu, et al, 2006):❖P, Q both adjacent to all nodes in clique (there are two (n-1)-cliques that overlap by (n-2) nodes) ⇒ likely that P,Q should be adjacent.2PQAligning Networks❖Let G1 = (V1, E1), G2, ... Gk be graphs, each giving noisy experimental estimations of interactions between proteins in organisms 1,.., k.❖If Gi = (Vi, Ei), we also have a function:that gives the sequence similarity between u and v.sim(u,v) : Vi × Vj → RG1G23(Kelley et al, 2003)PathBLAST:PathBLAST Alignment GraphNodes correspond to homologous pairs (A, a) where A is from one species, and a is from the other.•!Direct. A-B and a-b interactions are present.•!Gap. Edge A-B is present, and a & b are separated by 2 hops.•!Mismatch. Both (A & B) and (a & b) are both separated by 2 hops.Edges come in 3 types:(Kelley et al, 2003)PathBLAST Scoring FunctionS(P ) :=�v∈Plogp(v)prandom+�e∈Plogq(e)qrandomP is a path in the alignment graph.sum over logs = product over scoresprandom and qrandom are the average values of p(v) and q(e) in the graph.Pr[interaction]12≥ 30.10.30.9q(e)=�i∈ePr[i]q(e) = product of interaction edges “contained” within the alignment edgep(v) = Pr[Homology | Ev]p(v) = probability that proteins in v are really homologs.p(Ev | H) estimated from Ev distributions in COG:PathBLAST Search ProcedureS(v, L) = arg maxu∈pred(v)�S(u, L − 1) + logp(v)prandom+ logq(u → v)qrandom�If G is directed, acyclic (DAG) then its easy to find a high-scoring path via dynamic programming. S(v,L ) = max-scoring path of length L that ends at v:Because G is not directed, acyclic they randomly create a large number of DAGs by removing edges as follows:1. Randomly rank vertices.2. Direct edges from low to high rank.Run dynamic program on the random DAGs and take the highest scoring path. 2/L! chance that a path will be preserved.So repeat 5L! times.H. pylori & S. cerevisiae Find several (50) high-scoring pathsThen, remove those edges & vertices and repeat.Overlay the identified paths.Revealed 5 conserved pathways.(Kelley et al, 2003)Contains proteins from both: DNA polymerase and Proteosome => evidence that they interactH. pylori & S. cerevisiae Find several (50) high-scoring pathsThen, remove those edges & vertices and repeat.Overlay the identified paths.Revealed 5 conserved pathways.(Kelley et al, 2003)Contains proteins from both: DNA polymerase and Proteosome => evidence that they interactH. pylori & S. cerevisiae Find several (50) high-scoring pathsThen, remove those edges & vertices and repeat.Overlay the identified paths.Revealed 5 conserved pathways.(Kelley et al, 2003)Contains proteins from both: DNA polymerase and Proteosome => evidence that they interactSome Notes•Goal: use a well-studied organism (yeast) to learn about a less-studied organism (H. pylori).•There were only 7 directly shared edges between yeast & H. pylori. (you would expect 2.5 shared edges).-Gap & mismatch edges were essential!•Within conserved pathways, proteins often were not paired with the protein with the most similar sequence. -22% of the proteins in previous figure did not pair with their best sequence match•Single pathways in bacteria often correspond to multiple pathways in yeast. (Yeast is suspected of having undergone multiple whole-genome duplications.)Over-represented Network Motifs❖Are there connection patterns that occur frequently?❖“Frequently” = more often than you’d expect in a random graph with the same degree distribution.❖Milo et al, 2002 found the feed forward motif over-represented in gene regulation networks.❖Difficulty is larger motifs: subgraph