Algo for Scalable Biological Data Analysis

Lecture 20  Data Visualization o A picture is worth a thousand words o A critical part of being a successful bioinformatician o Should be done at all stages of the scientific process  Data exploration  Data analysis  Final presentation  What Not To Do o Do NOT be the researchers that uses Excel for plots o Do NOT abuse 3D o Do NOT waste empty space  Use the minimum amount of ink + space to convey the maximum amount of information possible o Do NOT put an overly simple plot  E.g. If it’s a straight line, instead of wasting it as a plot, just say “Perfect linear correlation” o Try to avoid using pie charts  Usually, the fact that they add up to 1 is not important and you’re just highlighting the relative magnitudes  Instead, just plot them as points side-by-side (or even bar graphs) o If you’re using a bar graph, see if plotting points connected by a curve would make more sense (i.e., save ink for the same information if it doesn’t make it less clear) o When showing ratios, always use log-scale  If the numerator is smaller than the denominator, you only have the range 0 to 1 to use for the ratio, but if the numerator is bigger than the denominator, it has the range from 1 to infinity to use for the ratio  In log-scale, if the numerator is smaller, you have negative infinity to 0, and if the numerator is larger, you have 0 to infinity, so equal real estate o Try to minimize the clutter on a plot o If you have a plot with multiple lines, instead of coloring them differently and having a legend on the side, if it doesn’t look too cluttered (i.e., the lines are far enough apart), just put each line’s label right next to the line o Do NOT exceed resolution of visual acuity  If you make the figure too small, you might have bars that are undiscernible to the reader o Show variation with statistics  Instead of having a plot specifically to highlight how much a value varies, just report the variance as a single statistic o Don’t necessarily show the full data  For example, showing an entire gene network might not be very useful: it’s super overwhelming  Instead, perhaps highlight the important parts and lighten the color of the rest  Perhaps don’t even show the unimportant stuff! o Help the viewer judge accuracies  It’s much easier to judge relative lengths (especially if adjacent) than areas  Back to the “try to avoid pie charts” point o Use perceptual palettes  Try to make sure color-blind people can read your figures  There exist color palettes online that are designed specifically for this o Luminance Effect: The eye can only discern between a small number of differences between colors

ECE | 286 | Algo for Scalable Biological Data Analysis | lecture notes | Lecture 20  Data Visualizatio

Lecture_14.docx-Lecture 14  Hypothesis Testing o

Lecture 12  Phylogenetic Inference (Review) o High-Level Problem :  Given: A sequence data matrix D at the leaves of an unknown tree  Compute: The tree(s) that would best explain the data o What do we mean by “explain”?  Maximum Likelihood (ML) : The log-likelihood according to a CTMC model of sequence evolution  Bayesian Methods : The log-likelihood according to a CTMC model plus our prior beliefs on phylogenetic trees and model parameters  Distance-Based Methods : Compatbility between pairwise leaf distances defined on a any given tree and distances computed from the matrix D  Distances computed from D are typically corrected based on a CTMC model  Maximum Parsimony : Requires fewest evolutionary events (e.g. substitutions) to explain all the data  This is the only approach that is not model-based  Maximum Parsimony o Problem : Given a set of aligned sequence data for n species, find:  1) An unrooted tree T leaf-labeled with n species  2) Sequence data for all internal nodes of T o We want to minimize S ( T ) = ∑ ( u,v ) ∈ E ( T ) H ( D u ,D v )  E ( T ) is the edge set of T  H is the hamming distance between two sequences  D u is the sequence data for node u o Given a tree T , what is its parsimony score (i.e., S ( T ) )?  Given internal nodes, this is trivial: just count the number of changes  Fitch’s Algorithm o We arbitrarily root the tree and process the characters (i.e., sites) one at a time  For each character, we traverse the tree twice: once post-order and then once pre-order o Define the following:  c x is the state of leaf x for the current character  A u is the set of optimal states at node u for a MP solution to the subtree rooted at u  s is the total score (starts at 0) o Stage 1 : Perform a post-order traversal (i.e., bottom-up)  For a leaf u :  Set A u = { c u }  If u is an internal node with children v and w : o If A u ∩A w = ∅ : Set A u = A v ∪ A w o Else: A u = A v ∩A w o Stage 2 : At the root r , pick an arbitrary state in A r to be the state at the root ( c r )  Perform a pre-order traversal (i.e., top-down)  For every node v with parent u : o If c u ∈ A v : Set c v = c u  In other words, inherit the parent’s state if possible o Else: Set c v to be an arbitrary element in A v and increment s o At the end, each internal node has a character state, and the parsimony score is s  Weighted Maximum Parsimony o Problem : Same as the normal parsimony, but uses a weighted Hamming distance  We are given the cost, W xy , for the substitutions between each pair of states  The distance is the sum of all the costs for all positions where the two sequences differ o Sankoff’s Algorithm (Dynamic Programming solution)  Let S u ( x ) denote the optimal cost of the subtree of T rooted at u , given that we assign the character of u to be x  For leaves:  If x = c x : S u ( x ) = 0  Else: S x ( x ) = ∞  For internal node u with children v and w :  S u ( x ) = min y { S v ( y ) + W xy } + min y { S w ( y ) + W xy } o Note that y ranges over the possible states (e.g. nucleotides)  Termination (at root r ): Minimum weighted parsimony score is min y { S r ( y ) }  Backtracking provides internal node states  Maximum Parsimony: The Motivation

