Son presented a very natural approach to fragment assembly. I, on the other hand, will present a very unnatural approach to genome assembly. And we will debate later whose approach is better. The first thing to notice that in fact, there are two Hamiltonian paths in the graph that Son presented. This is the first one and this is the second one. And while Son presented his very natural approach, it's absolutely unclear how to find either of these paths. I will do something different. First, I will slightly modify the graph. Remember, in the Hamiltonian path problem, we put 3-mers into nodes of the graph. In contrary, I will represent every edge of my graph as a 3-mer. See this almost cosmetic difference. It's not clear why do I care so much about this difference at the moment. If we label the edges of the graph, let's also try to label nodes of the graph. And how should we label the nodes of the edge TAA? Let's label the starting node by the prefix of TAA. And let's label the ending node by the suffix of TAA. As a result we will have this graph, shown below here, it's a path currently not a graph yet. And this is our starting point, this path labeled by 3-mers, where edges are labeled by 3-mers and nodes are labeled by 2-mers. And now we'll do something really strange with this graph. Let's glue identically labeled nodes in the graph. In this graph, we have three nodes labeled AT. Let's glue them together. Let's bring two of them next to each other. And next, let's bring three of them next to each other. Let's bring them even closer to each other. And finally, they will glue in a single vertex as shown at this slide. Now, we haven't done yet, because there are more identically labeled nodes on this graph. Here it is, three nodes labeled TG. Let's bring them closer together. And finally, they will be glued into the same node. Are we done? Not yet, there are two more nodes that identically labeled. Those are two nodes GG. Bring them closer together and glue them in a single node. The result is the graph that we will be study in this lecture. It is called De Bruijn Graph of a string. And the question that we first should ask, how does this graph can help us to find the genome. Where is the genome hiding in this graph? It isn't hiding at all. Because we started from the genome to construct this graph. We just made some operations to make the genome somewhat illusive in this graph, but it is there. It was always there. Let's take a look. What corresponds to the genome in this graph? Of course, it is the part that we were gluing, that goes like this. This, this, this, and this path along the graph is slowly but surely builds the string, the original string that was used. Let's continue doing this. Continue doing this. Well, what are we trying to do? Well, since we need to explain all 3-mers in the graph, what we are trying to do is to find a path in the graph that visits every edge 3-mer exactly once. Let's continue. And after we finish this, we construct actually something that we call an Eulerian path. The path that visits every edge in the graph exactly once. And now we have eulerian path problem that is attributed to Euler, of course. Find an Eulerian path in the graph which is a path visiting every node exactly once. And as you remember, Euler solved this problem by trying to solve the Seven Bridges of Konigsberg problem. This is an ancient map of Konigsberg. And the orange dot on this map is exactly where I took you to the field-trip. Now what Euler did, he constructed a graph by connecting four nodes in the graph, each node corresponds to a district of the city. By an edge, if there is a corresponding bridge between these two districts in the city. It is an undirected graph in difference from directed graphs that we mainly consider in this lesson but it doesn't matter that much. The differences between directed and undirected graphs are small, and we will be mainly working with these directed graphs. And we'll let you a chance to implement whatever other problems for for undirected graph. so we now have two problems. Eulerian path problem and Hamiltonian path problem. Do you find many differences here? And the question arises, why did I waste your time reformulating the problems that Son already presented? What was my goal? And in the next segment, I'll give the answer to this question