Applied Genomic Technologies

Biological Databases

Genomics Proteomics and Network Biology

Introduction to Bioinformatics Algorithms

Molecular Physical Chemistry

Molecular Sequence Analysis

Sys Biology and Bioengineering I Bio Cpnt

Lecture 06  More Clustering o Say we finished our clustering algorithm, but we can still end up with different clusters o We want “tight” clusters: we want all of the nodes of the same cluster to be close together o We want “separated” clusters: we want the different clusters to be far apart from one another  Computing the Optimal Clustering o Say we have Data Z = { z 1 ,z 2 ,…,z n } (where each element can be multidimensional) o Say we have Inference ∆ = { ∆ 1 ,∆ 2 ,…,∆ n }  ∆ i = { 1,2 ,…,K } o Say we have a Distance Function d ( z i ,X k ) o We can thus construct a Target Function:  min K,∆ f ( Z,∆,K )  f ( Z,∆,K ) = ∑ k = 1 K ∑ ∆ i = k d ( z i ,X k ) o However, this fails when k = n (since minimal sum of distances would be if we had each node in its own cluster, because each distance would be 0, so sum of distances is 0)  Thus, we probably want a penalty for how many clusters k we make  ChIP-Seq Technology o Chromatin Immunoprecipitation (ChIP) followed by sequencing o Transcription factor binds to DNA, and while it’s bound, somehow “fix” it to the DNA o Shear the DNA, and the parts bound by TF will be preserved o Extract the TFs using antibodies o Purify DNA and sequence, and you’ll see what parts were bound by the TFs  ChIP-Seq Data o Unlike TF ChIP-Seq results, which tend to be pretty targeted, Histone ChIP-Seq results typically span a wide range of the genome  Where do TFs Bind in the Genome? o Most TFs bind around the proximal promoter o Some, however, bind all over the place!  How is Specificity of TF Binding Achieved? o Consensus motif  Commonly found sequence  Shows which nucleotide is most abundant at each position  Example: YYANWYY o Used to computationally identify potential binding sites o Does not guarantee specificity o ChIP-Seq suggests some TFs don’t require a specific motif (E2F)

BENG | 183 | Applied Genomic Technologies | lecture notes | Lecture 06  More Clustering o

Lecture 15  Force Directed Graph Layout o Spring-like forces based on Hooke’s Law ( F =− kx ) attract connected nodes towards each other o Repulsive forces, as for charged particles based on Coulomb’s Law, separate all pairs of nodes o At equilibrium, edges tend to have uniform length (spring forces), and unconnected nodes tend to be further apart (repulsion) o Simulation is typically used, although the overall energy can also be explicitly minimized  Network-Based Prediction o Networks are filters and integrators in an input-output prediction paradigm o General Process  Start with input events (signal + noise)  Filter to reduce noise  Use integrator to increase effect size Δ  Use statistical test t  Relax t α (threshold) to maintain FDR o Example: Vazquez et al  Vazquez assigns a function σ v to each unannotated protein v so as to maximize the number of edges that connect proteins (unannotated or previously annotated) assigned with the same function  Precisely, maximize ∑ ( u,v ) ∈ E ' δ ( σ u ,σ v ) + ∑ v ∈ V h v ( σ v )  E ' is the set of edges incident on two unannotated proteins  δ is a function that equals 1 if the inputs functions are equal, and 0 otherwise  h v ( f ) denotes the number of neighbors of v previously annotated with function f  The first term concerns unannotated proteins  The second term accounts for interactions between unannotated and previously annotated proteins  Solved using simulated annealing  Network Propagation o Can identify subnetworks highlighted by data AND make network predictions o F t + 1 = αF t A + ( 1 − α ) F 0  α is the diffusion tuning parameter  F t is the current node scores  A is the network adjacency matrix o Identification of recurrently mutated networks (HotNet)  Network Alignment o E.g. species 1 vs. species 2, or condition 1 vs. condition 2 o Cross-Comparison of Networks  1) Conserved regions in the presence vs. absence of stimulus  2) Conserved regions across different species o S ( P ) = ∑ v ∈ P log 10 ( p ( v ) p random ) + ∑ e ∈ P log 10 ( q ( e ) q random )

BENG | 203 | Genomics Proteomics and Network Biology | lecture notes | Lecture 15  Force Directed Gr

Lecture_04.docx-Lecture 04  Brief Review of

