Video 4-1: Exploding Newspapers, DNA Sequencing Technology

0:02 Welcome back to uh algorithms of bionformmatics. We'll start a fresh new topic with some I think again uh very nice nice puzzles uh and algorithms to solve them. This time we're putting together genomes something we're that popped up or I've alluded to this uh ref human reference genome and so on uh but we didn't really talk about where these come from. Yeah. And uh today I want to show you both a little bit kind of the intuitive version of the lab techniques so that we can have a bit of a feeling for what kind of restrictions they come with and then again as always focusing on the algorithms to work with what comes out. And let me start with um a little fun motivation for this problem. And this is from Compo and Pepser's book. Uh suppose you take a stack of newspapers. These are all identical New York Times issues from whatever June 27th of 2000. I'm not sure what happened on that day. Maybe uh someone can look that up. Uh they don't give away the the solution there.

1:11 Now suppose you take take that pile of newspapers and you just blow it up. What you're left with and suppose that paper doesn't burn. So maybe their example isn't perfect. uh paper doesn't burn. What you're left with is all these little snippets of these many copies of the same paper and from that you're trying to answer what was the headline on that day which I indeed now am curious to find out. Um clearly the example is a bit whimsical and extreme. Now how would you even start having any chance of doing this? Right? If you take a single newspaper and you rip it to pieces or maybe a more a more um true version, you put it in in one of these machines that just uh carefully cut it into very tiny pieces. If you just do that and all the pieces are nice rectangular as these machines do, um there's no way to really assemble back the original paper because maybe there's a few cases where some character sticks over the edge and you can make sure that these are connected. Uh but often times or between the lines there will be nothing to guide you. So there's just not enough information for reconstructing this. Uh the key why here there is a hope is that you have these many many copies of the paper. So likely they're going to get scattered in different places and so by finding pieces that have the same information from different copies and overlap them there's a chance that you can puzzle your way through the entire paper maybe.

2:52 And unfortunately this is not not so far away from what genome assembly looks like. uh you'll see in a second there's much less dynamite and boom involved. Apart from that uh it looks almost as daunting.

3:10 So let's start with a bit of the lab technique background. How do we even start reading out something that is you know three billion letters long but so tiny that you can't see it, you can't touch it. uh even on a microscope it's you can see chromosomes but not much more fine grain versions. How do we do this even uh on a conceptual level?

3:33 The answer is uh through clever clever indirect tricks and chemical tools at the end of it. Um there's two main methods and I want to briefly present both. Uh the first one is the the historically more relevant one that was my understanding is the main one used for the human reference genome and then since the turn of the millennium roughly uh this was replaced by another technique but this first one um is is kind of old and the principle hasn't changed so much. The only reason why it fell out of fashion is cost is uh I think it was when they started around uh one pick your favorite currency in unit per base. So sequencing one base costs one one euro and now multiply that with the three billion bases and you get a a hefty price tag.

4:34 is also relevant uh that he won the Nobel Prize. Frederick Sanger that is it was his second. There's not so many people that got two Nobel prizes. He's one of them. Uh he popped up early in the lecture for sequencing insulin. Um and the other one again a sequencing task but this time nucleic acids. Um he was was pioneering this a lot. >> Second type of oligode on the surface. That's not the one.

5:10 >> DNA sequencing is the process of working out the order of the building blocks or bases in a strand of DNA. DNA. Before we can sequence the DNA, it has to be cut up into smaller pieces that are inserted into plasmid DNA and then put into bacterial cells. This makes it possible to produce lots and lots of copies of it. As the bacterial cells multiply, the DNA is then isolated from the bacteria and sent for sequencing.

5:47 The isolated DNA is transferred to a plate where the sequencing reaction will take place. A mixture of ingredients is added. These include free DNA bases A, C, G, T, DNA polymerase enzyme, and DNA primers. Modified DNA bases labeled with colored fluorescent tags are also added. These are called terminator bases.

