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?
Computers are used in several steps of sequencing, from the raw data to finished sequence:
Modern sequencers usually use fluorescent labelling of DNA fragments in solution. The fluorescence encodes the different nucleobase (= “base”) types (generally called A, C, G and T). To achieve high throughput, millions 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 progressive digital photographs of the chip containing the sequencing reagent. These photos have differently coloured pixels which need to be told apart and assigned a specific colour value.
As can be seen, this (strongly magnified; the image is < 100 µm across!) image fragment is fuzzy and many of the dots overlap. This makes it hard to determine which colour to assign to which pixel (though more recent versions of the sequencing machine have improved focussing systems, and the image is consequently crisper).
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 length 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 (often called a “read”) and are considered separately. So for each fragment you get such a spectrum:
(This image is generated by an alternative sequencing process called Sanger sequencing but the principle is the same.)
Now you need to decide which base to assign for each position based on the signal (“base calling”). For most positions this is fairly easy but sometimes the signal overlaps or decays significantly. 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 up to billions of reads, each representing a short fragment of the original DNA that you sequenced.
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.
The key point that allows retrieving the original sequence from these small fragments is the fact that these fragments are (non-uniformly) 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.
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 …).
Two points make this hard:
You have got billions (!) of reads, and the reference genome is often several gigabytes large. Even with the fastest thinkable implementation of string search, this would take prohibitively long.
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).
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.
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.
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
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 sequence of the entire DNA molecule. 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 a contiguous sequence to recover the original DNA sequence.
