2016

2015

2014

2013

2012

2011

2010

High-throughput sequencing technologies such as that offered by Illumina have permeated nearly all areas of biological research. Illuminas technology produces sequencing reads of 35-125 bp that may have base calling errors at rates as high as 1-2%. These errors create difficulties for downstream sequence analysis tasks, such as detecting overlaps for genome assembly or aligning reads to a reference genome for SNP detection.

Due to its lower cost, deep coverage of the genome is generally possible using Illumina sequencing. Past work has shown that errors can be identified in a set of reads with deep coverage by first counting k-mers, and then considering k-mers with coverage less than some threshold to be artifacts of sequencing errors. Previous methods to correct reads with errors have searched for a minimal set of edits to the read that ensure all k-mers have sufficient coverage. We demonstrate that due to biases with respect to where errors occur in the read and the likelihood of specific nucleotide to nucleotide errors, such approaches are prone to mistakes that introduce corrected sequencing reads that fail to represent any true genomic fragment.

We introduce a program named Quake that corrects errors in reads using a more robust model of sequencing errors than previous approaches. By using read quality values and learning the rates at which nucleotides are called as errors to different nucleotides, Quake achieves near perfect accuracy on simulated data. We also demonstrate the role of error correction with Quake in improving assembly and SNP detection.

The first step towards analyzing a previously unsequenced organism is to assemble the genome by merging together the sequencing reads into progressively longer contig sequences. New assemblers such as Velvet, Euler-USR, and SOAPdenovo attempt to reconstruct the genome by constructing, simplifying, and traversing the de Bruijn graph of the reads. These assemblers have successfully assembled small genomes from short reads, but have had limited success scaling to larger mammalian-sized genomes, mainly because they require memory and compute resources that are unobtainable for most users.

