Thanks for the introduction, everybody. So this talk is actually quite complementary to the previous one. In the previous talk, we've seen that it's actually possible to have strong security guarantees against high-channel attacks thanks to the masking counter measures, assuming that we have a sufficient level of noise in the implementation. And in this talk, we are concerned with the other question, which is how can we convince ourselves that one concrete device, with concrete leakages, actually has the sufficient level of noise so that masking is going to play its role. So this is the outline of my talk. I will start with a few words of introduction and motivation. I will then explain what leakage certification was so far and what were the limitations of previous approaches. We'll need to introduce a seemingly useless quantity and then I will show how this quantity can be used for our main result, which is upper and lower bounds for the mutual information. And I will finally explain how we can use these results in order to analyze concrete leakages with large number of dimensions and conclude. So let's start with introduction and motivation. So this is a paper about masking. In masking, what we want to do is to compute securely in a leaking device and typically what we are going to do is to split every sensitive variable like here the Y into D shares and perform all the computations on those shares only. And as a result, the adversary will be able to observe what we call a leakage trace which is here, so this is typically the power consumption of the implementation that manipulates the D shares. You have the time samples on X axis, the leakage on Y axis and what we expect is that there will be some leakage samples depending on the first share, some leakage samples depending on the second share and so on. And there has been a large body of theoretical work on this counter measure ranging from abstract to more concrete and I would say the most concrete view on masking is that what ultimately we can do is to bound the mutual information between the sensitive variable Y and the full leakage vector by the mutual information between one share, Y1, YI, sorry, and the corresponding leakage samples. And we raise this to the power D and as a result, if this mutual information is smaller than one, we have a mechanism that allows us to amplify the amount of noise in the implementation exponentially. And based on this view, on this theory, of course the practical challenge is how can we bound this mutual information between one share and the corresponding leakage samples. Here I give the equation for the mutual information, which is essentially a weighted sum of log probabilities conditioned on the leakage. So this is the equation for a discrete leakage function, which can happen for example if your sampling device or your oscilloscope is using 8 bits of quantization. Sometimes we also like to view the leakage as a continuous random variable and in this case we just turn the sum into an integral. I would say in both cases the problem is exactly the same and it is that concretely we have no clue about this leakage distribution. So we really don't know what's the distribution of this power consumption and this is because it usually comes from a complex device with millions of transistors and so on. So if I go back here, that means that I don't know the function F nor the function P and I cannot compute this equation directly. And unfortunately it's also hard to estimate this mutual information because it's known in the literature that the mutual information is in general hard to estimate meaning that all the estimators we have are biased and the bias is actually distribution dependent. In fact even the sign of the bias is distribution dependent so it's not even easy to bound the mutual information. So in order to mitigate that what was done so far before discussing leakage certification I would like to say a few words about leakage evaluation in general. So in the literature what will be done in a vast majority of the case when you perform a concrete sectional attack is that the adversary or the evaluator is going to directly estimate the leakage probability density function or the leakage probability mass function and try to attack with this estimated leakage model. The adversary it's perfectly fine if it works because then you recover the key. As an evaluator it's really not perfect because even if it works you have no guarantee that you are optimal as an adversary and I would say anyway the main problem both for the evaluator and the adversary is that when this approach doesn't succeed it's quite hard to interpret because when it doesn't succeed it can mean two things. Either it means that the leakages are sufficiently noisy or it means that the statistical models that you used in the evaluation is not sufficiently accurate and that's what we usually call a false sense of security in the literature. So in order to mitigate this risk of false sense of security a first step has been made with this idea of leakage certification and the idea essentially was that rather than just launching the attacks what you can try to do is try to distinguish between estimation errors and assumption errors in the statistical models that we use. By estimation errors I mean errors in the model that are due to a lack of samples by assumption errors I mean errors that are due to a wrong to a wrong choice of statistical model. So typically if you assume that your leakage follow a Gaussian distribution and they are not. So I will try to illustrate this with an example. Let's imagine that this is the leakage distribution that we want to evaluate, to estimate and that we made this Gaussian assumption. So we built a Gaussian model for this distribution what we can then do is just to sample both the model and the true distribution and built a non-parametric estimation of the distribution for example with histograms. This is what we have here and the red samples are the model samples, the blue samples are the leakage samples. So if you have this situation where typically the number of samples is not sufficient you will conclude that estimation errors dominate and that you need to measure more. If you do measure more at some point you will reach this situation where clearly you can see that there's a discrepancy between the model and the true distribution and then you will rather conclude that assumption errors dominate and that you should look for another statistical model. And based on this the main idea behind leakage certification was to say that in practice you can consider that your leakage model is good enough as long as the assumption errors are small in front of the estimation errors for the number of traces that you could measure. And that typically means if you are an evaluation laboratory you can measure your chip for one week you use a statistical model and this test is going to tell you whether it's enough or whether you have to look for another statistical model in order to efficiently exploit the information that's available. So there's an information theoretic view for this problem and for this I need to introduce this idea of perceived information that comes from a couple of years ago and if you look at the equation it's very similar to the mutual information the main difference is that right of the logarithm we replace the true probabilities that we don't know by the probabilities is assigned by the statistical model that has been estimated. So intuitively this is really the amount of information that you can extract from the sample with a given statistical model, possibly biased by both estimation and assumption errors. So if you look at the equation it may seem that we are not so much advanced because there's still the F here that we don't know but the good news is that these times this is something that we can actually compute in a two-step process, so what we can do here is we first estimate the model and once we estimated the model we consider the model as fixed in the equation and then we perform the integration by sampling the true distribution which just means that you pick up a lot of test samples from your real measurement apparatus and you do this sum of log model probabilities here and the main reason why this is correct is intuitively this blue thing here can be viewed as the empirical distribution that converges towards the true distribution. Okay and what's important to see here is that this perceived information is going to be equal to the mutual information in case the model that you use is perfect and it's going to be different in all the other situations and for example the perceived information can even be negative if you have a model that is completely disconnected from the actual leakage that you try to analyze. So concretely these are the plots that we are usually able to build what we do here on the X axis we put in log scale the amount of samples that we used to build the statistical model on the Y axis we put the information theoretic metric which is this perceived information here for a Gaussian leakage model and what we see is that as we increase the number of samples in order to build the leakage model we can extract more and more information and at some point there's a kind of saturation and saturation typically means that you have estimated all the parameters of your Gaussian model sufficiently well. If we then launch leakage certification what's going to happen is that at some point the certification test is going to fail and when this fails at this stage for example what it means is informally that the PI curve saturates too far from the mutual information and despite we still don't know what is the mutual information so that really means the evaluator has to look for another statistical model. So there were limitations to this approach I would say one first very concrete limitation is that it may of course happen that we lack samples to be conclusive that's an example where I replaced the Gaussian leakage model where a Gaussian mixture model which is the dotted curve and in this context we see that for the amount of samples that we were able to measure certification didn't fail yet which of course doesn't mean that it will never fail if we could access to more measurements. So that's one thing I would say the most important problem or more important problem is that this certification test they are only qualitative they tell the evaluator if the model is good enough or not but if the model is not good enough we have absolutely no indication about what's the actual distance between the perceived information and the mutual information because in general we still don't know what is the mutual information we don't know what is the perfect leakage model and that's annoying because of course this means we have no indication about what is the security loss because of this incorrect leakage modeling. So in order to move forward I first need to introduce this seemingly useless quantity which is the hypothetical information so the hypothetical information is again quite similar to the mutual information but this time both left and right of the logarithm we replace the true probabilities by the probabilities that are assigned by the model and this time intuitively what this means is what this represents is the amount of information that would be extractable from the samples if the true distribution was the model. So very concretely this looks nice because of course this is now an equation where everything is known so it's much easier and also much faster to compute because we know the distribution sometimes we even have an analytical formula for the distribution what's much more negative is that at first sight it's completely disconnected from the true distribution the true distribution doesn't appear in the equation anymore and that means typically that this hypothetical information will always be positive even if your model is completely incorrect you could even build the model without using your leakage samples and you will have a positive hypothetical information so that means in general it's not very useful what we are going to show is that in some specific cases for certain families of distribution it can be quite useful and in particular the most useful distribution is going to be the empirical distribution and we are going to denote the EHI as a hypothetical information when you use the empirical distribution as a model so now what is the main result that we have it's essentially upper and lower bounds for the mutual information based on this unknown model so from a security viewpoint I think the most interesting result is the upper bound for the mutual information metric because this allows us to lower bound the security which essentially is that in expectation over the constructions of the models we can show that this empirical hypothetical information is an upper bound for the mutual information and it also converges towards the true mutual information so it may look surprising that we have this type of result because in general we don't have that for the mutual information in fact there are two ingredients that we leverage to make that possible and the main one is that in our mutual information in the context of key recovery one part or one of the two random variables has a constant and known distribution the secret variable is a constant uniform distribution so you don't need to estimate this one and as a result the mutual information becomes biased upwards everywhere a little bit like the entropy would be so that's one thing that we use the other thing that we use is the nice properties of the empirical distribution that converges towards the true distribution in a monotonic manner we also have a lower bound for the mutual information metric which is essentially that the perceived information is always lower than the mutual information this is a bit more technical it's obtained by solving an optimization problem but it's also quite intuitive because it shows that whenever you use an incorrect leakage model you can only lose information now concretely what does it mean as usually in this field we perform experiments and we usually start with what we call simulated experiments so in these simulations we generate leakages ourselves and we perfectly know what is the leakage distribution so in this case we can actually compute the mutual information as well so here in this graph you have this we can support again where the x-axis is a number of samples used to build the model the y-axis are the IT metrics and we have the perceived information in blue the hypothetical information in red and the mutual information in black we see that we as expected have a bound and one first nice observation is that the hypothetical information which is the bound that we are always going to use is converging faster than the perceived information and that's essentially because it's a simpler quantity and it doesn't embed a kind of causality step in its estimation and what's also nice I guess from an evaluation viewpoint is that the bound is becoming tighter as the number of samples that you have increases and that means if you're an evaluation lab the more you measure your chip the better the security claim that you can make will be so these are four simulations we as usual next move to concrete experiments so these are the results that we obtained with an FPGA implementation of the AES we again have the hypothetical information in red the perceived information in blue both corresponding to the empirical model empirical distribution we have the bound aspect again so what's mostly different in this case is of course we don't know where the mutual information is because this time we have no clue about the real distribution and also the total number of samples that we could use is a bit lower because it takes much more time to measure the chip than to generate the leakage ourselves and what we did in addition is to look at other statistical models in particular the Gaussian leakage model because it's always convenient and this is what we have here so here we have the Gaussian perceived information and the Gaussian hypothetical information we see that they converge much much faster because the models are also much simpler and what's nice is that despite the model is simpler they still fall within the bounds so that typically means for this particular device which is not a general conclusion the model, the Gaussian leakage model is actually good enough and that leads me to the last step this good news that we can actually use here a Gaussian assumption is interesting because there's one thing that I've been hiding a little bit so far and it's the fact that in general what we want to do as evaluator is not to bound the amount of information that you have for one single leakage sample but it's to bound the information that you have for all the leakage samples so typically this is what we call multivariate analyzers and this is an example where I compute this hypothetical information for all the time samples corresponding to the manipulation of one share so to make the link with the previous figures the conversion plots that I've just shown actually corresponds to this single sample here which has the maximum amount of information and this full figure here corresponds to the older time samples corresponding to the manipulation of the first share of my masking scheme so what we want to do is not to know what's the individual information for every point in time for all the points in time and this is something that we can quite efficiently do under the Gaussian assumption so again this is what we call multivariate Gaussian HI and we see here the information progresses as you are using more and more dimensions the interesting bit is that there's actually a factor of 5 between the best univariate attack and this best multivariate attack that we have so it really means that if you ignore this fact that you have actually many time samples available you are going to overstate security by a factor of 5 raised to the power d which can be very substantial and what's also interesting is that there's another factor 10 between this bound that we've just defined and the naive bound where you just sum the information of every point in time which is essentially assuming that all the informations are independent and it turns out it's not the case so in this case it would be much more in fact too conservative and the last thing I would like to show is why the hypothetical information bound is useful in this context and for this I again show the convergence plots for the multivariate analysis so again number of samples to build the model information theoretic metric this curve is here for the hypothetical information and the green one is for the PI for 10 dimensions we are still able to estimate the PI for 40 dimensions you see that you have more information in the bound but PI becomes harder to estimate so the bound becomes increasingly useful and for the 250 dimensions there's no way we can estimate the PI we can only use the bound and that's essentially because there the PI will be stuck to minus infinity all the time and so it's time to conclude so to the best of my knowledge these are the first quantitative tools that we can use in order to avoid a false sense of security in such an L security evaluations and by this I mean avoiding this problem due to incorrect assumptions about the leakage model when we have low number of dimensions we have a formal bound on the material information which is based on the slow convergence of the empirical distribution when we want to analyze larger number of dimensions we show that it's usually needed and useful to have simpler models and that suggests as a typical strategy when you have a leaking device to first try different models for low number of dimensions and compare with the empirical bounds so you know whether the model is good enough and then generalize to multivariate attacks the main advantage of all this is that performing this type of text is much much faster than mounting an attack both in the amount of data that you need and in the amount of time that you need to compute the matrix for example it's really the first time that we are able to bound the material information for a leakage vector with 250 dimensions and what I think is also interesting is I believe it's potentially applicable in other contexts like for analyzing privacy leakage in particular I would say one nice feature of the bound in the context of open data publishing is that the tightness of the bound increases or becomes better if you reveal more information that this typically means that as a database owner you have no incentive to hide the data that you collected in order to show the bound and this concludes the talk thank you Any questions? I have one question are you familiar with the quantitative information of theory? I don't know much myself but it sounds vaguely related to me not enough not enough I would say because from what I know very little they also they have techniques to quantitatively bound this mutual information associated to leakage from the communication channels and I just wonder if they are in a relation but I don't know much about it sorry ok thank you let's thank the speaker again