6:29 To start the sequencing reaction, everything is heated to 96°. This separates the DNA into two single strands. The temperature is then lowered to 50°.

6:43 This enables the DNA primers to bind to the plasmid DNA. The temperature is then increased to 60° and the enzyme DNA polymerase binds to the primer DNA.

6:57 DNA polymerase starts making a new strand of DNA by adding unlabeled DNA bases to the target DNA. It continues to add DNA bases until a terminator base is added. These terminator bases have been chemically altered so that no more bases can be added to the new strand of DNA. Once a terminator base is added, the DNA polymerase enzyme stops making DNA and falls away from the strand. Everything is then heated to 96° C again to separate the new DNA strand from the original strand.

7:43 So maybe a quick kind of summary up to this point. The first step was how do you even make many copies? Remember we have the pile of newspaper. We need many copies of DNA. And it seems to be the easiest is to hijack bacteria to do it for us. um kind of using life itself to do it which has um a potential problem. What if some small snippet of the DNA you want to copy is somehow lethal for bacteria for some stupid reason. So you may have gaps because of that. I think this is what happened at some early stages. Okay, but first ignore this part. There's some some way to produce copies of DNA. Then the second one was we start reading at some specific places. So we need these primers. we can only start reading at specific points. But uh apart from that, we get copies of parts of the DNA of random length because it's random when this terminator base finds its way into the process of creating the copy. So you get many many copies from starting from the same place but ending in random positions.

8:44 But it's it's important that you can control where they start. That's the primer they call that's a special sequence where this uh reverse complement copy can attach to.

8:56 Okay. This process of heating and cooling is repeated again and again to produce lots of fragments of DNA of different lengths. The length of each fragment depends on when a terminator base got added.

9:35 To read the sequence of the DNA, the various fragments are separated by length using a process called electrofaresis. A capillary tube is lowered into each well of the plate and an electrical charge is applied. This causes the negatively charged DNA molecules to move through the capillary tube.

9:57 Each capillary contains a porous gel. The shorter fragments of DNA move through the gel more easily than the longer DNA fragments. As a result, the fragments become arranged by size from the shortest to the longest. As the DNA fragments come to the end of the capillary, a laser makes the terminator bases light up. The color is detected by a camera and recorded. Each terminator base is labeled with a different color. A flores green. C blue, G yellow, and T red. The shortest DNA fragments will be read first and the longest read last. The sequencing machine records the color of the terminator bases as a series of colored blocks.

10:59 Each colored block represents the labeled terminator base at the end of each fragment of DNA. By converting the colors into letters, we get the sequence of our piece of DNA.

11:22 All right. So, a pretty clever trick, this sorting by length question. Just so you know on the 27th of June 2000 page news was an article announcing >> the human genomes of the human >> I should I should have made the connection the year 2000 I remember yeah there was some controversy at around at the time that people the the science news cycle sped out the human genome is deciphered when it was only really 90%. And I think it took um it's only a couple of years ago that they finished it in entirety because of these these problems that well that pop up here. Uh so I I'm not 100% sure, but I would assume that this last step is really a bottleneck, right? You have to get these molecules moving through the tube. You can't do that arbitrarily quickly because you need to have the light recorded carefully. Uh, and so you need essentially for each sequence you need a tube. Uh, and I could imagine you can build machines that do this somewhat in parallel, but maybe not millions of things in parallel.

12:34 That's why there's probably an inherent limit to this. Uh, the benefit seems to be that you can sequence relatively long reads. Maybe a thousand bases is still okay. The downside it seems to be cost and potentially also sometimes uh you get errors that um the the readout is not perfect. Well, perfect will never work. Uh but the second um group of methods seems to do really well on reading much much shorter reads. Think of 150 to 200 base pairs bases. um but at a a tiny fraction of the cost and very reliable for this first part at least and then once you get to longer reads it becomes very quickly uh noisy. Now this um this yeah commercially available since 2005. So they were developed after the human human genome project was over. And I think that's not a coincidence. Uh because with this reference genome there was suddenly a market for sequencing genomes and doing something productive on it all sorts of health applications where people could again make money with the application.