Addressing this limitation, we are developing a new assembly program Contrail (http://contrail-bio.sf.net), which uses the Hadoop/MapReduce distributed computing framework to enable de novo assembly of large genomes. MapReduce was developed by Google to simplify their large data processing needs by scaling computation across many computers, and the open-source version called Hadoop (http://hadoop.apache.org) is becoming a de facto standard for large data analysis, especially in so called cloud computing environments where compute resources are rented on demand. For example, we have also successfully leveraged Hadoop and the Amazon Elastic Compute Cloud for Crossbow (http://bowtie-bio.sf.net/crossbow) to accelerate short read mapping and genotyping, allowing quick (< 4 hours), cheap (< $100), and accurate (> 99% accuracy) genotyping of an entire human genome from 38-fold short read coverage.

Similar to other leading short read assemblers, Contrail relies on the graph-theoretic framework of de Bruijn graphs. However, unlike these programs Contrail uses Hadoop to parallelize the assembly across many tens or hundreds of computers, effectively removing memory concerns and making assembly feasible for even the largest genomes. Preliminary results show contigs produced by Contrail are of similar size and quality to those generated by other leading assemblers when applied to small (bacterial) genomes, which scales far better to large genomes. We are also developing extensions to Contrail to efficiently compute a traditional overlap-graph based assembly of large genomes within Hadoop, a strategy that will be especially valuable as read lengths increase to 100bp and beyond.

2009

Biological researchers have a critical need for highly efficient methods for analyzing vast quantities of DNA resequencing data. For example, the 1000 Genomes Project aims to characterize the variations within 1000 human genomes by aligning and analyzing billions of short DNA sequences from each individual. Each genome will utilize ~100GB of compressed sequence data and require ~400 hours computation. Crossbow is our new high-throughout pipeline for whole genome resequencing analysis. It combines Bowtie, an ultrafast and memory efficient short read aligner, and SoapSNP, a highly accurate Bayesian genotyping algorithm, within the distributed processing framework Hadoop to accelerate the computation using many compute nodes. Our results show the pipeline is extremely efficient, and can accurately analyze an entire genome in one day on a small 10-node local cluster, or in one afternoon and for less than $250 in the Amazon EC2 cloud. Crossbow is available open-source at http://bowtie-bio.sourceforge.net/crossbow.

In the next few years the data generated by DNA sequencing instruments around the world will exceed petabytes, surpassing the amounts of data generated by large-scale physics experiments such as the Hadron Collider. Even today, the terabytes of data generated every few days by each sequencing instrument test the limits of existing network and computational infrastructures. Our project is aimed at evaluating whether cloud computing technologies and the MapReduce/Hadoop infrastructure can enable the analysis of the large data-sets being generated. We will report on initial results in two specific applications: human genotyping and genome assembly using next generation sequencing data.

As growth in short read sequencing throughput vastly outpaces improvements in microprocessor speed, there is a critical need to accelerate common tasks, such as short read alignment and SNP calling, via large-scale parallelization.

Crossbow is a software tool that combines the speed of the short read aligner Bowtie and the accuracy of the SOAPsnp consensus and SNP caller within a cloud computing environment. Crossbow aligns reads and makes highly accurate SNP calls from a dataset comprising 38-fold coverage of the human genome in under 1 day on a local 40 core cluster, and under 3 hours using a 320-core cluster rented from Amazon’s Elastic Compute Cloud (EC2) service. Crossbow’s ability to run on EC2 means that users need not own or operate an expensive computer cluster in order to run Crossbow. Crossbow is available at http://bowtie-bio.sf.net/crossbow under the Artistic license.

The massive volume of data and short read lengths from next generation DNA sequencing machines has spurred development of a new class of short read genome assemblers. Several of the new assemblers, such as Velvet and Euler-USR, model the assembly problem as constructing, simplifying, and traversing the de Bruijn graph of the read sequences, where nodes in the graph represent k-mers in the reads, with edges between nodes for consecutive k-mers. This approach has many advantages for these data, such as efficient computation of overlapping reads and robust handling of sequencing errors, and has demonstrated success for assembling small to moderately sized genomes. However, this approach is computationally challenging to scale to mammalian-sized genomes because it requires constructing and manipulating a graph far larger than can fit into memory.

MapReduce was developed at Google for parallel computation on their extremely large data sets, including their database of more than 1 trillion web pages. Computation in MapReduce is structured into 2 main phases: the map phase and the reduce phase, which act together to construct a large distributed hash table of key-value pairs in a map phase, and then evaluate a function on each bucket of the hash table in the reduce phase. The power of MapReduce is dozens or hundreds of map and reduce instances can execute in parallel, enabling efficient computation even on terabyte and petabyte sized data sets.

Drawing on the success of CloudBurst, a MapReduce-based short read mapping algorithm capable of mapping millions of reads to the human genome with high sensitivity, we have developed a MapReduce-based short read assembler that shows tremendous potential for enabling de novo assembly of mammalian-sized genomes. The deBruijn graph is constructed with MapReduce by emitting and then grouping key-value pairs (ki,ki+1) between successive k-mers in the read sequences. After construction, MapReduce is used again to remove spurious nodes and edges from the graph caused by sequencing error in the reads, and to compress simple chains of nodes into long sequence nodes representing the unambiguous regions of the genome between repeat boundaries. The resulting graph is a small fraction of the size of the original deBruijn graph, and is output in a format compatible with other short read assemblers for additional analysis.

Using the closely related D. melanogaster as a reference, we aggressively co-assembled the seven sequenced strains of D. simulans using our comparative assembly program, AMOScmp. The AMOScmp contigs were then passed to Celera Assembler to assemble and scaffold alongside reads that failed to match the reference genome. Our improved co-assembly increases depth of coverage threefold over the original assembly and contains thousands of additional genes. These results show that comparative assembly is a promising means for assembling diverse population samples and outperforms traditional assembly in quality and the number of genes it is able to successfully recover. In addition, when combined with overlap-based assembly, comparative assembly can succeed even for reference genomes of a different species.

2008 and earlier

Since the initial "draft" sequence of the human genome was released in 2001, it has become clear that it was not an entirely accurate reconstruction of the genome. Despite significant advances in sequencing and assembly since then, genome sequencing continues to be an inexact process. Genome finishing and validation have remained a largely manual and expensive process, and consequently, many genomes are presented as draft assemblies. Draft assemblies are of unknown quality and potentially contain significant mis-assemblies, such as collapsed repeats, sequence excision, or artificial rearrangements. Too often these assemblies are judged only by contig size, with larger contigs preferred without regard to quality, because it has been difficult to gauge large scale assembly quality.

Our new automated software pipeline, amosvalidate, addresses this deficiency and automatically detects mis-assemblies using a battery of known and novel assembly quality metrics. Instead of focusing on a single assembly characteristic as other validation approaches have tried, the power of our approach comes from leveraging multiple sources of evidence. amosvalidate statistically analyzes mate-pair orientations and separations, repeat content, depth-of-coverage, correlated polymorphisms in the read alignments, and read alignment breakpoints to identify structurally suspicious regions of the assembly. The suspicious regions identified by individual metrics are then clustered and combined to identify (with high confidence) regions that are mis-assembled. This approach is necessary for accurately detecting mis-assemblies because each of the individual characteristics has unavoidable natural variation, but, when considered together, have greatly increased analysis power. Furthermore, our pipeline can easily be adjusted to analyze assemblies utilizing new sequencing technologies where some metrics are unreliable or not available, such as base pair quality or mate pairs.

Our validation pipeline provides a robust measure of assembly quality that goes beyond the simple measures commonly reported. Evaluation of the pipeline has shown it to be highly sensitive for mis-assembly detection, and has revealed mis-assemblies in both draft and finished genomes. This is particularly troubling as scientists move away from the "gene by gene" paradigm and attempt to understand the global organization of genomes. Without a correct genome sequence or even a clear understanding of the errors present, such studies may draw incorrect conclusions. Our goals are to help scientists locate mis-assembled regions of an assembly and help them correct those regions by focusing their efforts where it is needed most. amosvalidate is compatible with many common assembly formats and is released open-source at http://amos.sourceforge.net.