IEEE Spectrum July, 2013 - 32

in Cambridge, Mass., or BGI, in Shenzhen, China, have more than
100 high- capacity instruments on site, but smaller institutions
like the Malaysia Genome Institute or the International Livestock
Research Institute, in Kenya, also have their own instruments. In all
these facilities, researchers are struggling to analyze the sequencing data for a wide variety of applications, such as investigations
into human health and disease, plant and animal breeding, and
monitoring microbial ecology and pathogen outbreaks.
The only hope for these overwhelmed researchers lies in advanced
computing technologies. Genomics researchers are investigating a
range of options, including very powerful but conventional servers,
specialized hardware, and cloud computing. Each has strengths
and weaknesses depending on the specific application and analysis. But for many, cloud computing is increasingly the best option,
because it allows the close integration of powerful computational
resources with extremely high-volume data storage.
One promising solution comes from Google, a company with
plenty of experience searching vast troves of data. Google doesn't
regularly release information on how much data it processes, but
in May 2010 it reported searching 946 petabytes per month. ToThe roughly 2000 sequencing instruments in labs and hos- day, three years later, it's safe to assume that figure is at least an
order of magnitude larger.
pitals around the world can collectively sequence 15 quadrillion
To mine the Internet, Google developed a parallel computing
nucleotides per year, which equals about 15 petabytes of compressed genetic data. A petabyte is 250 bytes, or in round numbers, framework called MapReduce. Outside of Google, an open-source
alternative to MapReduce called Apache Hadoop is emerging as
1000 terabytes. To put this into perspective, if you were to write
a standard platform for analyzing huge data sets in genomics and
this data onto standard DVDs, the resulting stack would be more
other fields. Hadoop's two main advantages are its programming
than 2 miles tall. And with sequencing capacity increasing at a rate
model, which harnesses the power of many computers in tandem,
of around three- to fivefold per year, next year the stack would be
and its smart integration of storage and computational power.
around 6 to 10 miles tall. At this rate, within the next five years the
While Hadoop and MapReduce are
stack of DVDs could reach higher than the
simple by design, their ability to coorbit of the International Space Station.
Clearly, we're dealing with a data delordinate the activity of many computuge in genomics. This data is vital for the
ers makes them powerful. Essentially,
Like the index of a book, a genome index is organized
advancement of biology and medicine,
they divide a large computational task
by key terms (in this case, short strings of nucleotides).
but storing, analyzing, and sharing such
into
small pieces that are distributed to
It lists all the places in the larger text (the genome) where
vast quantities is an immense challenge.
many computers across the network.
those key terms appear.
Still, it's not an unprecedented one: Other
Those computers perform their jobs
gatcacagaaattccagcatatgacatccacg
fields, notably high-energy physics and
(the "map" step), and then communicgctagccggtatatgaaatgagaggatcatc
astronomy, have already encountered
cate with each other to aggregate the
acactatgtgatgacatactagaccggtgatg
gggatatcaggaattccagcatatgacatcca
this problem. For example, the four main
results (the "reduce" step). This procgcgctagccggtatatgaaggatgagaggga
detectors at the Large Hadron Collider
cess can be repeated many times over,
gccaccactatgtgatgacatactagaccggt
produced around 13 petabytes of data
and the repetition of computation and
acgatggattacaggaattccagcatatgaca
in 2010, and when the Large Synoptic
aggregation steps quickly produces regaggccacgcgctagcgcgtatatgaaatgag
agagggacaccactatgtgatgacatactaga
Survey Telescope comes on line in
sults. This framework is much more powccccggtgatggattacaggaatcccagcata
2016, it's anticipated to produce around
erful than basic "queue system" software
tgacatacacgcgctagccgagtatatgagag
10 petabytes per year.
packages like the widely used HTCondor
acatgagagggacaccactatgtgatgacata
The crucial difference is that these
and Grid Engine. These systems also diccctagaccggtgatggattacaggaattccc
gcatatgacacccacgcgctagcacgtataag
physics and astronomy data deluges
vide up large tasks among many comcattgaaatgagagaggaatccactatgtgat
pour forth from just a few major instruputers but make no provision for the
gacatactagaccgtttgtgatggattacagg
computers to exchange information.
ments. The DNA data deluge comes
aattccagcatatgacatccacatcctagctc
Hadoop has another advantage: It uses
from thousands-and soon, tens of
caggtatatgaaatgagagggacaccactatg
the computer cluster's computational
thousands-of sources. After all, almost
INDEX
nodes for data storage as well. This
any life-science laboratory can now afa a a O f f s e t s : 9 , 4 9 , 2 5 7, 4 6 7, 5 7 1
means that Hadoop can often execute
ford to own and operate a sequencer.
a t c O f f s e t s : 2 , 6 0 , 1 0 4 , 1 2 7, 3 1 9 , 4 8 0 , 5 51
programs on the nodes themselves, thus
Major centers like the Broad Institute,
c g g O f f s e t s : 4 0 , 1 24 , 1 41 , 1 9 4 , 3 0 0 , 4 0 4

an index at the back of a book, a genome index is a list of all the
places in the genome where a certain string of letters appears-
for example, the roughly 697 000 occurrences of the sequence
"GATTACA" in the human genome.
One powerful recent invention is a genome index based on the
Burrows-Wheeler transform-an algorithm originally developed
for text compression. This efficient index allows us to align many
thousands of 100-nucleotide reads per second. The algorithm works
by carefully changing the order of a sequence of letters into one
that's more compressible-and doing so in a way that's reversible.
So, for example, let's say you have 21 As in your jumbled string of
As, Ts, Gs, and Cs. That part of the string could then be compressed
into A21, thus using 3 characters instead of 21-a sevenfold savings.
By compiling a genome index of sequences reordered in this way,
the search algorithm can scroll through the entire genome much
more quickly, looking for a read's best match.
Once we have the best algorithms and data structures, we arrive
at the next massive challenge: scaling up, and getting many computers to divvy up the work of parsing a genome.

genome IndexIng

jul 2013

north american

SPectrum.ieee.orG

http://SPectrum.ieee.orG

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