[MUSIC] All right, so now that we know what Hamiltonian graphs and Eulerian graphs are, we get to see how they are used in practice to really solve a very important problem. Now to set the stage, we're really happy to have colleagues, from UC San Diego, talking about their work in genome assembly. And so I'll let Pavel take it from here. >> As we speak, there are 1000s of genome sequencing projects that is being conducted all over the world. Personal medicine and personalized genomics have important implication in medicine. And in 2010, Nicholas Volker has become the poster child of personalized genomics. His life was saved by genome sequencing. We expect that very soon the cost of sequencing the human genome will fall under $1,000 mark. To accomplish this genomic revolution, we need to develop algorithmic techniques for sequencing genomes. >> So, this is the overall picture of the genome sequencing and assembly. You have multiple copies of the genome. The sequencing machine generate reads, and the task of the genome assembly is to read from this read to reconstruct the original genome. Now, we are ready to put the genome assembly problem into the language of computer scientists. >> Now, as Shawn said, we need to translate the problem of genome assembly into the language of computer science, and here's where a lot of magic and creativity needs to happen, because when we do this translation we have lots of options. And in particular when we're thinking about translating some big problem into graphs, we need to choose what are the vertices and what are the edges. Now the classical way of translating genome assembly to the language of graph theory is to take those reads, those little pieces of the genome that we read off, and put them are vertex labels. And then what we want to do is look for ways that those vertex labels overlap. And so we have an edge between two vertices if we have vertices whose labels overlap. And then what we want to do in order to reconstruct the genome is to find a path through this graph that visits every vertex exactly once. Now, we're looking for a path that visits every vertex in a graph exactly once, and that is exactly the Hamiltonian problem. Thing is, though, that when we talked about Hamiltonian problems just two videos ago, we saw that they're intractable. We don't have efficient algorithms for solving the Hamiltonian problem on an arbitrary graph. Now the beautiful, brilliant insight of Pavel and his team was that we could model this situation in a completely different way. We could instead have a different collection of vertices and edges, that I'm not going to get into in too much detail because it gets a little technical, but you could learn about it later and I'll tell you how in a minute. But with this new graph formulation, what ends up being the problem that we're trying to solve is looking for a path through this graph where we visit every edge exactly once. That's an Eulerian path, and Eulerian Paths, well, they are amenable to solutions with efficient algorithms. And so, by reformulating what it is that we're trying to solve, and how we represent the problem at hand, all of a sudden these algorithmic tools that we've developed really help us out and help us solve really hard problems. And so, to wrap up this conversation about translating the genome sequencing problem to graph theory, I'm gonna hand it back to Pavel. >> Let me ask you a question. If you were given the possibility to choose between the Hamiltonian path problem and Eulerian path problem as presented at this slide, what choice would you make? Shawn? >> Well, I would like to solve the Eulerian path problem because the graph on the right looks simpler, and maybe it's easier to find a path that traverse all the edges in the graph. >> Sean just gave a very wrong answer. In real life, this graph will contain millions, if not billions, of edges. And it doesn't matter that one of them contains 2 millions and another contains 1 million of edges. What matter is whether we have efficient algorithms for solving these problems. >> So I hope you're really excited, or as excited as I am about these amazing applications of graph theory to bioinformatics. And if you want to learn more, Pavel and his team have put together an amazing specialization here on Coursera, and we invite you to look into it further.