13:50 Uh, and so I want to show this video. Um, take into account that this is by Illuminina Sequences Sequencing themselves. It's one of the leading companies that builds these machines. So, there's a little bit of advertising in. They might not stress the weaknesses as much as maybe some some other videos would, but I think it's very nicely illustrated. For this one, I think the details are a bit more messy and we don't care about the details all that much. Maybe just take it as a sign of sophistication that people really um developed um iterations on this just to make it more product more more um more parallelizable and more reliable. >> Base call >> aluminous sequencing systems have moved from a four channel detection. >> Let's start this from beginning.

14:52 The aluminina sequencing workflow is composed of four basic steps. Library preparation, cluster generation, sequencing, and [music] data analysis. There are many ways to prepare libraries based on sample input type and sequencing application. [music] All library preparation methods add adapters to the ends of the DNA fragments. Through library preparation, these adapters contain [music] regions such as sequencing initiation sites, indexes for molecular barcoding and regions that will bind [music] or hybridize to complimentary sequences on the flow cell. Clustering is a process where each library [music] fragment molecule is amplified to create a cluster of identical copies on the flow cell surface. Aluminina utilizes two flow cell architectures. random flow cells with a lawn of oligos over the entire surface and patterned flow cells with oligos only in nano wells. Newer aluminous systems utilize patterned flow cell technology to create clusters at greater density and efficiency. Flow cells are coded with a lawn of two types of oligos. Cluster generation occurs when library fragments hybridize to the surface of the flow cell. DNA fragments are bound to the flow cell substrate through hybridization of complimentary sequences. After libraries are attached to the flow cell, the strands are now clonally amplified through a novel amplification chemistry called exclusion amplification or XAMP.

16:19 [music] After the polymerase creates a copy of the hybridized template molecule, another copy is made by hybridizing to the second type of oligote [music] on the surface, creating two identical copies tethered to the surface of the flow cell. The process [music] is then >> so my understanding is that this is how they trigger a chain reaction so that you get the same snippet of DNA in each of these clusters. I think they don't really clearly say this, but there's a single one attaching to these lawn this these fragments at the bottom. They stick to any kind of DNA that has these adapters attached. And they hope that one will stick and then we'll amplify so that the cluster is filled with a with copies of the same same read or the same sample >> heated >> many times per cluster resulting in clonal amplification of all the library fragments. >> X amp performs this process [music] quickly, efficiently and in real time.

17:21 >> After amplification, the reverse [music] strands are removed leaving only the forward strands. The three prime ends are blocked during the removal of the reverse strand to prevent unwanted [music] priming during sequencing. Sequencing begins with the extension of the first sequencing primer to produce the first read. With each cycle, a mix of fluorescently tagged nucleotides are available for addition to the growing chain. Only a single [music] fluorescent base is incorporated that is complmentary to the sequence of the template. After the addition of each nucleotide, the clusters are excited by a light source and a characteristic fluorescent signal is emitted. This proprietary process is [music] called the luminous sequencing by synthesis. The number of cycles determines the length of the read. The emission wavelength along [music] with the signal intensity determines the base call. Aluminous sequencing systems have moved from a four channel detection chemistry to a twochannel detection chemistry. Two channel detection chemistry improves efficiency and reduces sequencing run times. New XLE SPS chemistry [music] further improves the speed and accuracy of the two channel detection approach through an improved block and linker and a new polymerase engineered to incorporate nucleotides faster [music] and with higher fidelity. This delivers up to two times faster incorporation rates relative to standard SPS. All identical sequence strands in a given cluster [music] are read simultaneously.