Hey guys, it's MJ, the student-actry, and welcome back to our series on probability paradox. So in the last video, we had the lovely decision where one of the boxes contained a million dollars and we decided whether we're going to choose it. Whereas in today's video, I'm sad to say, but it's a lot darker.   What they're going to do is they're going to take a gun, it's one of those old-school guns. I don't know how to draw a gun, it's got a little chamber and then a little trigger. Anyway, that is our gun, think of it like a cowboy gun. It's a cowboy gun and there are six spaces in the barrel, so six spaces in the barrel. And what the crazy terrorists have done is they have put two bullets inside the barrel and this is important in consecutive order. So they've put the bullets in consecutive order inside the barrel. And what they do is they take this gun and they put it towards your head.  So yeah, they've got the gun, they've got it to your head, they spin it and they say, we're going to shoot you and if you don't die, we're going to let you go. This is their sick game. So they spin the barrel and they pull the trigger and fortunately you survive, it's a blank. Okay, so they've shot the gun, it is a blank. And this is where the game comes in. The terrorists give you two choices, okay, choice number one is to re-spin the barrel. Choice number two is not to re-spin. Which one do you do? And they say, if it's another blank, we're going to let you go, you can return to your country's embassy, all is forgiven, we're going to be best mates.  Okay, that's quite dark. Sorry about that. Okay, so what do you do? After the terrorist has pulled the gun and it's been a blank, are you going to re-spin it with choice number one or are you not going to re-spin it? Choice number two.  Quickly pause the video and think about what your answer is going to be. Okay, great. Now you can un-pause the video, although I don't know if you could hear that instruction. Well, anyway, I hope you're back to the video. Back to the video. And what's interesting is that a lot of people choose choice number one.  But what if I told you that choice one is the wrong decision and it's more likely to get you killed? Okay, now that's kind of crazy thinking because you're thinking if they re-spin it, there's more blank barrels than bullet barrels. And we've already used up one of our blank barrels. So by re-spinning, I should be refreshing the blank barrel. That's the school of thought there. And so you would say you have a one in three chance of getting shot. And you're correct. You do have a one in three chance because when you re-spin, there's two bullets, there's six potential spaces, you know, really hardcore maths. You can see that two six is the same as one third. So you have a 33% chance of dying in, by doing choice one. But choice two, you only have a 25% chance of dying. And if you're really good at mathematics, you'll notice that 25% is less than 33%. Now, a lot of you are probably saying, no, no, this can't be true. How can choice two be the better option when we've used up one of our blanks? Well, let me show you the power of conditional probability and why you should always understand the mechanics of devices when using probability. So let's say this is our gun barrel. Remember, the two bullets are in consecutive order. That's that's crucial pieces of information. Remember, we know that a gun rotates after it shoots. Okay, that's how that's how guns work. Okay, so if you had to re-spin, you could see one, two, two out of six. There we go. That's a third, but if you don't re-spin, what an effect you've done is you've reduced the state of the various ones that you're exposed to. Because because you're being told that the first shot was a blank, it means your space has been reduced from all six bullets to just the four bullets that were blanks. Okay, so before we had six potential ones, now we only have four potential ones because we were told that the previous one was a blank. Now, if it's this one, we've got one, two, three, four. So we have four instead of six. But if it was this one, you're safe because it's a blank that follows up. Number two, you're safe because it's a blank that follows it. Three, you're safe because there's a blank that follows it. It's only blank number four where you actually get shot, which means it is only one-fourth. And like I said, one-fourth is 25% chance of getting shot. So this is a very, very educational video.  So don't spin because they're in a consecutive order. If the bullets were not in consecutive order, hmm, then would you spin or wouldn't you spin? Let me know in the comment section below and like always, hit subscribe. What else do the kids do these days? There's liking videos, you can share videos. Can you poke a video? I don't think you can poke a video. But do whatever you need to do. This encourages me to keep making these types of videos. So let me know if you've enjoyed it. Next week we'll be seeing another probability paradox video. Hopefully it won't be as dark and dingy as this one. Thanks guys so much for watching. Cheers.


