Text By the Bay 2015: Frank Nothaft, Scalable Genome Analysis With ADAM

Text By the Bay 2015: Frank Nothaft, Scalable Genome Analysis With ADAM

Recording: Text By the Bay 2015: Frank Nothaft, Scalable Genome Analysis With ADAM

all right well uh thank you all for coming out today and uh thank you John for the great introduction to this topic uh so you know I'll build a bit on what John was talking about in kind of the context of how we you know how we algorithmically work on some of these sequence analysis and sequence interpretation questions uh you know so I think I think John really motivated this this whole question you know what what are we doing when we're analyzing genomic data what's our goal and uh you know a a big metaphor that really works great when you're speaking to an audience that's a programming audience is that your genome is the source code for Life uh you know in the human genome you know humans are what we call diploids so you have 23 chromosomes you know 22 are autosomal chromosomes and then you have you know one chromosome from each parent that's a sex chromosome and you have two copies of each of these so you know diploid means that you have two of each chromosome uh you know in this this Human Genome it's this 3.2 character uh 3.2 billion character file or program that split across these 46 files and these files are uh you know the recipes that encode what proteins you manufacture as well as how you regulate these proteins and uh you know we we talk about this this five you know this program being 3.2 billion characters long you know between each one of us the vast majority of this code is the same you know it's it's kind of like if I went ahead and I made a fork of the Linux driver and I you know I modified the file buffer you know my file buffer might be different than your file buffer but overall we're still running the same you know same operating system so you know actually if you look at each one of us in this room our genomes are are the are the same at about 99.9% of locations this small you know one10 of 1% variance is what drives you know not just the rise of diverse traits like you know what's my eye color my hair color how tall am I but ultimately this is what you know drives what diseases I'm susceptible to especially when you look at hereditary diseases you know things like you know cancer which a lot of you know a lot of the risk factors are hereditary or you know if you look at things like Alzheimer's autism many of these disorders that we're finding out have very strong genetic links and ultimately the way that we've been studying this is that we go ahead we you know we take this genome this long string of text and we go ahead as John described earlier we shred it up we take this 3.2 billion bases we copy it a bunch of times you know we copy it some replication Factor we wind up calling our you know our coverage and then we go ahead and we run the shredding process that's really it's a Pon substring sampling process so you know there's actually a bu bunch of folks who've gone ahead and come up with information theoretical models for you know how we're getting these substrings it actually turns out most sequencers you know they really just have a Pon distribution in which they draw these all these different substrings from and you know right now if I have $1,000 I can uh you know I can send your uh you know I can extract your genomic data I can send it to a lab and they can sequence 30X copy you know 30X coverage of your genome uh you know this depending on where you send it to you know might take up to two weeks get this back I can you know in a matter of days to you know a week go ahead and turn this you know I can reassemble your genome from this you know big bag of Pon subsamples and what's what's really enabled this is a rise of this uh this procedure we call genome resequencing so I bet that most of the people in this room are familiar you know have at least heard of the human genome project uh you know so the Human Genome Project ran for several years in the late 1990s you know and finished in about 2001 and what they did was they took 20 different humans they put all their sequences together and you know over the course of couple of years and using a billion dollars they came out with a draft of what the average human genome looks like once we've got this you know and a lot of people will argue whether this is a you know whether you can really come up with an average human genome you know those one those little you know 0.1% variants actually cause a bunch of artifacts and this average sequence that don't actually appear in any single individual but you know this average sequence is pretty accurate for many of the places that we care about you know a lot of the genes that you know for example efgr which we know is important in many cancers or you know bricka one and two which are very important in breast cancer a lot of these places we come out with very good average sequences for so now that we have this average what makes this process cheaper you know what drops this 1 billion down to $1,000 is that we don't have to recreate your entire genome every single time what we do now is we we try to figure out how you're different from the average genome you know we we care really strongly about these this 0.1% variation so all that we have to do is use your reads compare them to this Human Genome and figure out where you're you know where you're different uh but ultimately this this leaves us with two new problems so first we have to figure out you know what are what are ways that we can compute this difference with good Fidelity you know there you know I can just throw a bunch of these reads together you know I can just take this bag and you know try to flatten it out but that's not necessarily going to give me good information about how you're different it's just going to tell me you know you know maybe you don't have the same exact word distribution you know maybe you know actg you know let's say actg is a you know genomic substitute for worse you know maybe that showed up you know 100,000 times in the average genome and it only shows up 999,000 times in your genome how are those different you know that doesn't necessarily tell me useful information so the process of computing this diff is important and then finally once we've gone ahead and we've you know figured out how you're different we need to make sense of the differences and in some cases you know for example the mutation John was talking about we've sequenced a bunch of patients you know we've been able to say Hey you know this variant if I delete 10 bases from efgr that breaks the efgr gene efgr is you know implicit in this regulatory Cascade if I've broken that Gene that Cascade doesn't work anymore and Tada you get cancer but in many cases these differences are much more subtle so we we need to find some way that we can make sense so you know the way that you know I'll kind of walk you through this going from how we compute the diff to how we make sense of the diff and the common approach that people use right now is a alignment assembly approach so you know what we do is we take these these subsampled you know these substrings and we figure out what's the best place in our original reference that the string could have come from and this is a uh you know this is a problem that actually builds very heavily off of a lot of search and retrieval techniques that you know come originally from the database and the NLP communities you know some of the common techniques that people use if they're you know trying to align strings to you know this reference genome is they'll go ahead and they'll compute a you know just a substring index of this genome you know using a bunch of things people use FM indexes people use suffix trees people use Burrows wheelo transforms to compute an efficient index that allows them to map these substrings back to the reference genome another approach that you can do is uh actually an approach that's uh very similar to the document similarity approach so you know there's a really cool paper that came out just in the last year that realized hey you know this problem is very exactly a document similarity approach so you know they wound up using a you know jard similarity approximation you know they they used a minhing algorithm you know which some of you may be familiar with uh you know used in document D duplication all the time and they use that to figure out okay you know what's the similarities between two different reads and if I can find the similarities between two different reads I can connect those two reads together so this is the you this is kind of the first stage that we go through and do and then the second stage is this assembly pH you know this assembly stage and so the you know essentially what we're trying to do you know we've gone ahead we've taken this bag we've aligned it to the genome so that's given us you know kind of a sequence of locations where we have some observation at that location and then we have to flatten this back into a consensus string uh and you know in this case this looks very simple you know all of these all of these subsequences agree right you know however in your you know in your genome right we were saying humans are diploid organisms I don't have one copy of the string I have two and some places you know if I have a copy number variant I might have three copies or I'll only have one so what we have to do is you know let's say that we had you know two sub samples that say yes you know I saw the best of you know right here and then we have two other you know two other subsamples two other reads that say oh you know I just saw the of so I I deleted best so there's a few you know few things you know one is you know we could have the best of on both you know both of your chromosomes we could have the best or you know the of on both of your chromosomes or we could have the best of and the of you know each on one copy so this the sequence assembly process you know makes use of a variety of techniques you know drawing some from graph Theory and some from uh you know statistics and probability to go ahead and come up with the two best consensus sequences that describe your genome and uh you know ultimately kind of how this all integrates is in this you know this framework that a lot of people are calling data intensive genomics so you know while in some places we have very clear links between a mutation and a disease in many places we actually have you know rare mutations that you know they show up in a very small percentage of the population and you know we we can tell that these people you know they wind up a disease you know maybe they wind up getting a leukemia or some other sort of cancer but it's not necessarily straightforward to pinpoint pinpoint what exactly the cause of this was so you know part of this is you know the cost of sequencing has fallen you know 10,000 times in the last 15 years so that makes it very cheap to collect large data sets and since we know that we have statistical linkages between these variants and the diseases they cause what we want to do is you know look at these very large large populations go ahead sequence many of these people understand what you know what phenotypes they have so you know what traits they have what diseases they're susceptible to and then draw out these links draw out these low frequency links that you know wind up being trait causal or disease causal and you know part of the problem that we run across is you know this is a very big data challenge you know we uh you know we talk a lot about big data in science um but you know just to kind of give you an example of how much data we're actually going to go ahead and collect there's a project in the UK that's launching right now uh it's you know the genomics England 100K for UK project so they're going to go ahead and sequence you I think they're sequencing about 40,000 healthy people and then 60,000 people who have you know some different sort of disease whether it's a heart disease or they have a cancer they've broken this out into a bunch of different disease cohorts they're going to go ahead and they're going to sequence their genome so wgs stands for whole genome sequencing so you know we're sequencing all of the 3.2 billion bases not just the ones that code for something and each one of these you know whole genome sequencing runs generates somewhere between 100 and 200 gigabytes of data per person so you know now we look you know 100 gigabyte 100 to 200 gigabyt per person 100,000 people we're looking somewhere in the range of 10 to 20 pedabytes of data and even when we go ahead and just extract these 0.1% you know these 0.1% variations we wind up with about 300 terabytes of variant information so this is a very big data processing challenge so the approach that we've taken is to build this uh this system called atom which is a open- source distributed framework for processing genomic data so we build our tools on top of a bunch of you know commodity open source tools uh you know so we've actually gone ahead and we built our data schema on top of apachi Avro which you know for those of you who are you know familiar with the Hadoop ecosystem you probably heard of or maybe even used Apachi Avro before we store all our data in paret and then uh you know we've gone ahead and defined a a set of distributed programming apis that map very well to Common genomics tasks using uh you know spark and Scala so you know it it turns out that a lot of the genomic algorithms uh they wind up mapping down to you're running some statistical algorithm that's anchored to some location in the genome you know we talked about this reference genome most of the time we have you know something either we're we're trying to identify what the expression you know how many copies do we have of something at a position in the genome so this is something we would do if we're looking at expression or we're looking at copy number you might be looking do we have you know Peaks you know do we have some of that happens at a place in the in the genome which we look for trying to detect how proteins interact with the genome and then you finally when we have these these variants that we're trying to detect you know they're very well anchored to positions in the genome so a lot of these can actually be expressed through a set of common join patterns so we've built uh you know essentially a a high performance join engine with a bunch of uh you know straightforward Primitives on top of that allow us to express these genomic algorithms in a data parallel distributed scalable manner so really the the big thing that we're trying to attack is this problem of integrating across these very large terabyte to petabyte data sets to find these low frequency linkages and we've gone ahead and we've started to build an ecosystem around you know around this tool so you know atom's kind of a core of the API so you know it's it provides useful Primitives but in and of itself it doesn't you know doesn't do interesting meaningful science so you know I'll talk a little bit about two tools today so avocado is the tool that actually goes ahead and you know mins and extracts these variants and then I'll give a little bit of uh you know of an introduction to a new tool that we started working on um that goes ahead and tries to identify what this variant modifies and uh you know what you know what we're really trying to do is solve kind of these two challenges in variant detection and variant analysis so you know there's there's this process that we were talking about this reassembly process that goes ahead and takes the aligned reads and compresses them down to a you know a single consensus sequence and uh a lot of the approaches that people are using to do this right now are very expensive you know they use these statistical SLG graph theoretic approaches that wind up having really bad runtime complexity uh you know so one of our goals is to come up with more efficient ways of implementing these algorithms on the other side we want to you know we want to work on statistical models that allow us to draw out you know these low frequency correlations you know for example if I see if I see a populate you know if I see a variant and my evidence for it isn't great you know it's probabilistically it's it's borderline but I see hey you know this person you know has a certain phenotype like they have a breast cancer or this person is from a certain ethnic group for for example you know they're from a you know a population like let's say you know they're from a Scandinavian population or you know some population that's from a very geographically isolated area we might say well you know this variance Is On The Border but what's the Frequency that this variant shows up in the group that we know this person is similar to and if that variant shows up with high frequency in that in that group then that'll give us you know evidence to push it over the edge from being you know border line to being a variant that we can confidently say they probably have yes so you are in fact talking about uh confidence in variant detection not confidence in variant correlation to a disease correct yeah we're talking about confidence in variant detection so it's kind of the you the joint variant calling problem if you're familiar with that sure uh I guess it might be helpful if you could say a sense or two about why it's called in a particular sample to determine whether especially with you know 10 or 20 or 30X coverage uh to determine whether a variant uh actually is present what's what's the barrier sure sure great thanks uh that's a very good question so part of this uh you know and I'll get to this on the next slide so maybe let's hold off until the next slide um you I'll talk about that a little bit more um but you know this does lead into that the second question is finally coming down to this variant analysis side so you know one thing is that we do want to detect these statistical linkages between a variant and a trait you know whether that's or a variant in a phenotype whether that's a trait you know hair color or if it's something you know like a disease status or a disease risk factor but what complicates this is that variants don't always have straightforward explanations and we'll talk about this a little bit later uh but you know I think an analogy that works really well especially kind of in the text processing and language community is you know if we talk about a you know we talk about a variant that occurs in your exome a variant that modifies the product of a gene and there we actually have a fairly good grammar for describing what a variant does you know for example if I have a variant you know maybe I have an A to a c variant that's in a section of your your section that codes for an amino acid this a to c might change it from one you know one amino acid to another amino acid if it changes that you know that's going to change how the protein itself Works however if we're in a section of the genome where you know this variant doesn't change what the amino acid is how can we tell what it's doing you know do we go ahead and say well we don't know what it does so we can just throw it away can we come up with a better hypothesis you know can we hypothesize a grammar for you know the areas outside of the exome so I'll talk about that a bit more towards the end so you know the variant detection problem so you know we were just saying why do we want to integrate why do we want to figure out these backline Pro or these uh Baseline probabilities for whether someone has a variant based on their membership in a group uh you ultimately this is because the sequencing process itself is noisy uh you know so we've we've just presented that we have this Pon you know this Pon uh you know subsequence sampling process but we haven't talked about the characteristics of these reads other than that they're Pon distributed uh you know one of the things that's kind of crazy is that these sequencing you know these sequencing machines are uh you know by many standards for data quality not very good you know they have a 2% error rate which you know think about it if you had a 2% packet error rate in your network you'd be going insane you know you you couldn't get you know you could you could barely even connect you know say to your your wireless router if you're you know your wireless link had a 2% error rate but our sequencers you know they have a 2% error rate so one of the things that makes this even worse is it's not just a 2% error rate overall but these errors tend to be correlated so one of the um you know one of the error form you that's very common and uh you'll see this show up in papers is that they'll have an entire you know like they'll have an entire position where all of the bases at that site were sequence and error um so you know what you'll see is you'll you know you might spuriously detect a variant at that site but you know the variant called or the sequencer will tell you hey you know I saw these bases it looked like an A but it looked like an a with 90% confidence and you know 90% confidence sounds pretty good but for these sequencer machines 90% confidence is pretty much at saying I'm telling you I'm 90% confident but I actually have no idea what's going on you know normally people use 99% confidence as the uh you know base level for saying that something was probably good and part of this is just because the sequencers themselves are very bad at estimating these probabilities so if you see you know if you have a site where you have 15 A's all of which are you know 0.9 you know probability of 0.9 and you have 15 C's all of which are probability you know five nines you probably you probably have you know two A's there there you know no uh no te's you know none of those .9 probability bases were actually sequenced correctly and one of the ways that we filter this out is by looking at the you know the percentage you know of times that we've seen that AAL across a population if we haven't seen it in anyone else and it has very dubious evidence then we can go ahead and throw it out if we see it it's you know very strong evidence or we've seen it elsewhere in the population you know then we'll say okay you know this is actually this is likely a real variant that we've seen another problem um that's a bit different from the sequencing process but the you know the actual algorithmic process is that if we have a large edit the algorithms that we're using to align these strings to the reference genome will often give us incorrect alignments and uh you know for anybody who's familiar with edit distance calculation algorithms you know in intuitively you know why this happens you if we have a large edit and we don't have any evidence that tells us oh you know this this is you know this is an acceptable edit we'll go ahead and generate a low probability you know for what the you for the sequence alignment so you know if we if we're aligning two strings you know we might say that these this string alignment has a very large edit distance if it's a very large edit distance did is it really correct to place a string here or does it you know belong somewhere else was the string just see sequence incorrectly you know we have this error rate do we just get a a really bad sequence and you know the last half of this read is just wrong and that's why we have this edit distance of 14 uh so you know and this is especially important when we talk about some of these uh important variants you know the mutation that John was showing earlier I think it's like a 10base deletion right uh so you know 10 based deletion implies that any string that aligns correctly will have an edit distance of at least 10 so you know we have to find a way to be sensitive to these strings that are aligned with high edit so ultimately what we wind up doing is we apply a variety of algorithmic cleaning steps and then we apply these statistical models at the end and this allows us to reconstruct the genome with fairly fairly high accuracy and uh you know I'll just talk about one of the um one of these processing steps today which is this uh reassembly this this graph-based reassembly and so this is a very common approach that we use to deal with the uh the edit problem so you know we were just discussing if we have a large edit we may not put the strings in the correct location or even if we put the strings globally in the correct location we may not locally have aligned them properly and uh this is a very common method uh you know if you're familiar with these tools which you some of us in the room may be or maybe you'll hear about them in some talk later you know there are tools like the gatk or you know there's a few popular ones like platypus or scapel uh you know we have great names in in BIO informatics uh that that use this exact sort of graph-based cleaning process and what we're doing is we're using a uh a de Bruin graph to go ahead and express you know what all of the different reads are and then what the sequences that these reads could you know could describe without you know and we kind of throw away our knowledge of what the reference genome looked like at that location we'll pull that back in later but just for a minute we're going to go ahead and we're going to throw out that information and uh you know who here is familiar with a de Bruin graph uh they they come up a bit in uh computational Theory and a few other locations but you they're not a very common data structure uh what a de Bruin graph is is really just a way of expressing transitions in a sequence uh you know so here let's go ahead and take this SE quence you know this you it's just a 10base genomic subsequence what we can do is we can cut this this subsequence into all of its you know K Bas long subsequences so you know here we have this you know 10 Bas long sequence we'll use K of three that gives us nine separate subsequences you know where each one has a two base overlap with a sequence before it and the sequence after it once we've got gone ahead and we've uh you know cut this up we can go ahead and put these sequences into a graph where you know if we if we saw you know in our uh you in the observed sequences that two of these subsequences are connected we'll put a directed Edge between them and uh you know what we wind up doing is we wind up walking this graph and really we we try to find all of the permissible walks between you know a start node and an end node in the graph so uh you know you might notice here this ACA node you know doesn't have any arrows leading into it and this act node has two arrows leading into it but only one Edge coming out of it so we can label that the ACA Lo the ACA node is our start node Act is our end node because they have different number of arrows going into and out of them and what we try to do is we try to find all permissible oan walks in this graph or you well the permissible oan walk in this graph uh so that's kind of the general theoretical setup for it uh the problem is and you know I I kind of said this in in passing earlier in the talk this process is very expensive as it's normally implemented uh so you know typically you know we we just said oh you know we we find the oan walk in reality um you know that's like a very nice theoretical setup but in reality these graphs don't have a single path you know for example if I saw some reads that had a variant some reads that didn't have a variant let's just let's just say you know in this entire region that I have where you know I have a bunch of reads I only have a single variant then my graph is going to have two paths so it'll have one path that is the S you know that is the string that contains the variant and one path that is the string that does not contain the variant and the way that we uh you know the way that we handle this right now uh you know in most of these these tools I was telling you about earlier is we go ahead we find every single path through the graph we'll go ahead and perform you know for every read that we had we'll perform an edit distance computation against every single graph you know every single graph that or every single path that we've walked through the graph and then we'll attach a score to this alignment so what this winds up having um you know it's so you this this edit distance computation is Big O N squar it's a dynamic program for every single read to to uh path you know we wind up doing N squared computations again so this algorithm itself has you know Big O end to the four runtime complexity um and you know I don't know how many of you are you know like algorithmic you know theorists and whatnot but I think you know we all can tell you know Big O N to the four is not really the runtime complexity that you it's if I if I come up with an algorithm that's Big O N to the four I don't go home and you know like oh yeah you know get together with my friends be like yeah I came up with this awesome algorithm Big O N to the four complexity unless the previous algorithms were you know like NP complete or something you know Big O N to the four better than MP complete not better than much else um so we instead come up with a different approach that doesn't look just at the raw graph but looks at the structure of the graph in comparison to the ideal graph that we would draw up for the reference so you know let's go ahead and say this was a reference sequence and then we had you know a bunch of reads that had this uh you know this G to T edit so we can go ahead and we can build one graph that is the reference graph and then we can build a second graph that is the OBS the observation graph and one thing that we can do is you know we could still go ahead and you know enumerate all the possible paths pull those all out run this you know Big O N to the four you know scoring algorithm or the simpler thing that we can do is we can just look at where these two graphs diverge and we can say okay well you know so we've got you know this bubble right here between CAC and act where our reference graph does one thing and our you know observation graph does a different thing we'll go ahead and call this a bubble because that's kind of the standard terminology that people use uh you know it kind of makes sense you've got a bubble you know that kind of comes off the graph and we can you know then just go ahead and look at the two strings that you know you know that we have in these different paths and note that hey you know this is just a simple one base edit and we can actually come up with uh you know canonical representations for describing these edits so if we have a one edit there's a very clear way we can come up with that just by in inspecting the structure of the graph if we have an insertion or deltion edit there's another very clear signature in the structure of the graph that allows us to extract it right from there and uh you know from this we actually wind up having complexity that is worst case n squ and best case linear yes is the reference sequence ctg CA or am I missing something uh reference sequence so the way that you would read this so the reference sequence is ACA then you add a c so it's AC a c add a t a a c g c a CT so it's what you do is for every for every Edge that you go you grab the last character from the new node I'm refering to the under reference oh yes C yes yeah sorry about that um I think what I did is I just truncated the last I I think I truncated a letter in there but yes correct yeah it should be that my apologies um but yeah so this provides a nice Improvement in the complexity of this one algorithm and this one algorithm is actually where uh you know we spend a fairly good amount of our time there was a recent study I think that that put this on 75% of our runtime is spent in this one phase is there any family of algorithms that you can get useful work out of that doesn't require reassembly so there there are um so you don't strictly speaking have to run reassembly and what actually a bunch of people do is they app you they apply us you know there's a bunch of different classifiers that people have gone ahead and used that can detect you know approximately when you need to use reassembly and when you can use the naive approach which is just to go directly off of the alignments so you know in I think it's about somewhere between 70 to 90% of your genome uh the genome is unique and you don't tend to have large edits so in those locations you don't need to run this reassembly process at all in that last 10 to 30% of the genome you know which we can statistically identify you need to run these expensive algorithms that actually you know takes 75% of the time so even though you're only running this on you know 10 to 30% of your genome it's about 70% of your runtime yeah and the um you know essentially the the big issue is that in areas where you either have low mapping sensitivity so it's sequences that are common in the genome you know one thing that we don't often talk about is the repeat structure of the genome so you know it's nice to assume that you have 3.2 billion completely unique strings but uh you know 3.2 billion where you only have a choice of four letters you're you're going to have some repeats and actually in humans the largest repeat blocks are 10,000 base pairs long and the length that we normally use for our reads is about 250 so you know if you have a 250 base pair string and you have long blocks of repeats that are at least 10,000 base pairs long you often can't map uniquely to that location um so sometimes these sorts of algorithms can provide an improvement but so um you kind of the the big thing getting back to this uh you know this big o n squ complexity you know just I I just want to show you the graph structure of 20 bases from The genome yeah we talked about that 2% error rate so this is a 200 basee pair segment of your genome that has one true edit so it has one true variant and uh just with this 2% error rate from this simple region we wind up having you know 300 or you know 3,000 you know graph sub segments along with 30 different valid paths that we can take through this graph and this is uh you know so this was 200 base pairs normally when we run this algorithm we run it on about you know 2,000 base pairs at a time uh you know so with that error weight you know you can start start imagining you the actual number of paths through a graph winds up growing linearly um so actually this this complexity is a pretty big deal so then ultimately you know once we've gone ahead and we've run this algorithm that will clean up our observations of edits what we go ahead do is this genotyping process um and in this genotyping process we're essentially looking at every position of the genome so you know we call this a lowai so we look at every lowai of the genome we look at all of the observations that we have there and we apply a likelihood model uh to score the probabilities of these observations at this site given you know a hypothesis for what you know whether there's a true variant or not um so you know in our approach we use a likelihood model that assumes uh site Independence and then we use a um you know a binomial prior for this site or for each site where the binomial prior is drawn from you know essentially what the expectation that we see you know in a Le you know what's the Frequency at which we expect to see in a Le in this population so you know once we've collected you know these 100,000 samples we go ahead and we run an em style process to estimate these per you know these per location uh you know prior probabilities we feed those into our likelihood model and we generate the likely call at each site so this is this is kind of how we go ahead and we extract these variants finally we have to make sense of this variation data so you know uh John talked a little bit about how a variation impacts of biology and uh you know we can we can really break it down into two you know General classes of effect so you know on one side a variant can modify a protein so it can change or break a protein product um on the other side we can have a variant that changes how you know how these protein production processes regulated so you know uh we actually expect that many variants are going to fall into this because as we were saying earlier a variant can only modify a protein if it's in the part of the genome that codes for a protein uh that's only one % of your genome so you know if we assume that there's an equal distribution of variance between the 1% and the remaining 99% most of the variants are probably going to fall into this class but the big question is you okay so let's say that we've gone ahead we've got a variant that falls into this this class of of variants that doesn't modify a protein but changes how much of a protein is created what we want to do then is link that to how this protein was expressed and the way that we normally do this is we run a uh a statistical you statistical procedure called an eqtl or what this is is a you know it's an expression quantitative trait Losi experiment which is a fancy way of saying we're going to look at all of the locations that we have variant and then we're going to go ahead and say you know what correlation do these variants have with the expression of a gene uh and one of the big problems that we have is so if you have two variants that are close together they're going to be inherited at roughly the same frequency so what we can frequently do is link you know we can link a probability to a a section of the genome but we can't necessarily link it to a single variant so what we really want to do is break up these blocks so you know we might have these 100 base thousand Bas blocks where maybe we have one maybe we have two you know or let's say that we have multiple variants because if we have a single variant you know then we don't have to break up this block if we have two variants in the block we want to come up with some ranking you know we want to associate a higher probability to one lower probability to the other so you know once again if the variant modified a gene we would have an easy way to handle this you know if if the variant didn't change the gene then we could say okay you know even though you know statistically speaking since this variant is inherited at the same frequency as this other variant since you know that variant didn't modify the gene the other variant does modify the gene we could link it to this phenotype but once again 99% of our genome does not code for proteins so how can we make sense of this last 99% and you know is this really important so one of the things that's uh you that's interesting we did a study looking at um mutations in uh certain you know certain class of leukemias and uh so know if you actually go ahead and you compute this uh you kind of decision tree structure this looks at um you know it's a decision tree that describes the you know relationship between frequency of mutation and uh you know different genes and this long tail running down the side here is people who you know didn't have a mutation here didn't have a mutation here no mutation here no mutation there no mutation all the way down and one of the things that's actually very interesting about leuk leas is it's pretty common to have you know to get acute myoid leukemia and to not have a single variant in your exone so you know they did a this is this is actually drawn I think from tcga data tcga was a big study called you know the cancer genome Atlas did exactly what it sounds like it tried to do it tried to create an atlas of variation across a whole bunch of cancers and uh you know they sequenced about 200 people with AML and in uh I believe about 20 of those people they did not have a single mutation in their exone so we want to find a way to understand what's going on there and one of the things that's uh you that's very interesting uh this was actually a you know hypothesize this has been a an idea that people have been talking about since about 2006 but there was a really nice review that came out of this last year um you know if we have a mutation in the exome we have a grammar we can use to say Hey you know this mutation changes an amino acid this mutation you know cuts off translation this mutation changes how this protein is spliced together there must be a grammar that exists for regulation and uh you know what people have been looking at is uh you know they've essentially pulled out a set of about nine transcriptional you know these regulation grammar cards so you know you might say Hey you know a lot of the way that that transcription is regulated is you have proteins that bind to the DNA and you know either they increase the activation they promote building a gene or they go ahead and they repress you know the transcription of a gene and actually a lot of this can be you know you can predict some of this if you look at hey you know how many sites do we have where that you know that protein can bind or you know if we have two spots that are close to each other how close are they you know are they five bases apart 10 Paces apart um so they put together these uh this grammar and you know really what we what we want to do and this is what this fig project that we' started working on is doing is trying to develop a way to enhance these statistical models that you know tell us hey these two mutations you know they're in a block we can tell that they have a statistical linkage but we don't know which one is statistically linked and then we want to feed these grammar cards in so you know we might say Hey you know we know that there's a trans there's a protein that binds at this position or at this position but you know no protein could be impacted by you know no protein binding could be impacted by this variant so then we go ahead and we say okay you know this is actually the high probability variant so you know this is uh just a little bit of work that we've we've really started to do recently but really what I want to you know want to get across is that you know as people who have understandings of text processing there's a lot of ways that you can can help you know what we're what we're really trying to do is come up with methods for you know going ahead and identifying patterns and edits and text you know we're trying to find un you know we're trying to understand the underlying grammar of this text and these are kind of core you know core ideas in natural language processing um so you know if you're interested you know in getting involved you're interested in you know contributing to the state of the art in these fields all of our projects are open source software we all have you know we have all posted on GitHub uh GitHub bigdata genomics is our organization they're all Apachi to licensed um and we're actually currently looking to hire software engineers at Berkeley so if you'd be interested in this you know feel free to go ahead check out our GitHub Fork our project Push Pull requests we love pull requests and uh you know if you're interested uh you know in actually trying to work on this full-time you know please feel free to come back to me afterwards uh you just wanted to acknowledge we've actually uh you we a you we really thrive on the open source Community we've been able to pull together people you know formally from about six institutions and informly from 12 so you know although I presented on a big body of work today I can't claim responsibility for all of it so you know just want to thank the 40 different contributors that we've had to this work over the past uh two years so be glad to take any questions and thank you for listening [Applause] so I didn't see fig on GitHub yet it's um it's in uh my personal so if you do it's ffig so yeah it's it's just really just started to spin up over the last like week or two okay so no problem so seems like your would be a lot easier if if the Bu you're using to we the would be one more that produce longer Str sentences is there any yes and so um so the accuracy let's come back to the accuracy question um the string length yes so there's a bunch of uh really cool projects um you know a few of them are you know actually commercial some of them are commercial but still in the startup phase that are trying to build what we call Long read sequencing techniques and uh yeah so there's a a company down in Meno Park actually Pacific biosciences or pack bio for short and they generate reads that are you like 10,000 base pairs long but with about like a 15% error rate and then uh there's a company um out of the UK uh really cool Oxford nanopore um they have a USB drive sequencer so it's it's like uh this long you know it's it's like the size of this remote and uh people have so people have generated crazy length sequence with it I think the longest one that I've heard of is about 200,000 base pairs um the yeah and the error rates actually been so like it first came out and people were getting 30 to 40% error rates which you know it's like 200,000 base pairs that are mostly you know like junk is you know it's interesting but not quite prime time but they've gotten the uh the error rate down to you know somewhere like 15 to 5% depending on you know how new of a sequencer and how new chemistry you're using so I think there's a lot of opportunity there especially with the you know the last one it actually has a very very low cost model uh yeah so both of these techniques use uh you so it's like the pack bio uses zero Mo Wade guides which I don't know what that is and then the um the Oxford nanopore uses nanopores which so it's like there's a bunch of people who are doing really awesome physics to solve these problems um so I I think that it'll get aot better yeah so I think we're out of time but I'll be glad to stay around for any questions afterwards so [Applause]