1、Biological networks Construction and Analysis,Recap,Gene regulatory networks Transcription Factors: special proteins that function as “keys” to the “switches” that determine whether a protein is to be produced Gene regulatory networks try to show this “key-product” relationship and understand the re
2、gulatory mechanisms that govern the cell.We went over a simple algorithm for detecting significant patterns in these networks,Other networks?,Apart from regulation there are other events in a cell that require interaction of biological molecules Other types of molecular interactions that can be obse
3、rved in a cell enzyme ligand enzyme: a protein that catalyzes, or speeds up, a chemical reaction ligand: extracellular substance that binds to receptors metabolic pathways protein protein cell signaling pathways proteins interact physically and form large complexes for cell processes,Pathways are in
4、ter-linked,Signalling pathway,Genetic network,Metabolic pathway,STIMULUS,Interactions Pathways Network,A collection of interactions defines a network Pathways are subsets of networks All pathways are networks of interactions, however not all networks are pathways! Difference in the level of annotati
5、on or understanding We can define a pathway as a biological network that relates to a known physiological process or complete function,The “interactome”,The complete wiring of a proteome. Each vertex represents a protein. Each edge represents an “interaction” between two proteins.,An edge between tw
6、o proteins if.,The proteins interact physically and form large complexes The proteins are enzymes that catalyze two successive chemical reactions in a pathway One of the proteins regulates the expression of the other,Sources for interaction data,Literature: research labs have been conducting small-s
7、cale experiments for many years! Interaction dabases: MIPS (Munich Information center for Protein Sequences) BIND (Biomolecular Network Interaction Database) GRID (General Repository for Interaction Datasets) DIP (Database of Interacting Proteins) Experiments: Y2H (yeast two-hybrid method) APMS (aff
8、inity purification coupled with mass spectrometry),These methods provide the ability to perform genome/proteome-scale experiments. For yeast: 50,000 unique interactions involving 75% of known open reading frames (ORFs) of yeast genome However, for C. elegans they provide relatively small coverage of
9、 the genome with 5600 interactions. Problems with high-throughput experiments: Low quality, false positives, false negatives Fraction of biologically relevant interactions: 30%-50% (Deane et al. 2002),Solution:,User other indirect data sources to create a probabilistic protein network. Other sources
10、 include: Genome data: Existence of genes in multiple organisms Locations of the genes Bio-image data Gene Ontology annotations Microarray experiments Sub-cellular localization data,Probabilistic network approach,Each “interaction” link between two proteins has a posterior probability of existence,
11、based on the quality of supporting evidence.,Bayesian Network approach,Jansen et al. (2003) Science. Lee et al. (2004) Science. Combine individual probabilities of likelihood computed for each data source into a single likelihood (or probability) Naive Bayes: Assume independence of data sources Comb
12、ine likelihoods using simple multiplication,Bayesian Approach,A scalar score for a pair of genes is computed separately for each information source. Using gold positives (known interacting pairs) and gold negatives (known non-interacting pairs) interaction likelihoods for each information source is
13、computed. The product of likelihoods can be used to combine multiple information sources Assumption: A score from a source is independent from a score from another source.,Computing the likelihoods,Partition the pair scores of an information source into bins and provide likelihoods for score-ranges
14、E.g. Using the microarray information source and using Pearson correlation for scoring protein pairs you may get scores between -1 and 1. You want to know what is the likelihood of interaction for a protein pair that gets a Pearson correlation of 0.6.,Partitioning the scores,Computing the likelihood
15、,P(Interaction | Score) / P (Interaction)L = -P(Interaction | Score) / P (Interaction)Example,Protein interaction networks,Large scale (genome wide networks):,ProNet (Asthana et al.)Yeast3,112 nodes12,594 edges,Analyzing Protein Networks,Predict members of a partially known protein complex/pathway.
16、Infer individual genes functions on the basis of linked neighbors. Find strongly connected components, clusters to reveal unknown complexes. Find the best interaction path between a source and a target gene.,Simple analysis,The network can be thresholded to reveal clusters of interacting proteins,Co
17、mplex/Pathway membership problem,E.g., C. elegans cell death (apoptosis) pathway Identified 50 genes involved in the pathway. Are there other genes involved in the pathway? Biologists would like to know: Which genes (out of 15K genes) should be tested in the RNAi screens next?,Complex/pathway member
18、ship problem,Given a a set of proteins identified as the core complex (query), rank the remaining proteins in the network according to the probability that they “connect” to the core complex. This problem is very similar to the “network reliability” problem in communication networks.,Network reliabi
19、lity,Two terminal network reliability problem: Given a graph of connections between terminals: Each connection weighted by the probability that the corresponding wire is functioning at a given time What is the probability that some path of functioning wires connects two terminals at a given time?,Ex
20、act solution: NP-hard Several approximation methods exist,Monte Carlo simulation,Monte Carlo simulation (ProNet: Asthana et al. 2004) Create a sample of N binary networks from the probabilistic network (according to a Bernoulli trial on each edge based on its probability). Use breadth-first search t
21、o determine the existence of a path between the nodes (i.e., the two terminals). The fraction of sampled networks in which there exists a path between the two nodes is an approximation to the exact network reliability.,Parameters,Number of binary networks (samples) to be sampled from the probabilist
22、ic network 1000, 5000, 10000 ? The depth of the breadth-first search: complexity increases as you search for the existence of a path to a distant node. 4, 10, 20 ?,ProNet,Generate 10,000 binary networks from a probabilistic network (according to a Bernoulli trial on each edge based on its probabilit
23、y) Use breadth-first search to determine the existence of a path between two nodes Limit the maximum depth to 4 to reduce computation For each protein i in the network, count the fraction Ci of sampled networks in which there exists a path between i and the core complex. Report proteins ranked by Ci
24、,ProNet: example,Example,Complex nodes: p1 and p2,Example,Sample size: 4, maximum search depth: 3,Example,Sample size: 4, maximum search depth: 3,Cp12 = 0/4 = 0.0,Cp11 = 0/4 = 0.0,Cp10 = 0/4 = 0.0,Cp9 = 2/4 = 0.5,Cp8 = 2/4 = 0.5,Cp7 = 1/4 = 0.25,Cp6 = 0/4 = 0.0,Cp5 = 1/4 = 0.25,Cp4 = 1/4 = 0.25,Cp3
25、= 4/4 = 1.0,Results,Running time vs. sample size,What about accuracy of the technique? Is it able to give a good ranking for the nodes of the network, based on their closeness to the core?,Leave-one-out benchmark,Use known complexes to evaluate the accuracy of the method Leave one member (in turn) f
26、rom each complex/pathway. Use the rest of the complex/pathway as the starting, i.e., query, set. Examine the rank of the left-out protein. What do we expect from a good technique?,Accuracy vs. sample size,How does the sample size effect returned results?,Monte Carlo simulation,Disadvantages: What is
27、 the best choice for the number of samples? What should be the maximum depth for breadth-first search? (Need a cutoff to decrease running time) Scalability issues: May need a lot of computation time for large networks,Random Walks,Random Walks on graphs Googles page rank,Googles PageRank,Assumption:
28、 A link from page A to page B is a recommendation of page B by the author of A (we say B is successor of A) Quality of a page is related to its in-degreeRecursion: Quality of a page is related toits in-degree, and to the quality of pages linking to it PageRank BP 98,Definition of PageRank,Consider t
29、he following infinite random walk (surf): Initially the surfer is at a random page At each step, the surfer proceeds to a randomly chosen web page with probability d to a randomly chosen successor of the current page with probability 1-d The PageRank of a page p is the fraction of steps the surfer s
30、pends at p in the limit.,Random walks with restarts on interaction networks,Consider a random walker that starts on a source node, s. At every time tick, the walker chooses randomly among the available edges (based on edge weights), or goes back to node s with probability c.,s,0.2,0.4,0.4,0.1,0.3,0.
31、6,0.1,0.2,Random walks on graphs,The probability , is defined as the probability of finding the random walker at node v at time t. The steady state probability gives a measure of affinity to node s, and can be computed efficiently using iterative matrix operations.,Computing the steady state p vecto
32、r,Let s be the vector that represents the source nodes (i.e., si=1/n if node i is one the n source nodes, and 0 otherwise).Compute the following until p converges:p = (1-c)Ap + cswhere A is the column normalized adjacency matrix and c is the restart probability.,Same example,Start nodes: p1 and p2,R
33、andom walk results,Restart probability, c = 0.3,Experiments,Conducted complex/pathway membership queries on a probabilistic Yeast network: ConfidentNet (Lee et al., 4,681 nodes, 34,000 edges) Assembled a test set of 27 MIPS complexes and 10 KEGG pathways.,Leave-one-out benchmark,Leave one member (in
34、 turn) from each complex/pathway. Use the rest of the complex/pathway as the starting, i.e., query, set.Examine the rank of the left-out protein.,Leave-one-out on ConfidentNet,MIPS complex queries,Leave-one-out on ConfidentNet,KEGG pathway queries,Running time,Random Walks,Network Reliability by Monte Carlo Sampling,Total time to complete 121 MIPS complex queries,