Lecture 05  Machine Learning o The core of Machine Learning is making predictions or decisions from data o Impact: Machine Learning is arguably the greatest export from computing to other scientific fields o We can think of each “object” as a Training Image o We want to classify each Training Image as one of our Training Labels  To do this, we want to classify Image Features  We then have our machine undergo Classifier Training , by tying Image Features to Training Labels  At the end, we have a Trained Classifier o To test our Trained Classifier, we get a Test Image, pull Image Features, pass them to the Trained Classifier, and the Trained Classifier will form a Prediction Supervised Learning Unsupervised Learning Discrete Classification/Categorization Clustering Continuous Regression Dimensionality Reduction  Clustering o Before we can do the clustering stuff, we want to limit the genes we look at o If we look at all the samples, we can find the variation of gene expression levels for each gene, and ones with low variation (don’t change much between samples) can probably be cut  Hierarchal Clustering: Nearest Neighbor Algorithm o Use Euclidean distance to find the distances to closest neighbors o Take the two nodes with the closest distance and merge them o Number of nodes is reduced by 1. Repeat (take the two nodes with the closest distance and merge them) o How do we calculate the distance of one cluster to another, though?  We could define distance between two clusters as the distance between the two closest nodes (Simple Linkage )  We could define distance between two clusters as the distance between the two furthest nodes (Complete Linkage )  We could find the average point of each cluster and define distance as the distance between the two average points (UPGMA = Unweighted Pair Group Method with Arithmetic Mean) o We first have to define a Distance Function  Getting One Piece of Data from the Other o If I have the Centroids, I can label the points by simply finding the distance of each point and pick the closest ones o If I have the labels, I can calculate the Centroids by simply finding the average of all of the points with the same label  K -Means Clustering o 1) k initial “means” are randomly generated within the data domain o 2) k clusters are created by associating every observation with the nearest mean o 3) The centroid of each of the k clusters becomes the new mean o 4) Repeat steps 2 and 3 until convergence has been reached  We reach convergence when either the recalculated centroids stop changing or when label assignment of points stops changing

BENG | 183 | Applied Genomic Technologies | lecture notes | Lecture 05  Machine Learning 

Lecture 10  Gene Finding: The 1 st Generation o Given a genomic DNA, does it contain a gene (or not)? o Key Idea : The distributions of nucleotides is different in coding (translated exons) and non-coding regions o Therefore, a statistical test can be used to discriminate between coding and non- coding regions  Coding vs. Non-Coding o You are given a collection of exons, and a collection of intergenic sequence o Count the number of occurrences of ATGATG in Introns and Exons  Suppose 1% of the hexamers in Exons are ATGATG  Only 0.01% of the hexamers in Intergenic are ATGATG o How can you use this idea to find genes?  Generalizing o Compute a frequency count for all hexamers o Exons, Intergenic and the sequence X are all vectors in a multi-dimensional space o Use this to decide whether a sequence X is exonic or intergenic  Choosing Between Intergenic and Exonic o We can exploit geometry by “plotting” a point E (for exonic), a point I (for intergenic), and our point X (our query) o Normalize: V ' = V ‖ V ‖  V = { v 1 ,v 2 ,…,v n } is the original vector  ‖ V ‖ = √ v 1 2 + v 2 2 + … + v n 2 is the magnitude of the original vector (distance from the origin)  Thus, V ' = V ‖ V ‖ is the unit vector of V o Now, all vectors have the same length (lie on the unit circle, length = 1) o Next, compute the angle to E and the angle to I  Chose the feature that is “closer” (smaller angle)  In other words, Escore = α α + β  Coding Region Detection o The coding region can now be detected o Plot the coding score using a sliding window of fixed length  The (large) exons will show up reliably  Not enough to predict gene boundaries reliably o We can also use other signals for exon boundaries  Introns usually start with GT and usually end with AG  However, a GT should come up every ~16 bp (and same for AG), so not very specific  Other Signals o Signals at exon boundaries are precise, but not specific  Coding signals are specific, but not precise o When combined, they can be effective  Combining Signals o We can compute the following:  E-score(i,j)  I-score(i,j)  D-score(i) = score of i being a Donor Site  A-score(i) = score of i being an Acceptor Site  Goal is to find coordinates that maximize the total score o If we have a 2-exon gene where exon 1 goes [i1…i2] and exon 2 goes [i3…i4]  TotalScore = Escore ( i 1 ,i 2 ) + Iscore ( i 2 + 1 ,i 3 − 1 ) + Escore ( i 3 ,i 4 ) + Dscore ( i 2 + 1 ) + Ascore ( i 3 − 1 )  In other words, just sum up all the required scores o Define S E ( x ) as the best score of any parse (set of gene coordinates) that ends at position x in an exon (the exon starts at j )  S E ( x ) = max j < x { Escore ( j,x ) + Ascore ( j − 1 ) + S I ( j − 1 ) o Define S I ( x ) as the best score of any parse (set of gene coordinates) that ends at position x in an intron (the intron starts at j )  S I ( x ) = max j < x { Iscore ( j,x ) + Dscore ( j ) + S E ( j − 1 )  Hidden States and Gene Structure o Identifying a gene is equivalent to labeling each nucleotide as E/I/etc. o These “labels” are the hidden states o For simplicity, consider only two states E and I  Population Structure o 377 locations (loci) were sampled in 1000 people from 52 populations

All courses in BENG

Popular Documents