Take the 2-minute tour ×
Biology Stack Exchange is a question and answer site for biology researchers, academics, and students. It's 100% free, no registration required.

I've thoroughly read the Wikipedia article on DNA sequencing and can't get one thing.

There's some hardcore chemistry involved in the process that somehow splits the DNA and then isolates its parts.

Yet DNA sequencing is considered to be a very computationally-intensive process. I don't get what exactly is being computed there - what data comes into computers and what computers compute specifically.

What exactly is being computed there? Where do I get more information on this?

share|improve this question
    
This article goes through computational processes involved in lining up fragments –  jonsca Apr 18 '12 at 10:45
    
@jonsca: That looks like we already have "strings" representing the DNA, but how do we get those strings? –  sharptooth Apr 18 '12 at 11:13
    
It's not the sequencing itself that is computationally particularly intensive, but the assembly of the sequenced fragments into continuous DNA. Also, even a computationally trivial task will take time if repeated billions and billions of times. To get any decent quality sequence, one has to sequence the DNA multiple times (20+). If you have a genome that's 3 billion bases long... –  yotiao Apr 18 '12 at 11:42
    
This is a very good question. Is the computation easier if you have 300,000,000 reads of 100 bp length, or 60,000,000 reads of 500 bp in length? –  leonardo Apr 18 '12 at 15:19
1  
@leonardo That’s easy, in the second case not only do you have less reads (good), you also have longer ones (also good). Even though increasing read length increases computation time, it also increases the quality of the result. In the “worst” case you could just consider those reads as already-created contigs of several smaller overlapping reads. –  Konrad Rudolph Apr 18 '12 at 19:53

4 Answers 4

In a genome, there are usually billions of base pairs. However, it's impossible to read all of them in one go. The DNA is fragmented, and the sequence of the fragments is determined. Next-generation sequencing techniques are faster and cheaper, but produce only short fragments (say, 100 base pairs, this depends on the technology). It's extremely computationally intensive to put these fragments back together.

More info: Genome sequence assembly primer; intro in Nature Methods

share|improve this answer

As you mentioned in the question, current sequencing platforms split the genomic DNA into many small pieces which the machine then analyzes. The product of a sequencing experiment is millions or even billions of short "reads"---strings of A, C, G, and T representing the nucleotides of a single fragment of DNA.

The DNA reads in this form aren't particularly useful. The idea in the first place was to determine the sequencing of the entire genomic DNA. This is where genome assembly software comes in---to determine the original sequence of the genomic DNA by finding the optimal arrangement of overlapping reads to reconstruct the original DNA sequence.

Computers are crucial at 2 stages of this process---first, in the sequencing experiment itself, the platform must record and interpret fluorescent signals to generate the sequence reads in the first place; and second, very powerful computers are needed to assemble the reads back into contiguous DNA to recover the original DNA sequence.

share|improve this answer

Think about it like this. Suppose you own a hundred copies of "The Lord of the Rings", a 500000 word novel. Unfortunately, you have those hundred copies in the form of several million tiny scraps of paper, each of which contains about ten sequential words from the novel. Your task is to take those several million scraps of paper and put them in order so that you can read the novel from start to finish. Suppose for example you find the fragment

stab that vile creature, when he had a chance!" "Pity? 

You could then search the other several million fragments for a fragment that overlaps this in some way. Perhaps you find

chance!" "Pity? It was Pity that stayed his hand. Pity, and Mercy: 

Odds are extremely good that those fragments go together into

stab that vile creature, when he had a chance!" 
"Pity? It was Pity that stayed his hand. Pity, and Mercy: 

But maybe not! Maybe either (1) there is another fragment of the novel that has chance!" "Pity? that is the correct overlap, or oh, by the way did I mention (2) some of those scraps of paper contain errors, and you have to also detect and eliminate them.

That is an extremely computationally intensive job. DNA assemblers have the same problem: millions upon millions of of tiny scraps of DNA that overlap, that might contain errors, and that need to be sorted into order by analyzing their overlaps and gradually building up short fragments into longer and longer fragments.

share|improve this answer
    
Good analogy, but I would say DNA assemblers have the same problem, not sequencers. –  Daniel Standage Apr 18 '12 at 15:04
    
@DanielStandage: Thanks -- I am a computer guy, not a biology guy. :-) –  Eric Lippert Apr 18 '12 at 15:06
1  
@DanielStandage: Would it be correct to change the word "sequencing" with "assembling" in my question and on the charts in the genome.gov page I link to? –  sharptooth Apr 18 '12 at 15:36
1  
@sharptooth I'm not sure you want to replace the word "sequencing" with the word "assembly" in the question. The answer to your question is that sequencing and assembly are closely related, and assembly is the part that requires significant computational power. –  Daniel Standage Apr 18 '12 at 15:48

