IEEE Spectrum July, 2013 - 31

The Human Genome Project's goal was to
sequence the 3 billion letters that make up the
genome of a human being. Because humans
To sequence a species' genome for the first time, the double-stranded DNA molecule is first
split down the middle [1]. This creates a single-stranded template. The template is copied many
are more than 99 percent genetically identimes [2]. All the templates are then diced up at random, to create many small fragments of different
tical, this first genome has been used as a
lengths [3]. A sequencing machine determines the order of nucleotides on each of those short
"reference" to guide future analyses. A larger,
fragments [4]. Then a software program looks for the places where the sequences of letters overlap
and constructs an "assembly graph" [5]. Finally, the program constructs one continuous sequence
ongoing project is the 1000 Genomes Project,
of letters: the genome [6].
aimed at compiling a more comprehensive
picture of how genomes vary among individuals and ethnic groups. For the U.S. National
Institutes of Health's Cancer Genome Atlas, researchers are sequencing samples from more
than 20 different types of tumors to study how
the mutated genomes present in cancer cells
differ from normal genomes, and how they
vary among different types of cancer.
Ideally, a DNA sequencer would simply take
a biological sample and churn out, in order,
the complete nucleotide sequence of the DNA
molecule contained therein. At the moment,
though, no sequencing technology is capable
of this. Instead, modern sequencers produce
a vast number of short strings of letters from
the DNA. Each string is called a sequencing
read, or "read" for short. A modern sequencer
produces reads that are a few hundred or perhaps a few thousand nucleotides long.
The aggregate of the millions of reads generated by the sequencer covers the person's entire genome many times over. For example, the
HiSeq 2000 machine, made by the San Diego-
based biotech company Illumina, is one of the
most powerful sequencers available. It can
sequence roughly 600 billion nucleotides in
about a week-in the form of 6 billion reads of 100 nucleotides each.
We have an easier job when we're studying a species whose genome
For comparison, an entire human genome contains 3 billion nucleo- has already been assembled. If we're examining mutations in human
tides. And the human genome isn't a particularly long one-a pine
cancer genomes, for example, we can download the previously
tree genome has 24 billion nucleotides.
assembled human genome from the National Institutes of Health
Thus our first daunting task upon receiving the reads is to stitch website and use it as a reference. For each read, we find the point where
them together into longer, more interpretable units, such as genes. that string of letters best matches the genome, using an approximate
For a organism that has never been fully sequenced before, like the
matching algorithm; the process is similar to how your spell-check
pine tree, it's a massive challenge to assemble the genome from
program finds the correct spelling based on your misspelled word.
scratch, or de novo.
The place where the read sequence most closely matches the referHow can we assemble a genome for the first time if we have no
ence sequence is our best guess as to where it belongs. Thanks to
knowledge of what the finished product should look like? Imagine
the Human Genome Project and similar projects for other species
taking 100 copies of the Charles Dickens novel A Tale of Two Cities and (mouse, fruit fly, chicken, cow, and thousands of microbial species,
dropping them all into a paper shredder, yielding a huge number of
for example), many assembled genomes are available for use as refsnippets the size of fortune-cookie slips. The first step to reassembling
erences for this task, which is called read alignment.
the novel would be to find snippets that overlap: "It was the best" and
In general, these reference genomes are far too long for brute
"the best of times," for example. A de novo assembly algorithm for force scanning algorithms-those that simply start at the beginning
DNA data does something analogous. It finds reads whose sequences
of the sequence and work their way through the entire genome,
"overlap" and records those overlaps in a huge diagram called an as- looking for the part that best matches the read in question. Instead,
sembly graph. For a large genome, this graph can occupy many tera- researchers have lately focused on building an effective genome
index, which allows them to rapidly home in on only those porbytes of RAM, and completing the genome sequence can require
weeks or months of computation on a world-class supercomputer.
tions of the reference genome that contain good matches. Just like

de novo sequencIng

illustration by

L-Dopa

SPectrum.ieee.orG

north american

jul 2013

http://SPectrum.ieee.orG

Table of Contents for the Digital Edition of IEEE Spectrum July, 2013