Very descriptive stories in the Indian culture about the type of jewelry the courtesans used to wear. This one pin, if she pulls, pulls, the entire jewelry falls down in one… Karma is like this. It's a complex web of chains, but there is just one single pin, just in case if you find it. Another karmic aspect falls off and you exist as a liberated being. Karma probably one of the most misunderstood words. For sure it's become part of the English lexicon today, but misunderstood and misinterpreted in a million different ways, a range of things. The very way the nature of karma is just like that, it's interpretations. The karmic structure is a very complex mess, but there is a… there are very… what to say, very descriptive stories in the Indian culture about the type of jewelry the courtesans used to wear. That is, very famous courtesans were covered in gold and diamonds. No clothes, only jewelry covered their body. Such complex jewelry that when… when the men who came to them, they had no clue how to take off this jewelry because it was such a complex web of chains. Try as hard as they did, but they cannot get this jewelry off. Jewelry is beautiful, but for a man who is… whose mind is running right with lust, this is a barrier. So usually she encourages him to drink and drink little more and little more so that he sleeps and gifts her more jewelry and goes home. But when she wants to take it off, there is just one pin normally located at where our anahata is, this one pin if she pulls, pulls, the entire jewelry falls down in one… just like that, it falls down. Stories like this, it's a complex web of chains. Some of them of course decorated with diamonds, some are ugly, some are rusted chains, but chains and chains and chains, but there is just one single pin. Only because you are not able to consciously find the pin, the fundamental reason. Let me tell you, the fundamental reason why there is a culture or there is a tradition of depending upon a guru for one spiritual growth is just this, that you want him to pull the plug when the time is ripe because in this complex web of chains, you don't know where the pin is. Right now, if you try to find it, you can go on a search forever and not find it. And if you find it, just in case if you find it, you will dismantle it in such a way that you will dismantle your very life. To dismantle it skillfully that just what… just the karmic aspect falls off and you exist as a liberated being, that takes lots of skill.  It is your karma that you have to endure me. If you had figured it out yourself, you didn't have to bother about me. So said guru, when are you going to pull my plug? That means it's not… you're not ready yet. If you have… if you are in a state where you think your karma is a burden and you must get rid of it, you are not yet ready for it. If you come to a state where you have learned how to transform every memory, conscious and unconscious, pleasant and unpleasant, beautiful and horrendous once, everything into well-being, if you come to that state, then it'll be good for me to pull the pin. Now if you pull the pin, because this is not liberation, this is an escape. There is difference between walking out of this body and committing suicide. There are two different things altogether. Walking suicide means you want to escape a difficult situation. Walking out of this means your term is over, your time is up, so they've released you. These are two different things completely. If you escape from the prison, you will have to run for the rest of your life.  That's a big difference.