Computers are used in several steps of sequencing, from the raw data to finished sequence (or not):

Image processing

Modern sequencers usually use fluorescent labelling of DNA fragments in solution. The fluorescence encodes the different base types. To achieve high throughput, millions or billions of sequencing reactions are performed in parallel in microscopic quantities on a glass chip, and for each micro-reaction, the label needs to be recorded at each step in the reaction.

This means: the sequencer takes a digital photograph of the chip containing the sequencing reagent. This photo has differently coloured pixels which need to be told apart and assigned a specific colour value.

Digital image of a sequencing chip

As you can see, this (strongly magnified) image (fragment) is very fuzzy and most of the dots overlap. This makes it hard to determine which colour to assign to which pixel.

Base calling

One such image is registered for each step of the sequencing process, yielding one image for each base of the fragments. For a fragment of 75, that’d be 75 images.

Once you have analysed the images, you get colour spectra for each pixel across the images. The spectra for each pixel correspond to one sequence fragment (“read”) and are considered separately. So for each fragment you get such a spectrum:

Base calling spectrum

Now you need to decide which base to assign for each position (“base calling”, top row). For most positions this is fairly easy but sometimes the signal overlaps (towards the beginning in the above image) or decays significantly (near the middle). This has to be considered when deciding the base calling quality (i.e. which confidence you assign to your decision for a given base).

Doing this for each read yields billions of reads, each representing a short fragment of the original DNA that you sequenced.

Alas, this was the easy part. Most bioinformatics analysis starts here; that is, the machines emit files containing the short sequence fragments. Now we need to make a sequence from them.

Read mapping and assembly

The key point that allows retrieving the original sequence from these small fragments is the fact that these fragments are randomly distributed over the genome, and they are overlapping.

The next step depends on whether you have a similar, already sequenced genome at hand. Often, this is the case. For instance, there is a high-quality “reference sequence” of the human genome and since all the genomic sequences of all humans are ~99.9% identical (depending on how you count), you can simply look where your reads align to the reference.

Read mapping

This is done to search for single changes between the reference and your currently studied genome, for example to detect mutations that lead to diseases.

So all you have to do is to map the reads back to their original location in the reference genome (in blue) and look for differences (such as base pair differences, insertions, deletions, inversions …).

Mapped reads

Two points make this hard:

  1. You have got billions (!) of reads, and the reference genome is often several gigabytes large. Even with the fastest thinkable implementation of a string search, this would take prohibitively long.

  2. The strings don’t match precisely. First of all, there are of course differences between the genomes – otherwise, you wouldn’t sequence the data at all, you’d already have it! Most of these differences are single base pair differences – SNPs (= single nucleotide polymorphisms) – but there are also larger variations that are much harder to deal with (and they are often ignored in this step).

    Furthermore, the sequencing machines aren’t perfect. A lot of things influence the quality, first and foremost the quality of the sample preparation, and minute differences in the chemistry. All this leads to errors in the reads.

In summary, you need to find the position of billions of small strings in a larger string which is several gigabytes in size. All this data doesn’t even fit into a normal computer’s memory. And you need to account for mismatches between the reads and the genome.

Unfortunately, this still doesn’t yield the complete genome. The main reason is that some regions of the genome are highly repetitive and badly conserved, so that it’s impossible to map reads uniquely to such regions.

As a consequence, you instead end up with distinct, contiguous blocks (“contigs”) of mapped reads. Each contig is a sequence fragment, like reads, but much larger (and hopefully with less errors).

Assembly

Sometimes you want to sequence a new organism so you don’t have a reference sequence to map to. Instead, you need to do a de novo assembly. An assembly can also be used to piece contigs from a mapped reads together (but different algorithms are used).

Again we use the property of the reads that they overlap. If you find two fragments which look like this:

ACGTCGATCGCTAGCCGCATCAGCAAACAACACGCTACAGCCT
ATCCCCAAACAACACGCTACAGCCTGGCGGGGCATAGCACTGG

You can be quite certain that they overlap like this in the genome:

ACGTCGATCGCTAGCCGCATCAGCAAACAACACGCTACAGCCT
                  ATCCCCATTCAACACGCTA-AGCTTGGCGGGGCATACGCACTG

(Notice again that this isn’t a perfect match.)

So now, instead of searching for all the reads in a reference sequencing, you search for head-to-tail correspondences between reads in your collection of billions of reads.

If you compare the mapping of a read to searching a needle in a haystack (an often used analogy), then assembling reads is akin to comparing all the straws in the haystack to each other straw, and putting them in order of similarity.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.