2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

One of the main challenges for computational biologists is creating efficient algorithms to match improvements in high throughput sequencing. Here we describe how CloudBurst and Crossbow use cloud computing for mapping and genotyping whole human genomes at deep coverage in an afternoon. We'll also describe how our new program, Contrail, uses cloud computing to scale up de Bruijn graph construction and analysis for the assembly of large genomes from short reads.

2009

Recent advances in DNA sequencing technology have dramatically increased in the scale and scope of DNA sequence analysis, but these analyses are complicated by the volume and complexity of the data involved. For example, genome assembly computes the complete sequence of a genome from billions of short fragments read by a DNA sequencer, and read mapping computes how short sequences match a reference genome to discover conserved and polymorphic regions. Both of these important computations benefit from recent advances in high performance computing, such as in MUMmerGPU which uses highly parallel graphics processing units as high performance parallel processors, and in CloudBurst and Crossbow which use the MapReduce framework coupled with cloud computing to parallelize read mapping across large remote compute grids. These techniques have demonstrated orders of magnitude improvements in computation time for these problems, and have the potential to make otherwise infeasible studies practical.

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.

The theory and practice of genome assembly using the Celera Assembler. Special emphasis is given to tuning the parameters and settings to get the best results for your data.

MapReduce is the parallel distributed computing framework developed by Google for large data computations, including analyzing their collection of more than 1 trillion web pages on clusters with 10s of thousands of nodes. This system enables rapid development of highly scalable applications, because developers write just a few application specific functions, and the system automatically and intelligently provides the scheduling, monitoring, and partitioning necessary to scale to this size. Furthermore, MapReduce is becoming a de facto standard for executing large computations within the cloud, where remote compute resources are used generically under a pay-as-you-go pricing model.

In this presentation, I will describe the leading open-source implementation of MapReduce called Hadoop, the cloud computing capabilities of Amazon, and outline MapReduce-based sequence analysis algorithms for read alignment, SNP discovery, and genome assembly. Scalable algorithms for these problems are essential given that current sequencing technologies routinely generate tens or hundreds of gigabytes of data for a single experiment, and can require hundreds or thousands of hours of computation. The results show MapReduce is an extremely effective system for analyzing these datasets, with near linear speedups as the size of the cluster grows. Furthermore, the Amazon compute cloud can be an efficient and cost-effective resource, especially for periodic or unusually large compute tasks.

2008 and earlier

A technique called Graph Summarization can be used to partition protein-protein interaction networks to reveal modules that are more biologically relevant than the clusters produced by other graph partitioning techniques. We apply GS to predict Gene Ontology annotations of biological process for proteins of unknown annotations. We also apply it to detecting membership in protein complexes, as annotated in the MIPS catalog. GS outperforms other approaches such MCODE, MCL and modularity.

In the middle of the last century, the Papaya ringspot potyvirus (PRSV) devastated the papaya industry on the island of Oahu in Hawaii and in other fields throughout the world. With the eminent threat of the disease spreading to the fields in the Puna district of Hawaii island, researchers in the mid 1980s developed PRSV-resistant transgenic lines of papaya using the pathogen-derived resistance approach, in which genes from PRSV were inserted into the papaya genome using a gene gun. The commercialization of these transgenic lines in the late 1990s virtually saved the Hawaiian papaya industry, but without a full genome sequence, there was lingering concern as to the exact nature of the transgenic insertions.

In my presentation, I will report on the draft genome sequence of the virus-resistant ‘SunUp’ papaya, created in collaboration with the University of Hawaii, the University of Illinois at Urbana-Champaign, and other institutions. I will focus on the computational methods used for assembling the genome, validating its correctness, and the subsequent search for transgenic inserts. Our genome wide analysis, combined with Southern blot analysis and directed PCR, confirms the efficiency of the gene gun technology, with only 3 conclusive transgenic insertions. In addition, even though the papaya genome is nearly twice the size of the Arabidopsis genome, it contains fewer genes, and thus makes it an excellent candidate for further study of biosynthetic pathways and networks.

The recent availability of new, less expensive high-throughput DNA sequencing technologies has yielded a dramatic increase in the volume of sequence data that must be analyzed. Sequence alignment programs such as MUMmer have proven essential for analysis of these data, but researchers will need ever faster, high-throughput alignment tools running on inexpensive hardware to keep up with new sequence technologies. We present MUMmerGPU, a high-throughput parallel sequence alignment program that runs on commodity Graphics Processing Units (GPUs) in common workstations. MUMmerGPU uses the new Compute Unified Device Architecture (CUDA) from nVidia to align multiple query sequences against a single reference sequence stored as a suffix tree. By processing the queries in parallel on the highly parallel graphics card, MUMmerGPU achieves more than a 10-fold speedup over a serial CPU version of the sequence alignment kernel, and outperforms MUMmer by more than 3-fold in total application time when aligning reads from recent sequencing projects using Solexa/Illumina, 454, and Sanger sequencing technologies.

Genome assembly remains an inexact science. Even when accomplished with the best software available, the assembly of a genome often contains numerous errors, both small and large. Hawkeye is a visual analytics tool for genome assembly analysis and validation, designed to aid in identifying and correcting assembly errors. Hawkeye blends the best practices from information and scientific visualization to facilitate inspection of large-scale assembly data while minimizing the time needed to detect mis-assemblies and make accurate judgments of assembly quality.

All levels of the assembly data hierarchy are made accessible to users, along with summary statistics and common assembly metrics. A ranking component guides investigation towards likely mis-assemblies or interesting features to support the task at hand. Wherever possible, high-level overviews, dynamic filtering, and automated clustering are leveraged to focus attention and highlight anomalies in the data. Hawkeyes effectiveness has been proven on several genome projects, where it has been used both to improve quality and to validate the correctness of complex genomes.

During my talk, I will discuss the techniques and tools to discover and correct misassemblies in genome assemblies. The three primary sources of information used to detect misassemblies are the "happiness" of the mate-pairs, the base call agreement within the multiple alignment of reads, and the depth of coverage of those reads.

The open source AMOS assembly package provides tools for systematically analyzing these qualities to discover regions with potential misassemblies. The AMOS Assembly Investigator is a powerful genome assembly visualizer with semantic zooming capabilities. It allows one to navigate and visually inspect these potential misassemblies in a systematic fashion at all levels of detail. Once regions with misassemblies have been identified, users can correct the misassemblies with the AMOS contig patching tools.

Genome assembly is the problem of reconstructing the genome sequence of an organism from a collection of short sequenced reads. An assembly takes the form of contiguous stretches of DNA sequence (contigs) linked together in scaffolds by mate-pair and other information. Genome assembly is scientifically one of the most important areas of bioinformatics research as an accurate genome sequence is needed for addressing several fundamental biological questions. Unfortunately, it is also one of the most complex computationally, having been proved NP-hard under various formalisms and a typical problem size of thousands or millions of inputs.

During my talk, I will discuss some of the algorithmic challenges and trade-offs in genome assembly. I will also discuss some computational methods for improving an assembly, which can be applied generally but without requiring additional laboratory results. One method was implemented in AutoEditor, which acts as a second generation base-caller to find and correct base-calling errors in reads using the original chromatogram trace and the multiple alignment of reads. A second was implemented in AutoJoiner, which attempts to automatically close gaps between linked contigs, and generally enhance contig quality, by extending the usable portion of reads within an assembly.