Video 4-2: De-novo sequence assembly, Overlap Graphs

0:03 Let me in the next section show you a formalization of the problem where we first ignore some of the problems and we'll come back to uh them a little bit at the end and you'll see even the resulting problem is still kind of juicy enough hard enough to solve. Um to make things uh easier, I'm I'm making an assumption that the uh fragments of the genome I get are covering every possible starting position. Uh all of this um module will will use K mirrors just uh because the bioinformatics people tend to use this. It's just a length K substring. But I think because they got rid got annoyed by saying length k substring a million times they say it's a kr but it's nothing fancy.

0:56 Then if we're given um a text say our genome and some length for these k input to our problem will be this. The k composition of a text is just all these contiguous length k substrings that the text has. So every possible starting position you take the substring of length k all the k in the string. Now um as indicated with these double braces in general that's a multi- set right you can have repeated parts and that would mean that some kars might occur more than once.

1:36 So if you if you're given a text it's of course easy to produce this kir composition just listing all the the substrings. The problem that is uh that we're trying to solve is of course the reverse problem. Okay, here's an example just to make sure. Uh here I've sorted them alphabetically to make it a little less obvious or [snorts] to show the the duplicates more clearly. There's a stretch of uh Thank you.

2:12 there's a stretch of four G's. So, I'm going to have the first three and the second three. That's why G GGG occurs twice and so on and so forth. Uh life gets interesting when you try to reverse. Um someone might promise you and that's our assumption that we get a multi-et of these cursors that comes from some specific text and then we're trying to reconstruct that text. This is easier than the biological motivation problem for several reasons. U one we don't have sequencing errors. Uh but two also the assumption that we have a kr from every possible starting position and exactly once will help us uh a lot in kind of removing some um ambiguity. I'll I'll come back a bit later to motivate parts of why this is not completely hopeless even in the data from applications. Um but for now let's let's ignore this and just take all the possible klen substrings exactly once. Okay.

3:17 All right. Let's look at some examples. So here's uh a composition a three composition of some text. I'm going to give you a hint. The number of kmers is five. So if I want five things in here n I mean there's zero up to n minus k and n minus k is included. So the number of kmers I should have is always n minus k + one. So if k is three I can work out that from five km if this is five what's my n the other way around >> [laughter] >> Okay, people are puzzled. Um, can you figure out what molecule this is? Where what's the text that produced this? It's again sorted alphabetic, so don't interpret the order in any way. T A >> T A T >> G T T T T T T T T T T T T T T T T T T T T T G T. There's a letter missing. Hold on.

4:53 >> One more word. >> Seven should be. >> Yeah. >> Did we use everything exactly once? This one's there. >> Yeah, seems to match. Uh, do you want to describe how you approach this or it's a small enough example you just try randomly puzzling?

5:29 >> Say it again. corresponds to a >> there's only one double A >> that has to be in correspondence. That's right. >> There's no >> That's right. So, this has to be the start because there's nothing that matches on the beginning. And I think double T signals this is the end. and then kind of greedily just assembling the thing works. Okay, so easy problem. Um, this is just the uh the summary of uh of what you also produced. Um, and here's the solution again. Now, let's do a slightly bigger one. And it would be uh kind of more more revealing if you had a bit more time to puzzle with this. And if this was kindergarten, I would have cut out the things and we could puzzle uh exactly, right? But you already may know where this is going. But let's let's just try the same strategy, right? Um you can work out that maybe TAA is a good starting point because there's nothing that ends with TA. Is that right?

6:45 It looks like it. So there's nothing that ends with TA. So, we found our starting uh k three mer. Good. Now, I have to find something that starts with aa. Okay, also just one option. And then something that starts with a. No, because they're alphabetic. There's a whole bunch of things starting with a. Okay.

7:13 Uh so far there was no choice really. But for the next step, um, so here there's several things that start with at, but they're duplicates. Uh, but for the next one, the TG, you have options, uh, three options. And now it's not clear which one we should take. And it's also clear that not all three will be correct. [laughter] And so if we say for example we pick this one then you see you can continue for one more step but then you're you're uh stuck with the end TT. There's nothing that starts with TT. So while this is the beginning this has to be the end. It's coincidence that they're next to each other. Uh but here we're done. We can't continue. But we haven't used nearly all of the camer. So this can't be the original text. So somehow this choice was wrong. So we could go back and say that was the wrong choice. Let's take another turn in this maze and then uh let's say we do that. So at this point after we now choose the TGC, not the T. Maybe that's the right choice.

8:25 And then you you continue uh and again you arrive at the end. And now it looks better. But if you watch closely, we're still one nucleotide too short. There's another one where we could have um maybe maybe you see which one's missing. It's actually one >> the G >> the triple G. And it's kind of clear that it has to be something like this because I have to be able to insert this one extra thing without disrupting the whole thing, right? This is almost just possible with something self self- similar. Anyways, so here you could have done the GGG first and then you're you're happy.

9:06 Um, now of course then that's that's a solution. Now in general you may already see it could be tricky to make the right choices. Um, we need to somehow globally look at this.

9:23 Okay, but at least the puzzle seems a little more manageable with this assumption that you have this full camera composition. Now we would not like to systematically try not like to keep trying dead ends. We would have like a systematic algorithm. So what could we do? Uh it's a small group. Maybe you want to make some suggestions out of the blue. What would be your gut feeling would work? And if you've seen it already like okay forget it. But there similar to the first reading, maybe you can start with the first like the start and the end. >> That's right. Starting um beginning and end is is always a good idea. Now in general is it clear that the beginning and end is is uniquely recognizable? Maybe not right there's no guarantee that the beginning one can't also occur somewhere in the middle maybe as a duplicate. Uh like for sake of argument say the text is just all A's.

