0:02

We just saw how to create a de Bruijn graph, and

we also learned what an Eulerian walk is.

It's a walk through the graph that goes from node to node and

that crosses each of the edges exactly once.

And we said that this corresponds to a reconstruction of the original genome, and

so it gave us a new algorithm for

reconstructing the sequence of a genome from a collection of sequencing reads.

So let's apply this idea in a couple of scenarios, and

let's see how it works in a couple of more complicated examples.

And we also want to see whether it actually solved the issues that we

had with the shortest common superstring formulation.

For example, the shortest common superstring had a tendency

to overcollapse repeats, so we're going to see if we have the same problem here.

Here's a de Bruijn graph, for a familiar example.

This is the genome that the shortest common superstring had trouble with.

So we collapsed the three copies of the word long into just two copies.

0:59

Well, when we draw the de Bruijn graph for this string, for this genome,

using a camera length of five, and assuming that the sequencer sequences each

camera exactly once, then we end up with the picture that you see here.

We said previously that de Bruijn graphs produced in this way are Eulerian,

so they have an Eulerian walk, and so if we look at this graph we ought to be able

to find a walk through it that reconstructs the original sequence.

And we can.

So here it is.

We start here, and we spell out

a long, long, long time.

So there you go, that's the Eulerian walk through the graph.

1:40

So again, the Eulerian walk did what we said it should.

It gives us the reconstructed genome sequence back again.

But the point is that it, actually in this case, did not overcollapse that repeat.

It did not overcollapse the repeat long_long_long.

It gave us the original sequence back, and that's an improvement over the shortest

common superstring formulation of the problem.

So that's great.

But let's not be lulled into thinking that we've solved all our problems.

So we actually can't escape from the third law of assembly which states that

repetitive portions of the genome make assembly difficult.

And let's see exactly how they make assembly difficult when

we use an algorithm that's based on the de Bruijn graph, like we are here.

2:22

So here's another example, and this time things won't be quite so straightforward.

So the de Bruijn graph that you see on the right is the graph that corresponds to

the genome on the left using a camera length of three, and

as always we're assuming that each camera is given to us exactly once.

And this graph on the right is Eulerian like we said before because there's a way

to walk along the nodes of the graph such that we cross each edge exactly once.

However, there is more than one way to do so,

so there's more than one Eulerian path for this graph.

So one of those ways looks like this.

Let's start in ZA, and we're going to start by going down to AB.

And then we can go up to BE, and then along here,

and then down here and along here, and then down to BY.

And that's one of the Eulerian paths.

The other one goes like this.

We start from ZA, we go to AB, and we start by going down to BC and

going around like this.

Then we go up to BE and go around like this.

Then we go down to BY.

So here are those two walks that we just took,

the series of nodes that we visited along those walks.

3:39

So there's ambiguity.

We haven't escaped the third law of assembly here.

Instead, the way that it manifests itself is, it means that the de Bruijn graph for

repetitive genomes will, in general, have many different Eulerian walks, and only

one of those walks actually corresponds to the original genome sequence.

All the rest of the walks correspond to incorrect reshufflings

of the genome where portions of the genome that occur between repetitive sequences

are going to get shuffled around and put in the wrong order.

4:41

And then we build a de Bruijn graph using a camera length of four, and

then we call a function of the de Bruijn graph class here which is called

eulerianWalk which simply finds the Eulerian walk and

just returns basically a list of all the nodes visited during that walk.

5:12

So, this next line concatenates together the labels of all the nodes visited

over the eulerianWalk, which is a very simple thing to do.

It respects the overlaps between them so

it actually starts by appending the first node label, and

then it appends one more character for each subsequent node visited.

And then it simply prints out the superstring that it's put together.

5:48

So now let's repeat this entire experiment but

using a camera length of three instead of a camera length of four.

And by decreasing the camera length, we're increasing the chance of being

affected by repeats since the smaller k means there's more likely to be

multiple occurrences of any given k-mer in the genome which is going to increase

the chance that we have multiple different Eulerian walks for the same graph.

6:18

our reconstruction of the genome is incorrect, so

it mixes up the order of these words that start with T right here.

All right?

So this is the curse of the repetitive genome which

in the case of the de Bruijn graph it results in a spurious reshuffling

of portions of the genome like you can see here.

6:39

So now back to one other issue that we've been putting off,

our assumption about the sequencing data.

So we've been assuming that the sequencer is kind enough

to give us exactly one read per k-mer, and

without accidentally leaving out any k-mers, or giving us any k-mers twice, or

anything like that, or without sequencing errors, and things like that.

But of course none of these assumptions are actually true in practice.

The sequencer gives us sequencing reads, which are usually going

to be much longer than the value of k that we pick, by the way.

So typical values of k are around 30 to 50 or so, whereas sequencing reads

are usually around 100 to 200 or tp 300 or so bases long.

But of course, the sequencer does make mistakes.

There are sequencing errors.

The coverage is uneven.

It's not necessarily going to give you the desired number of copies of any particular

bit of the genome.

So given this reality,

we can certainly still use our procedure for building the de Bruijn graph.

In other words, we can take each read and chop each of the reads up into k-mers,

and then for each k-mer split it into it's two k minus 1-mers and

add the corresponding nodes and edges to the graph.

We can still do that,

but what we end up with is a graph that's not necessarily Eulerian.

In fact, it'll never be Eulerian in practice.

So, for example, if we have this genome, and

the sequencing reads reported by the sequencer are the three

reads that you can see here, and we're going to use a k-mer length of eight.

So when we chop those reads up into k-mers we get the k-mers that you see down here.

8:14

So we can still build a de Bruijn graph out of these k-mers.

Right? We can build a de bruijn graph out of any

set of k-mers.

Then we can do that, and this is the graph that we get.

And if you look at this hard enough,

you can figure out that this graph is not Eulerian.

There's no Eulerian walk of this graph, but it's almost Eulerian.

I mean, if you go like this, if you go a long, long, long,

time, you'll notice that it was almost Eulerian.

The problem here was right here,

the number of edges going from this node to this node.

So finding Eulerian walks will not necessarily solve the assembly

problem for us.

8:56

Now that doesn't mean what we just investigated was pointless.

So for one thing, it was an instructive example of how repeats make assembly

different no matter what algorithm we use, and we solved two different algorithms in

two different ways that the repeats made the assembly problem difficult.

9:12

But, another reason is because this de Bruijn that graph we studied,

the de Bruijn graph representation is actually a very common and useful way to

represent assemblies, to represent the assembly problem, and in fact,

many modern software tools for assembly use de Bruijn graphs as the internal

representation of the relationships between the sequencing reads.

So while shortest common superstring and Eulerian walk are both flawed

formulations of the assembly problem, the overlap graph and the de Bruijn graph

are both going to continue to be very useful to us in practice.