I'm pleased to announce the publication of "Tackling soil diversity
with the assembly of large, complex metagenomes", by Adina Howe, Janet
Jansson, Stephanie Malfatti, Susannah Tringe, James Tiedje, and
myself. The paper is openly available on the PNAS Web site here
(open access).
External links:
This paper is a milestone for me personally, because it's one of the
two projects that drove my first five years of research. This is the
project that led us to develop scalable k-mer counting with the khmer toolkit; figure out compressible De Bruijn
graphs and partitioning;
and ultimately led to digital normalization.
The story starts way back in ~2009, when Adina Howe arrived in my lab.
She had applied for an NSF postdoctoral fellowship in bioinformatics
to work between Jim Tiedje and me. (Adina
endearingly refers to me as her "less famous advisor.") Over the
first few weeks of her time in our labs, we decided that we would
fling Adina at the Great Prairie Grand Challenge,
an effort to apply the newly available Illumina sequencing technology
to the characterization of soil. I had some previous experience with
metagenomics from grad school, and somewhat
to my surprise found myself the local expert on shotgun metagenomics,
so I thought, what the heck?
We then proceeded to fail repeatedly for two years.
The fundamental challenge of this project lay at the intersection of
two problems: first, the large volume of data produced by Illumina
made most obvious approaches fail; and second, soil is the most
diverse and rich environment on the planet, exceeding the complexity
of the human genome by 100-1000 fold, meaning most obvious approaches
fail :).
What did we try?
First, we tried BLASTing the reads against nr. This was frustrating
on several levels. We had about 500m 2x76 bp reads from the Illumina
GAII machine, and it took a really long time to search these against a
large database like nr. Most reads didn't match, and, when they did,
they were very short matches that we feared were non-specific. After
a pain-filled few months of BLASTing, we decided we needed to get longer
contigs out of these. Cue the decision to attempt assembly!
Now, we faced the problem of actually completing an assembly. With
the diversity and volume of our data, most computers just ...broke. We
spent a lot of time crashing our lab computers, to no avail.
Since the problem was the volume of data, we decided to try
eliminating low-coverage reads by trimming them at low-abundance
k-mers. The logic was that we only expected high-abundance things to
assemble anyway, so if we stopped feeding low-abundance data into the
assembler maybe we could scale the whole process up. This approach had
been applied to several complex microbial communities, including
permafrost soil and
the rumen microbiome. Tallymer (the only
k-mer counter available at the time) also crashed on the volume of
data, and didn't seem that useful for trimming, either. This led us
to adapt khmer to low-memory k-mer
counting and read trimming -- you can see one of my first scientific
blog posts on that, here.
Once we trimmed the data, we fed it into an assembler and ... got
nothing. Turns out when you have shallow sequencing of an incredibly
diverse community, everything is low coverage; eliminating
everything with low coverage means you eliminate all your data!
(You may be noticing the "failure" theme here. Yes, it was a slightly
stressful time.)
Then came the Terabase Metagenomics meeting, a gathering of
computational folks and microbiologists interested in environmental
microbiology. This meeting convinced me that absolutely no one had a
solution -- all of the people working on large metagenomes were stuck just
like us. This was an important step mentally, because it
convinced me that this project was worth some real effort. Another
important aspect of this meeting was that the one of the groups that
claimed they had a partial solution was unwilling to share their
code with us (despite us being, in theory, collaborators). So I
mentally said, "screw 'em, I guess we'll have to go this alone."
Discussions at this meeting and follow-on conversations in my lab then
led to the development of the compressible De Bruijn graph
implementation featured here.
The conversations went something like this: "We should be able to
subdivide the data by walking from k-mer to k-mer." "How can we do
that?" "I don't know." "How about..." <repeated banging of head
against table followed by trial implementation> "That doesn't scale,
does it?" "No, shh, the k-mers will hear you." <repeat from beginning>
We eventually solved the problem (see our paper).
Entertainingly, the paper that came out of that work happened because I
gave the task of determining the limits of our k-mer graph
storage to Jason Pell. I specifically remember waving my hands at him, telling
him to figure it out, and
saying "You might look at percolation theory. I bet there's a
critical point in there somewhere." He then went off and figured it
out, taking about 6 months to become well versed in percolation theory
and associated simulations. True story. Mentorship at its best!
Once that worked we could assemble the Illumina GAII data by breaking it up into
disconnected partitions, or graph components. Huzzah! We got
about a 20x scaling factor out of this, so we could now take data that
would ordinarily require a maximum of 300 GB of RAM and work with it
in under 60 GB of RAM. Of course, in the meantime, Illumina had come out
with HiSeq...
I vividly remember the phone call with our JGI collaborators where we
announced our partitioning approach. I said, "Hey, so we can assemble
all 500m reads!" And they said, "Great! We just brought our HiSeqs on
line -- here's another 2 billion reads. Does your solution scale to that?"
The answer was no, our solution did not scale to that. The reason
we'd needed to assemble in ~60 GB of RAM was that Amazon m4.xlarge
machines had 68 GB of RAM; we didn't have access to 300 GB machines.
I became rather depressed at this point. Because of Illumina's damned
data generation capacity, we'd spent about two years coming up with
solutions that made us fall slightly slower behind than everyone else.
This didn't seem like a good way to do bioinformatics research.
The fundamental problem, it seemed, was that even when we could break
things up into partitions, the partitions would be getting bigger and
bigger as we sequenced more deeply; this led to more data to partition,
which was the blocking step.
Banging our head against this occupied our next few months. The key
insight we eventually reached was that even though the partitions
were growing larger, at some point the information content was
saturated. We just needed to stop collecting data at saturation!
This led to digital normalization, a sublinear algorithm for
discarding redundant data, which turns out to be pretty widely useful
in assembly and beyond.
The story doesn't quite end there, but you can read the rest of it in
the paper we just published. Our lab could now assemble large,
complex metagenomes fairly easily (although we still have a ways to go
towards the volume of data we think we need).
Adina spent a solid year or more analyzing assemblies and benchmarking
our approaches, and this paper is the result.
Challenges in publication
We submitted the paper to a Glamour Mag, and got rejected without
review. I inquired as to why, and was told, essentially, that "we
asked several reviewers informally and they said there wasn't anything
new in the methods." This was because we'd published the partitioning
approach already, and had submitted the diginorm paper separately as
well. I personally thought it would be a plus that we'd evaluated the
methods thoroughly before applying them to an unknown data set, but
apparently others felt differently.
Upon submission to PNAS, one reviewer likewise commented that they
were unsure of the distinction between our various papers on the topic
of assembly and this new paper. We tried to clarify this in the
paper, and ultimately the reviewer accepted our argument that we had
neither evaluated diginorm on metagenomes, nor shown that partitioning
led to species bins, in previous papers -- note this is separate from
the argument that, hey, we can do bigger assemblies than ever before.
Based on these experiences, I think this paper fell directly into the
"novelty squared" problem identified by Josh Bloom: it's not enough to
apply validated methods to cool new data, the methods themselves
have to be awesome and novel as well. When combined with the space
crunch of glam mags, this inevitably leads to bad science -- either the methods
(generally) or the data implications (rarely) are shorted in the final
paper.
tl; dr?
If you've made it this far, here are my personal take home messages from
the paper.
First, our combined partitioning+diginorm approach results in good
sensitivity and specificity when applied to known communities. This
mirrors what we've heard from many others who are now using the
diginorm approach.
Second, binning metagenome reads by De Bruijn graph partitions results
in species- or strain-level bins of reads. That was our intuition at the
time, and it's nice to see it born out.
Third, assembling dramatically improves the detection signal for
similarity searches (see figure S5). Since this was our original
rationale for assembly it's nice to see it born out. My pithy take
home message here is, Friends don't let friends annotate single
reads.
Fourth, we need higher coverage. We only assembled 20% of the data,
and it seems likely (based on our coverage plots; see Fig 2) that this
is due to low coverage. Give us 10x as much data and we'll give you
3x as much assembly :).
Related to this, I commonly get the question: "but you're ignoring 80%
of your data by only annotating your contigs!" Yep. I'd rather have
20% accurately annotated than 100% badly annotated, but YMMV -
hope you have a good rationale for how the increased false positive
rate is not a problem.
Take home career messages
Looking back, I'm pretty sure I wouldn't have taken on this project
if I'd understood the problem better. But it's been one of the projects
that's defined my research program. Hmm, food for thought.
Despite our progress, I've repeatedly failed to get funding for
environmental metagenome assembly. Either I'm really bad at
explaining the problem, or it's not viewed as an important problem, or
we're tackling problems that not many people have yet. How do you
evaluate this?
Good methods generalize. We've done our best to minimize parameters and
heuristics in our approaches, and, in reward, our approaches apply broadly.
We don't yet entirely understand the nature of the solutions -- partitioning
is annoyingly sensitive to coverage -- but we're working on it.
Tackling hard problems sometimes pays off! Most of my research program
came out of our various attempts to solve this problem.
--titus
There are comments.