So I'm going to give a lecture on how genome assembly works, go over some of the theory behind it, how we assemble genomes from short and long reads, then we'll have a coffee break, come back and you'll work through a lab where you'll actually get to assemble a small genome using some Pac-Bio and Illumina data. So there's a lot of different ways of presenting a high-level picture of assembly, here's how I like to think of it. We have a genome, we chop up many copies of the genome into fragments, we then sequence those fragments and the process of genome assembly is just essentially reversing the sequencing process and stitching together the original genome from those reads that we've sampled. People have used different analogies of putting together a puzzle without being able to know what the puzzle actually looks like or cutting up a bunch of newspapers, one that all uses, let's say I grab all the binders off your desks with the coarse materials, I take them to the paper shredder, shred it up into pieces, dump it on the floor and say reconstruct the pages that's in this binder. You'd be quite mad at me, but you could get a better understanding of what an assembly is. Now the key things here are that if we, if I shred that into really tiny pieces, you'd have a lot of leftover white pieces that give you no information of how they go together. Those are the repeats in the genome where we just don't have enough information from say short reads to assemble them back together. Conversely if I chop it up into very large fragments, just each page into three or four pieces, you'd have a lot of information to stick those pages back together and it would be relatively easy to assemble. So the talks in our three parts, I'll give you an overview of how assemblers work, a little bit of theory behind it. Then I'll talk about assembly algorithms for short and long reads. So that is two distinct parts because the methods that we use for short read assembly like Illumina reads are completely different than the methods we use for long reads. They're all based on the same underlying theory which I'll present first, but I'll give you a view of what the assembly pipelines for the different problems look like. And then finally, the third part which is going to lead into the practical session. I'm going to talk about what type of properties or features of a genome make short read assembly difficult and how we can measure that beforehand using some software that my group develops. Okay, so then here's a view of how assembly works. We have an input which is our genome sequence which is shown up in here in red. It's one point you're working, yes, kind of, up in here in red. We take many copies of that genome. We then fragment it into pieces and then read each one of those individual pieces using the DNA sequencers that I introduced to you yesterday. Now we call this process whole genome shotgun sequencing. The shotgun meaning that we randomly fragment the genome. We don't know where the pieces came from in the genome. We just blow up the genome, sequence each one of these fragments, then we need to put it back together.  They talk about shotgun methods of genome assembly. Now if we knew where every one of these reads came from in the genome, if we knew that this read here down at the bottom is the leftmost read or covers the first base through to the 15th base of the genome, we knew that this read starts at the fifth base and so on, it would be really easy to do the reconstruction. We could just merge all of these sequences along the genome to stitch it back together. So we'd start with this read, merge it with this one which adds that CG base, merge it with this one which adds GC, TCT, AGG and so on. Just walking along these ordered fragments until we've reconstructed a whole genome. Now the difficulty comes in that we don't actually know where the reads came from. We don't have this total ordering of the reads. We only have their read sequences and then we need to computationally infer what the order of those reads were on the original genome. And unlike when in the other practical sessions you've done where you've mapped the reads to a reference genome, which give you this ordering or an approximation of this ordering, in de novo genome assembly, we don't know anything about the genome. We only have this set of reads. And we need to look at the reads and try to figure out how to reconstruct the sequence. So this is one of the key terms in genome assembly is the idea of coverage. Coverage has probably come up in the other practicals, but I'll just reiterate what we think of it in assembly. And this is the average number of reads that's covering any position in the genome. So if in our read sequences, which are shown in blue here, we have 177 nucleotides total and our genome length is 35 nucleotides. Our average coverage is 177 divided by 35, which is about 7x, or what we say 7x coverage. What we mean by that is each base of the genome should be covered by around 7 reads. Another way to look at coverage is it can refer to the number of reads covering a particular position in the genome. So the coverage of this T here is six, as six of these blue reads cross this T position. Now, when you're doing a genome assembly, coverage is an incredibly important thing to consider. To assemble the genome, we need a lot of redundancy between our read set. We need reads that overlap each other that we can compare to each other to say that they might have come from the same region of the genome. And to ensure that reads overlap, we need to redundantly over sample the genome. We need to sequence it to 30, 40, 50x coverage to make sure that we have enough overlapping reads that we can walk across this whole sequence. The coverage requirements is a really common question I get. Someone will come to me and say, I want to assemble this genome. How much sequence? How many illuminated lanes do I need to put towards it? Or how many nanopore flow cells? And it depends on the size of the genome, how repetitive it is, what sequencing technology used. But typically we aim for something between 30 to 50x coverage not to get a good assembly. Okay, so the basic principle of assembly is that if we compare any two pairs of reads, reads that might have come from the overlapping positions of the genome, so the same location on the genome should be quite similar to each other in their sequence. We should be able to find reads where the end of the read or the suffix of the read is similar to the prefix or the beginning of another read. So if we look at this example here, we have our genome sequence in red. This read started from this position. This read started from this position. And they share this overlap of about maybe, say, 15 bases here. So they're very similar in their sequence. We can find that suffix of one read that matches a prefix of another. And this gives us some bit of information about what the genome sequence might be. So I mentioned in the intro that we use different assembly strategies for short and long reads. I'm going to talk about long read assembly approaches first. So as I introduced yesterday, long reads are produced by the Pacific Biosciences Instrument and the Autrib Nanopore Sequencer. We can get reads that are in excess of 10,000 bases. That's quite common, but they have a much higher error rate of 5% to 15%. And the key computational challenge and the thing that labs like mine work on are trying to overcome this high error rate in the sequencing data. So on the other hand, short read sequencing, which we've heard about throughout the course from Illumina, is very high accuracy, less than 1% error rate, and very high throughput. So you can get a lot of short, 100 base pair reads. The drawback of Illumina sequencing, which I've touched on before, is the short read length limits our ability to resolve repeats. And the key computational challenge is just being able to efficiently deal with this massive amount of sequencing data that Illumina produces. Yeah. Those 30X to 50X sort of typical coverage guidelines are different from the long read to the short read sequence. Yeah, it's a very good question and very insightful about the long reads. To cover the genome and have long enough overlaps, you can get away with shallower coverage for long read sequencing. But because you have a higher error rate to get accurate base calls at the end, you need more coverage to go into your consensus model, which we're going to talk about later. So to get the same, say, overlap percentage, you can get a shorter, shallower coverage with long reads, but the trade-off is that you'd have a lower consensus accuracy. So you get the same quality of assembly with less confidence in the read data meeting with both the same amount? Yeah. We usually, for nanopore assembly, I suggest at least 50X, 100X, is it better just because the error rate is so high and the error rate is particularly biased towards difficult sequence motifs? And you need statistical power from many, many reads at each base to get over that, those biases. With PacBio, you can get pretty good assemblies between 25 and 50X. We did an assembly of the Canadian Beaver Genome with 25X through PacBio. There's a point of national pride to do that. And we always get away with a bit lower coverage there. But we also use Illumina data than to correct some of the errors that we weren't able to fix with the PacBio reads alone. For Illumina sequencing, the method that we're going to talk about is based on the Brown graphs, which use k-mers. And you want to sequence really deeply to be able to use long k-mers to get around these repeat problems. So the coverage thing is incredibly, like I could give an entire lecture on just coverage considerations and the different trade-offs. But yeah, it's different between the short and long reads. Mainly the trade-off is between overlap length and accuracy. So the key computational challenge for Illumina sequencing is just making your software and your algorithms computationally efficient enough that it's going to complete the assembly in a reasonable amount of time. So the methods are used for long reads really have an origin of assembling Sanger sequencing data, which we talked about yesterday. So the very first of genomes were essentially assembled by hand by comparing these gel images. You could do that for viral genome. But when larger and larger genomes were sequenced with Sanger, computational or software-based assemblers were developed. And the dominant paradigm was called overlap layout consensus assembly, or OLC. Since short-read sequencing took over, but now long-read sequencing is becoming popular again, OLC-based assembly has seen a resurgence. And the main assemblers for long reads, like PacBio data, are all based on this idea. So OLC assemblers take in your sequencing reads as input. They first find overlaps between reads and construct an overlap graph. They then process that overlap graph to compute a layout of the reads, which is this ordering of the reads along the genome. They then calculate a consensus sequence at the end to overcome this high error rate. And then they output contigs as their output. And a contig here is a stretch of the genome that was assembled into one piece. It's short for a contiguous sequence. So it's a sequence of reads that had all their sequences merged together into some segment of the genome. So I'm going to talk about each one of these stages in turn here. So as I mentioned earlier, we have this unordered set of reads. And we want to figure out relationships between the reads, which reads may have come from the same location of the genome. The way that we do this is we take pairs of reads. We use dynamic programming, which is a way of performing string comparisons. And we look for significant overlaps between the reads. So the overlap has to be at least a certain length, let's say for 1,000 base pair PacBio read. The overlap length might have to be 500 bases with few mismatches or insertions and deletions. So here's an example of a small short pair of reads that overlap with one mismatch in the middle. But you can see the identity between the two reads is fairly high. So when constructing our overlap graph, we'll create a vertex in the graph, which is depicted by one of these circles for each one of our reads. And when we find one of these significant overlaps between a pair of reads, we connect them up with an edge. Now, for early signer sequencing data, where we didn't have that many reads, you maybe have a few thousand reads for your sequencing project, you could just take every pair of reads in your sequence collection, compare them to each other, look for an overlap if they have it, great, put an edge in the graph. When you assemble human genome-sized data sets with overlap-based methods, there's just too many pairs of reads to exhaustively compare all of them. So groups like mine develop ways of very efficiently screening for the pairs of reads, but might actually have an overlap. And the algorithms we use are quite similar to the mapping alignment algorithms that you heard about earlier in the course. So at the end of this, we get an overlap graph. So an overlap graph is just a graph where every read is a vertex. So the reads that we had on the previous slide are a vertex in here. So we had one read GCA, TTA, one read ATT, so on. In each one of those is a read, and those are the vertices of the graph. For all of the reads that had a significant overlap, we've connected them up with an edge here. Now, if the assembler's task to find a path or a walk through this graph, so the path that visits each one of these nodes that reconstructs the original genome sequence. Now, just looking at this graph, it's a little bit complicated. We couldn't tell exactly what the genome sequence is just by looking at the structure of the graph. So the assembler has to work a little bit harder and try to figure out what the true path through the graph is that reconstructs the genome from all the possible paths that you could take through this graph. So that's the job of the second stage of the assembler, which is called the layout stage, which is going to bundle stretches of the overlap graph into these contiguous sequences or contigs. So I'm going to turn to an example of reconstructing a fragment from a song. The fragment is to everything, turn, turn, turn. There is a season. And the reason we've selected this to demonstrate assemblies, there's a repeat in here. This word turn is present three times. Now, if we fragment this sentence into a lot of different copies with about five character words and construct an overlap graph from those words, it looks like this. It's pretty nasty. We don't really see what the reconstruction is by walking through this graph. So the assembler is going to do is it's going to examine the graph and try to figure out whether some of all of these edges in the graph are necessary. And overlapping layout consensus assembly is based on the idea that a lot of these edges in the graph are redundant in that they'll spell the same sentence as another path through the graph. So as an example, we have a series of blue edges here that go from this node to ever and then o every to every. And the sequence spelled by this path is the exact same as this sequence spelled by this path that bypasses this middle vertex. So in assembly language, we say that this edge can be transitively inferred from the other edges. There's a green one. And therefore, its presence is redundant in the graph. So what the assembler does is removes all these transitively inferrable edges, starting from edges that bypass a single vertex. So edges that have this pattern that goes from here all the way over and skips some middle vertex are going to be eliminated from the graph. So let's do that now. We get a graph that's much more simple in structure after doing that transitive reduction. Now if we take that one step further and we eliminate edges that skip two vertices, so these type of transitive edges, we again get a graph that's even simpler. And now we have these segments in our graph that are unbranched chains where there's no ambiguity. The assembler then does is builds contigs from these unbranched chains in the graph. So the first contig would be to everything, turn, and then the second contig over here is turn, there's a season, and then this structure here is an unresolvable repeat as we don't know how many times we should put the word turn into our output sentence. So the assembler would stop at that unresolved repeat and just output these two contigs as the assembly. We've having assembled the full thing but we've done a pretty good job. We've gone all the way up to where we had this repeated unit where we couldn't resolve how many copies of the repeat there are. The final step of overlap layout consensus assembly is picking the most likely nucleotide sequence for each contig. So we're using overlap layout consensus assembly for noisy long reads like Pac-Bio and Oxford Nanopore and we need to find, we need to develop an algorithm that will eliminate the errors in the sequencing reads. The way that we do that is we make what's called a multiple alignment where we take every read that makes up one of our contigs and we line up the bases so that the first base of every read is lined up, then the second base of every read lined up and so on. And then we walk from left to right and pick the most frequent base at each one of these columns. And that's what we call the consensus or the majority base at that position. So this first column is completely unambiguous. There's five T's here. This one's unambiguous, it's five A's, five G's. This one, there was a sequencing error where there was a deletion at this read. So we have four A's, one deletion. So the consensus nucleotide here is A. Let's keep walking along. Here we had four C's, one T, the consensus is a C. Here we had four C's, one gap. Four G's, one C. And over here we had four gaps and one A. So we infer that this A here is an erroneous insertion of an A in this read and we'd output the consensus as a gap character here which then would be removed. So we're just walking along the sequence taking the most frequent base at every position. Now this is how old Sanger sequencing consensus algorithms worked for the very noisy PAC-BIO and Oxford Nanopore data. We use more sophisticated methods which build generative probabilistic models of the underlying raw data, whether it's being these current traces from Oxford Nanopore data or these light pulses in PAC-BIO data and then we infer what the true sequence is using these generative probabilistic models which improve accuracy quite a lot but are very, very expensive to run. Okay, so overlap layout consensus assembly was developed for Sanger sequencing. When we first got Illumina sequencing the natural thing to do was take our old OLC assemblers and try to run them on Illumina data. Unfortunately this profoundly failed because the reads were just too short. The very first Illumina reads and it was still the Selexa company when I got involved that I saw were about 27 base pairs in length. If you think about trying to calculate an overlap between 27 base pair reads you're looking at an overlap of about 18, 19, maybe 20 bases. This is, there's very many repeated 20-mers in the human genome and any of the reads that cross over these 20-mers are going to have edges between them which are just spurious edges between different copies of the repeat. So if you try to construct an overlap graph of 27 base pair reads for a human genome you'd have this graph that has billions and billions probably hundreds of billions of edges, billions of vertices, it wouldn't fit into memory, your assembler would crash, and you'd have a very bad time. So what people developed were methods that were overlap free. They didn't want to have to compute pairwise overlaps between Illumina reads. So the field settled on a technique which is called the Brown graph based assembly which uses short camers. Prior to building the assembly graph, a requirement of doing the Brown graph based assembly is doing error correction on the reads. So rather than tolerating sequencing errors by allowing inexact overlaps, we're going to pre-process the reads first to find where the errors might be and then correct them to the true genomic base and then that makes our assembly task a lot easier later on. I'm going to come back to this figure later. It shows the error rate for six different data sets, Illumina data sets, and it's just here to show you what the error profile of Illumina reads looks like, where the error rate increases from the five prime to the three prime and up to around a few percent at the very last base. Now error correction is one of the major problems with short read assembly and people have worked very hard to develop computationally efficient methods to error correct Illumina reads. These are all based on counting the number of times camers or windows of length K occur across our entire data set. So to walk you through an example, let's consider a read that has a single error. Let's say this C was miscalled by the base caller. The way the error corrector is going to work is it's going to take a camer length, let's say 20, count the number of times the first 20 error in the read occurred across your entire data set and count the number of times the second, third, fourth, all the way to the last camer in your read and you're going to compare the counts as you go across the length of the read. Now the camers that don't contain sequencing errors that are true genomic sequence, they should be present in very high copy number depending on how much sequencing depth you acquired. So if you have 30 X sequencing coverage and you have a very low error rate, you should have around 30 camers that contain that particular sequence. Now if you have a sequencing error, the sequencing errors are quite rare, it's going to flip a base in true genomic sequence to something that's never been seen before. So the count, the number of times that camer seen across your entire read set should be very low. It should probably only be one, maybe seen a couple of times if it's a recurrent sequencing error. So the idea here is that we can use this camer count as a proxy for the number of times these bases are seen across our entire data set and we're going to switch the ones that are low frequency to sequences that are high frequency to fix errors. So that's said down here, we're going to look for rare camers, camers that are only seen once or twice across our read and then flip them to correct them to common camers to make our corrections. Now the benefit of doing it this way is that camer-based error correction is incredibly fast and memory efficient. You can error correct an aluminum data set for human genome in a few hours using one of the state of ER programs like BFC, whereas if you try to calculate overlaps between aluminum reads that allowed mismatches, it would take orders of magnitude longer and it wouldn't be practical for very large data sets. Okay, so once we've performed our error correction step, we then want to build this de Brown graph and use it to extract quantities. So the de Brown graph is also based on camers and the idea here is that we're going to break our reads into shorter fragments of a uniform length, which would be called K, and then we're going to construct a graph of the camer relationships shown in the reads. So here's an example, we have five reads here, the first one's C, C, G, T, T, A. We're going to take the first four base pair sub-sequence, which is C, C, G, T, and we're going to put that camer into our de Brown graph down here. We're then going to take the second camer in this read, C, G, T, T, we're going to put it into our graph here. And now because the camer C, C, G, T is followed by C, G, T, T in some read, we link them up with an edge. So this is trying to get across the same idea of overlap assembly, where the overlaps represent sequences that might have come being adjacent in our original genome. These edges between camers are representing camers that might be adjacent in our original genome. So if we do this process, so we just keep extracting all the camers from these reads, adding them into the graph as vertices and linking them up by edges, we end up with this graph here. Now this graph is fairly simple in structure, but it does have one branching point because of this camer C, G, T, T is repeated in our genome. So it's followed by G, T, T, A at one position and G, T, T, C at another position. And because this graph is simple, there is a unique reconstruction of the genome where we just walk from here down through this lower branch, back around, visit this vertex a second time and then go up here. And that's the assembly of this little simulation genome. But the nice idea of this Brown graph based assembly is that all you're doing is taking camers from your reads, these fixed length strings and linking up adjacent camers. So this graph can be constructed in linear time in the size of your input data set. And it can be very efficiently implemented using things like hash tables, which is what allowed Illumina sequencing reads to be assembled using this technique. And there's been a tremendous amount of work about building faster and more memory efficient Brown graph based assemblers. And that's actually what I worked on for my PhD. Right, so after we've constructed our graph, we need to do some post-processing of the graph to get rid of any sort of artifacts that we found in our sequences. So the main artifacts are residual sequencing errors that our error correction algorithm wasn't able to remove. So what happens is if we construct a Brown graph, let's say these three reads, if there's an error at the end of one of the reads, it causes these spurs off the graph where there is some camers that are, that diverge from the graph but don't really go anywhere. They stop at some position. So we have a couple camers, a couple of nodes here from read two, a couple of nodes here from read three. And we call these tips or spurs off of the graph. Now the reason that they just branch off and don't go anywhere, it's because the errors tend to be random, unique and at the end of reads. So there's no camers that contain this A base in the first position of the camer. So you don't have these as well connected things that go back into the graph. They're just these little tips that don't really go anywhere. If you're sequencing a diploid genome and you have heterozygous SNPs, that can cause what we call bubbles in the graph, which I divergences in the structure. So if you imagine all of the camers for this allele where there's this heterozygous CG SNP here, all of the camers before the SNP and all of the camers after the SNP are common between the two alleles. And that gives rise to this common gray structure here. Then the camers that cover one of the two alleles diverge, causing the split where one path represents allele one, one path represents allele two. And then they come back together once the divergent base has worked its way out of the camer back into this common sequence. So these are two very common structures that you find in de Brown assembly graphs and getting rid of them is what allows a de Brown graph assembler to construct very long contigs from short reads. So here's a cartoon of how these graph cleaning steps improve our de Brown graph. So let's say this is our input graph here. It's quite messy. It's not really clear what the genome sequence is. We'll first make a pass by identifying all of the one side connected vertices in the de Brown graph. These are nodes that only have an edge in one direction not coming out. We'll then walk those edges back until they rejoin the main part of the graph. When they do, we'll annotate them as being a tip or a spur and then we'll get rid of them, giving us a much cleaner graph. We'll then walk through the graph looking for these divergent structures where there's a branch point that then comes back together. We then select one of the two alleles to represent the sequence in the genome, remove the other one, giving us a much cleaner structure that looks like this. Now this is looking a bit like our overlap layout consensus graph where we have these long unbranched segments of the genome that can be compacted together into context. And that's exactly what the Brown graph assembler does. You would select it based on the frequency. You usually, what you'll usually do is you'll calculate the camber coverage along each branch and pick the one with higher coverage. Yes. It's an arbitrary decision. Usually it should be 50-50 the ratio. It doesn't really matter. The assembler doesn't care which allele it puts in there. It just wants to put one of the two in there. You can get these bubble structures from sequencing errors that occur right in the middle of a read. And that's why we pick the higher frequency one because if you have 30 coverage on one half, one coverage on the other, the one coverage is probably sequencing error and you want to get rid of that one. Okay, so the assembler is then going to take this much cleaned up graph, compact the nodes together into context. And that's just merging all of these unbranched segments into the final genome assembly. So it's going to ignore the places where the graph branches and just compact everything else together. Okay, so we've heard about paired end reads. The final step of short read assembly is leveraging the paired end information to try to jump over these repeats that stop the counting assembly. So if you have long insert paired end information, you can map your reads back to your contigs and then keep assembling 500 base pairs downstream after the other pair continues. So the first step is to take our contigs that we produced in the last stage, map our paired end reads to these contigs. So we're going to have paired end reads that map internally on the contigs, which are shown in black bars here linked by a line. But we're also going to have overhanging pairs where one half of the pair maps to the end of the contig and the other half of the pair maps the end of some other contig. So we can infer that in the genome, this contig might be followed by this contig here. Likewise, this contig might be followed by this contig. Now we can formalize this idea by constructing a scaffold graph where we can, we put a contig as a vertex in the graph link up a pair of contigs with an edge if there's pairs supporting those two contigs as being linked together. And then we post-process that scaffold graph to construct our scaffolds, which are just an ordering of our contigs with gaps in between, not more the gaps or the sequences that we can't resolve. Either they're too repetitive or we don't have enough coverage there. So our scaffolds contain gaps. We fill in the sequence between the contigs with N, the N big U.S. nucleotide code. And some assemblers take the approach where they'll try to use a local assembly to fill in the gaps. So they'll do a less astringent assembly of the reads that have pairs in this region to try to fill in that more repetitive sequence. There's some programs out there that will take in other sequencing data like low coverage pack bio data to try to fill in the gaps between your scaffolds as well. So what can you expect the output of an assembler to give you? Well, there's quite a lot depending on what the size of the genome you try to assemble and the type of sequencing data that you had. So for bacterial genomes, short read assembly will give you hundreds of contigs with an average size of between, say 10,000 and 100,000 bases. With long reads like pack bio or nanopore, it's typical to have the genome in only a handful of contigs, maybe one to five. With most genomes, I'd say being able to be completely assembled into one piece.  For large genomes, with short reads, your contact sizes, you can expect to be around 10,000 bases. For long reads, they'll be around a mega base in size. Long read data, as I mentioned yesterday is much more expensive. So the right question or the right technology to use depends on your question, what you're interested in getting out of your genome assembly and also the budget, how much money you can put towards the assembly. I typically recommend that people use long reads if they're assembling very large genomes. If they want to make a new reference genome or some crop that they're interested in, try to use long reads. It'll give you much higher quality reference if you're able to pay for it. Okay, I'm gonna switch gears now. Is there any questions at this point about sort of the theory on assembly? Can you reverse double-stranded if you're referred to double-stranded in here or in a single direction? Yeah, this is one of these ugly bits of implementing a genome assembler that are hard to deal with. Usually with this vertex that has the Kamer sequence is both the Kamer and its reverse complement. Because as you know by asking this question, like every sequencing read could have come from either strand, so we want to be able to incorporate that information. The other, some assemblers will have slightly different representations while they'll have sort of these mirrored graphs where there's one set of Kammers for one orientation, one set of Kammers for the other, but that gets pretty complicated to implement. So usually assemblers will just represent them both in the same vertex. Yeah, so we're, it's a very good question. Structure variation I think is the best application right now. There are other types of variation that are very difficult to call with the luminous sequencing. Indel calling, even calling short insertions and deletions of a few bases is notoriously difficult, especially for somatic mutations. There's a lot of, if you sequence a genome, let's say my genome, and you compared it to the reference genome, you'd find something like five megabases of sequence that's not present in the reference at all. Obviously if you're not doing de novo assembly, you have no information of the function of that sequence. So it's a combination of structure variation, short insertions and deletions, and novel sequence that gives you the benefit of assembly for human genomes. Okay, so the last part of the talk, I'm going to discuss some of the difficulties of performing short read assembly and how we can make predictions about how hard or easy a given assembly will be just from your set of sequencing data. So short read assembly algorithms were incredibly active area of research between about 2010 to 2015. And there were a lot of community projects to benchmark how well short read assembly software worked. And one of them was called the Assemblathon and Assemblathon two, which sequenced the genome of three species. One was a boa constrictor, one was Lake Malawi sicklet of fish, and one was a parakeet. They didn't know the genomes of these sequences. They released the read sets for these three genomes publicly. Everybody who was interested in doing assembly would download the data, assembled it, submitted it to the organizers, and they benchmarked how well the individual software performed. My group took part in that, along with about probably a dozen other groups around the world. And then the results were somewhat disconcerting as the results were very variable. Some assemblers that did very well, say on the snake genome, didn't do very well on the Lake Malawi sicklet. Some genomes just performed much, much better for all assemblers than other genomes. So this got me thinking about what makes a given assembly difficult and how can we help you guys, the users, figure out once we've sequenced something, is this gonna be an easy genome to assemblers? It's gonna be very hard genome to assembler. So I spent about a year working on a program called PreQC, which will take a set of sequencing reads and tell you whether you're in for a hard time during your assembly project. I'm sorry for that. Okay, so I sat down, I made a list of what features of a genome make assembly difficult. Something I've hammered on about for the last 40 minutes is repetitive sequence. This is an obvious one. High header is Igosity. If you have very high rate of headers, I guess snips and indels of your genome, you're gonna have a lot of these bubble structures which can confuse the assembler. If you didn't sequence enough, maybe you didn't have an accurate estimate of your genome size and you only have 15 X sequencing coverage, this is gonna make the assemblers job a lot more difficult. If you have very biased sequencing coverage, and by that I mean your sequencing coverage is very poor for low or high GC content sequences that causes a lot of problems. Classic example is the parasite that causes malaria, plasmodium, topsybarum, which has 80% AT. This is awful for aluminum sequencing. It's very, very difficult to get uniform good coverage of plasmodium for aluminum, but because it's so important biologically, people really, really want to sequence and assemble the genome. So the assemblers have to try to account for this, but is one of the factors that makes assembly more difficult. High error rate in your reads, that one's a bit obvious. If you have more errors, it's gonna be more difficult to assemble. If your reads are chimeric, where they contain a non-adjacent biological sequence, this confuses the assembler. If you have a lot of sequencing adapters in your reads, if your sequencing center contaminated the sample with something else, or if you simply can't get enough DNA from your organism, so you've taken multiple individuals from the population, you've sequenced them, now you've increased the amount of variation in that sample that makes the assembler's job a lot more difficult as well. So the way this pre-QC program works is it, it's going to look at the structure of the assembly graph and try to label each one of the branches it's seen with the cause of that branch, whether it's caused by sequencing error, whether it's caused by a heterozygous SNP, or whether it's caused by a repeat. And the way that it's going to do that is it's gonna go back to these methods that we talked about for error correction, where it's going to look at how many times each one of these camers occurs across our sequencing dataset. Now the first output of this program, and you're gonna have a look at these reports in the lab practical coming up next, is a histogram of the camer, in this case, 51 mer count distribution. Now this is an extremely clean example, and this is what we hope to see when we run a genome assembly. We have this nice peak around camer count of 30, which is roughly corresponding to 30x coverage. We have a peak over here of camers that are only seen a single time. These are camers that contain sequencing errors. And you see there's a little shoulder here, which are camers that are half the coverage of the main peak, which are camers that cover heterozygous SNPs, those ones that cause bubbles in the graph. Now, if we look at this, I'm immediately horrified when I look at this, it's a bimodal distribution. Now the reason it's bimodal, this is from an oyster genome, is that the heterozygous SNP rate in this oyster is roughly about 1%. There's a SNP every 100 bases. So what happens is you get this huge peak of camers at half coverage, which correspond to camers covering heterozygous SNPs. These are homozygous camers, these are heterozygous camers. Now no assembler, very few assemblers are designed to deal with this level of heterozygosity. And the authors of the oyster genome paper actually started with a short read assembly approach. They saw that this was a heterozygosity and they gave up and used long reads instead. So if you see something like this, it's gonna be a very difficult genome assembly. So going one step further, within PreQC we have a statistical model which will classify each one of these branches. Now I'm not gonna go into the details of how the statistical model works. It's essentially measuring the coverage between the three vertices that are caused by this branch and comparing the coverage of these ones, which are labeled CA and CB. So the idea here is that if it's a sequencing error, we expect one of the branches to have much better coverage than the other. If it's a heterozygous SNP, we expect the branches to have roughly balanced coverage. If it's a sequencing repeat, we expect the branches to have coverage which is corresponding to their copy number in the genome. So the output of this that the user can see is a prediction of how often the graph branches due to heterozygous SNPs. And this is the plot I'm showing here. Now this oyster genome that I just not told you was horrible to assemble has a heterozygous SNP branch prediction of about one in a hundred, which matches what we know. The human genome is about one in a thousand shown in blue here. The negative control here is haploid yeast genome, which has a heterozygous branch rate of about one and I think 30,000 bases, which is the false positive prediction rate of this approach. So these are the different assemblathon genomes are listed here. This is the cichlid, fish in green, the bow constrictor in red, pear peat in purple. And their difficulty of assembly roughly corresponds to heterozygosity shown here. Now we can also predict how often branches occur in the assembly graph due to repeats. This largely tracks our expectation of which assembly, which genomes are gonna be most difficult to assemble. The human genome, which is known to be very repetitive is up here with the highest repeat induced branch rate with the oyster genome. The yeast genome, which is very small and easy to assemble is shown down here. So by plotting where your genome lies on the spectrum from hard to assemble to easy to assemble, it gives you some idea of what kind of assembly you're looking at. This program will also predict the size of the genome. So it'll just take your sequencing read, calculate coverage statistics based on these camers and they make a prediction of what the size of the genome is. So if you wanna check that matches what the lab told you you can. It'll also do more basic quality control like looking at the mean quality score of each read across the sequencing read. So again, looking the same six data sets here. We see that the snake genome, the bull constrictor, which was actually sequenced by Lumina has the highest quality data across the whole read where the Lake Malawi Cichlid is the lowest quality data set here. You see a fairly steep drop off of the quality scores towards the three prime end of the read. I showed you this image earlier which is a per position error rate. This program will estimate where the errors in the sequencing reads are and plot the error rate as a function of the read length. Again, giving you an indication of how clean your data is. And we'll also try to get at this GC bias and whether there's GC bias in your data set. So this is the Lake Malawi Cichlid again and it's a 2D histogram where each bin is the camer coverage for camers with a particular GC content. And we see that this is a fairly clean data set where there's not a strong dependency between camer coverage and GC content. If we look at a yeast data set instead, we see there's a bit of a dependency between GC content and camer coverage with these higher GC camers having a somewhat low coverage. The oyster genome again, we see two peaks here because of this heterozygosity versus homozygosity camer problem. The program will also infer the fragment size histogram just like we saw when we can map to a reference genome but this just does it by looking at where are the pairs link up in your assembly graph and it'll automatically output these histograms for you. And finally, it will actually do a simulated assembly. It doesn't do a full assembly because that would take too long but it'll simulate a genome assembly process, output the length of the contigs that you'd expect to get for a particular camer size which will tell you directly how easy or how difficult your genome assembly is going to be. So the yeast data set which I've said is quite easy. You get the longest contigs across a very wide range of camers. This oyster data set which I'm using to demonstrate how difficult things are, you get very short contigs for pretty much all camer values. So in the practical session, you're gonna look at a report for the data sets we're gonna use. You're not gonna generate the report on your own cause it takes a little bit too long to generate for the practical session but the commands used to generate the report are shown here. They're also shown in the text file for the lab. If you wanna read the paper, it's up on archive and the codes available as well. I'll wrap up now. So this was just an overview of how assemblers work, a little bit of theory and more detail on how short and long read assembly pipelines work. We need different approaches for different types of data. My standing recommendation is use long reads if you can and then I just talked to a different factors that determine whether an assembly is gonna be difficult or easy. Here for the rest of the afternoon, so please feel free to ask questions now or during the lab practical. If you think of something after today, feel free to email me. I'm always happy to help people with assemblies. So do you have any questions at this point? In the back? Yeah. Yeah, that's a good question. So the question was about optical mapping. So this is a technology where you stretch out very long fragments of DNA and then you can figure out where little markers are on the DNA. So you can't sequence the entire piece, but you can figure out certain sub-sequences. A famous one is called BioNano that's used for optical mapping and that's really useful for building very long scaffolds from your genome assembly. So if you have an existing assembly with 100 kb contigs, you can use an optical map to order and orientate those contigs along the optical map to give you much, much longer scaffolds. This is becoming a really popular way of generating complete and nearly finished chromosome arm level assemblies. And we're starting to see a lot of that in human assembly as well. Since you asked that, I'm gonna use this to talk with different technologies as well, but I didn't get a chance to mention. One that you might hear about is 10x genomics. So 10x genomics is similar to the molecular technology. Matthew was just talking about where it fragments very large pieces of DNA around 100 kb and then it barcodes within droplets that all of the reeds came from the same source 100 kb molecule. And this can be used for scaffolding. It can be used for haplotype phasing as well. And that's becoming pretty popular in assembly too. All right, any more questions?