18:54 Hundreds of millions up to billions of clusters are sequenced in a massively parallel process. This image represents a small fraction of the flow cell. After the completion of the first read, the read product is washed away. [music] In this step of the example, the index one read primer is introduced and hybridized to the template. The [music] index read is generated similar to the first read. After completion of the index [music] read, the read product is washed off. The template now folds over and binds the second oligo on the flow cell. Polymerases [music] extend from the second reverse strand oligo forming a doublestranded bridge.

19:36 >> This doublestranded DNA is then linearized and the original forward strand is removed leaving only the reverse strand. Index two is read in the same manner as index one with the introduction of an index 2 sequencing primer. >> Why they do this double reading? >> I think it's not exactly clear. They don't explain it. >> Read two begins with the introduction of the read two sequencing primer. >> As with read one, the sequencing steps are repeated until the desired read length is achieved. >> This entire process generates billions of reads representing all of the fragments. [music] from >> sequences from pulled libraries are separated [music] based on the unique indexes introduced during the library preparation. Based on the library preparation and chosen sequencing application, downstream processes can either [music] assemble sequences to reconstruct the original sample without the need of a reference sequence. Map and align sequences to a reference genome to identify regions that differ from [music] the reference genome and detect variations. or count molecules via sequencing reads [music] to assess abundance and gene expression.

20:48 >> This OMIC data can be easily centralized within the aluminina connected software ecosystem. >> Okay, we'll skip the uh advertising part about their software infrastructure. Uh you see there's a lot of steps that they don't actually explain what happens or why. Uh everything is read forward and backward. Maybe you get better better errors. Uh fewer errors that way because you can probably sequence more carefully at the beginning of uh of the process. Um I think the the key point is unlike in this previous section you skip this step of sorting the copies or producing copies of different length but rather they they found a clever chemical way to have these bases attached with this fluorescent light so they can read off the current base that was added but then modify the base so that then the copying can continue. And again the video doesn't tell us how they do it and they may not uh let that knowledge out.

21:48 That's their secret. But the main point is that they can do this on this whole plate for millions of sequences in parallel. The whole process is probably still slow. Each of these rounds of adding one base, reading it out, washing it off and and all this probably is seconds and minutes, maybe hours. Uh but because they can do it for an entire large samples of of millions of reads, the cost per read is very very low. um around the point that sequencing your genome is less than a€,000 euros these days. Um and that that probably includes the post-processing which we're going to look at.

22:37 Okay. Uh so much for the um lab techniques in the background. Again, certainly you don't need to know the details. Uh but keep in mind the uh the core problem in both of these is you only get short snippets. Uh you can multiply the sequence in advance so you get the snippets in many places. Um but you can't expect very long reliable contiguous reads in one go. The only way to get cheaper is to make this in parallel but have even shorter snippets.

23:15 Yeah, depending on the technology, hundreds or thousands of bases and uh these are somewhat reliable, but we'll come back to this at the end. Uh nothing is perfect. So all the methods that rely on perfect uh input data um will have limitations.

23:42 Now the post-processing here's um again from the book the idealized picture you have many copies of the same long string you break this into pieces this can be done chemically as far as I understand this is not not a hard step and then you sequence all those reads and you can pretend that these reads are roughly the same length cutting them off at the end is actually harmless so wasting a few bases there is is not the big Then to sequence the original string, you would have to overlay all these these snippets and hope that they are long enough and convey enough information that this consensus string that you build from overlaying them all has meaning or is at least close to the original string.

24:27 I guess it's quite clear from the outset that this is not going to be possible possible for some contrived cases. Say if your original string is uh say four copies of some string just repeat it four times. Uh distinguishing that from five copies if your reads are not long enough to stretch over many copies of S is impossible.

24:57 You can try to get information about if you can recognize the end points maybe with how often you get fragments from each place. Maybe you can try to infer the number of copies. But there are fundamental limits to the to the reconstruction problem. It's not impos in general possible to get this string in all cases.