ECE | 286 | Algo for Scalable Biological Data Analysis | lecture notes | Lecture 12  Phylogenetic Infe

Lecture 17  Censored Coalescence o Let’s consider a species tree branch with length τ generations (e.g. 10^5) and population size N e (e.g. 10^3 chromosomes) o The exponential rate of coalescence between any two alleles out of i is ( i 2 ) N e  Assume fixed mutation rate per generation μ (e.g. 10^-5)  Multiply species tree branch lengths by μ to get expected number of mutations  In this new unit of “time”, the rate of coalescence is ( i 2 ) μN e  Defining θ = 2 μN e , the rate of coalescence is 2 ( i 2 ) θ o Let T be a random variable for the time to the first coalescence for any two out of i lineages:  f T ( t ) = 2 ( i 2 ) θ e − 2 ( i 2 ) t θ o There are ( i 2 ) lineage pairs, but we are interested in a specific pair  Let X be the time to coalescence of a specific pair of lineages:  f X ( t ) = 2 θ e − 2 ( i 2 ) t θ o The lineage tree has u (e.g. 4) lineages at the bottom and v (e.g. 2) at the top  Going up, coalescences happen in delta times (in mutation units) t u ,…,t v + 1  The PDF of the lineage tree is:  ( ∏ i = v + 1 u 2 θ e − 2 ( i 2 ) t i θ ) e − 2 θ ( u 2 ) ( τ − ∑ i t i ) o Ignoring gene tree branch lengths, the following formula [Simon Tavaré, 1983] gives the probability of going form u lineages down to v lineages in time t  ∑ j = v u ( e − ( j 2 ) t ( 2 j − 1 )( − 1 ) j − v v! ( j − v ) ! ( v + j − 1 ) ∏ y = 0 j − 1 ( v + y )( u − v ) u + y )  Also need to consider the number of all topologies that go from u to v (see [Degnan and Salter, 2005])  MSC Gene Tree Probability o Compute the probability for each species tree branch independently an dmutiply them to get the gene tree probability o If only gene tree topologies are used, we need to sum over all possible embedding of the gene tree inside the species tree (we need to sum over all reconciliation)  Example: node u in the gene tree can move to the ancestor o The probability of each gene tree can be computed independently from others  Hierarchical Generative Model o The species tree defines a distribution on gene trees  Multi-Species Coalescent Model (gene evolution) o The gene trees define distributions on sequences  General Time Reversible Model (sequence evolution) o Given sequence data, can we estimate the species tree?  Concatenation : Concatenate the sequences of the genes, and estimate a tree on the resulting supersequences   Statistically inconsistent and can even be positively misleading when done using (unpartitioned) maximum likelihood  Mixed accuracy in simulations (sometimes works better than alternatives)  Summary Methods : Estimate gene trees on each gene tree independently, and then somehow “merge” the gene trees into a single species tree   Can be statistically consistent given true gene trees o (Probably) not consistent given estimated gene trees  Co-estimation : Estimate the gene trees and the species tree simultaneously  A couple of co-estimation methods exist (e.g. *BEAST and BEST)  All are Bayesian MCMC methods

ECE | 286 | Algo for Scalable Biological Data Analysis | lecture notes | Lecture 17  Censored Coalesce

Lecture_05.docx-Lecture 05  Using the Posterior

All courses in ECE

Popular Documents