10:35 All the cameras are all A's. Now this is easy because they're also the same. One of them will be the starting point. Uh but I guess you can tweak the example. But still you're right. if there's a unique starting and end point that we should use. Um, sometimes there isn't.

10:52 The other piece that we used repeatedly was we have one kr. Now what are possible next steps? They have to overlap apart from the first and last symbol. So that looks like an edge, right? Uh I can connect two uh krs by an edge if they are overlapping in the right way. And then I have edges. So maybe something of a graph is is a good idea to represent the data. And let's maybe just try that before we think about the problem. Um I just wanted to throw that one in. Uh the kind of puzzle we were doing. The tricky bit here comes from having choice where several things match in the same way. And that comes essentially from having this substring repeated in the original text. And uh the same is true if you do ordinary puzzles, but puzzles where you don't have the shape of the pieces telling you much. Um then this is kind of easy if the pieces are all uniquely if if there's only two ways two two pieces that match across an edge. Uh if you have patterns like in this in this puzzle where there's many patterns that that occur many times, then it seems much harder.

12:12 uh so hard indeed that apart from the creator of the puzzle nobody has ever found the solution to this yet and there was a um a substantial prize money uh attached to this um and essentially people gave up at some point I don't know is if the competition is still open the puzzle still exists and the inventor claims there is a solution [laughter] let's suppose we believe that uh so these puzzles with repetitions can get very very hard. Okay, so maybe uh we're uh we should we should manage our expectations here.

12:55 Let's try this idea of edges and graphs and see where that leads us. Um I'll call it the overlap graph. Uh for the obvious reason, let's formally this define again what I what I said already before informally. Uh you're given such a k composition. Now this you can actually define whether or not there is a single string that this comes from. Let's just say some multi set of kurs. Uh then we define um a graph where the vertices are essentially these reads or these these kr. I gave them lowercase letters here so that uh we have a separate vertex for all the kamers even if they're duplicates. Okay. So I'm always going to have as many vertices in this graph as there are entries in the input. But there might be several that have the same KR associated with them. Is that clear the distinction?

13:49 So each of these vertices we we will label them with the KR and so uh there will be several vertices potentially with the same label but I want them as vertices to be distinct. And then we have an edge. Uh this is a directed graph because again like if you have some cam like this uh the orientation of the edge should go from from this guy to that guy.

14:20 It's a directed relation because there's an ordering. So there's a directed edge from RA I to RJ. Exactly. In this case, the the last k minus one letters of RA I match the first K minus one letters of RJ. It's just formalized what I just said. And uh here's an example. Um again, this is taken from the book because they drew it so nicely with colors that um I felt it's a it's not much one in in me redoing the drawing. So here's uh an example text where this comes from the first step. This is just the backbone. This is the edges that are obviously there from what we have in the text. Now the graph we defined of course will have more edges because there's some examples uh for example this one starts with a this one ends with with a so we should have an edge like this as well right and there's there's a bunch of others uh okay this edge is drawn down here but there's a bunch of other edges that come from this same overlap Now if I have the graph given like this it's obvious how I can read off the original text but that's not really what it's looks like. You should rather think of the ordering of the vertices being uninformative say alphabetic and then uh is a bit more messy but as a graph theoretic notion what are we looking for here? what is uh corresponding to this this chain of letters where if I read them from left to right for the first one I write the entire three letters but for the next ones I always just read the last letter and add it if I do this here along this chain then I get the original text back in graph theoretic terms what what would I need from this graph >> yeah so along first of all a path Right?

16:24 I have to follow edges to construct something that nicely overlaps. And I want a long path, essentially a maximally long path. I want a path that contains every single vertex, right? Because I want every single kr to be used in the construction of the text. So these things are called Hamiltonian paths. Uh so in this overlap graph in one way that's good news. If something has a name you can Google the algorithms for it. Uh it's also bad news because we already know that this is a hard problem. Uh so we uh kind of reduced our problem if you want to finding Hamiltonian paths in this overlap graph. This should be go and here's an example in the non nonlinear arrangement.

17:30 Um, and I think a nice nice if if you follow through the edges, you'll see that this is a different text that also matches the same k composition. So even in our perfect world where we assume that our input is a clean k composition of a single text, it can happen that the graph allows several Hamiltonian paths and the problem is not uniquely solvable. We'll have to live with that. Um there's essentially some some limitation of the kind of data we have. Again, this is not so much a concern for practical inputs. The reads tend to be so long that this rarely happens. Okay, so this is little problem result may not be uh unambiguous uh bigger problem. We identified that what we want to solve is an NPcomplete problem. So there's no there's not going to be a blackbox solution.

18:42 Ah, why not? Gi says, uh, the definition of the overlap graph, I mean, no Hamiltonian cycle can ever use this loop, so you might as well leave it out. >> Fair enough. The definition of the graph says I have an edge. >> Okay, just >> is a fair point. Like this self loop will never ever be used. [laughter] uh not in this not in this case where we have a single like duplicate kamers each get a vertex yeah it's never going to be used so again we've ran into a hard problem and uh that even ignores how to compute this graph uh I guess it's clear that this is not an NP hard problem you compute for every pair of krs whether they overlap or not so So it's quadratic in the number of kmers. That's not from complexity theory perspective a bad thing. In terms of the application, it is a bad thing because you have lots of these reads. But okay, we also have to solve the Hamiltonian path problem. So we're uh in double double trouble.