251
|
Hajirasouliha I, Hormozdiari F, Sahinalp SC, Birol I. Optimal pooling for genome re-sequencing with ultra-high-throughput short-read technologies. Bioinformatics 2008; 24:i32-40. [PMID: 18586730 PMCID: PMC2718651 DOI: 10.1093/bioinformatics/btn173] [Citation(s) in RCA: 13] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/03/2022] Open
Abstract
New generation sequencing technologies offer unique opportunities and challenges for re-sequencing studies. In this article, we focus on re-sequencing experiments using the Solexa technology, based on bacterial artificial chromosome (BAC) clones, and address an experimental design problem. In these specific experiments, approximate coordinates of the BACs on a reference genome are known, and fine-scale differences between the BAC sequences and the reference are of interest. The high-throughput characteristics of the sequencing technology makes it possible to multiplex BAC sequencing experiments by pooling BACs for a cost-effective operation. However, the way BACs are pooled in such re-sequencing experiments has an effect on the downstream analysis of the generated data, mostly due to subsequences common to multiple BACs. The experimental design strategy we develop in this article offers combinatorial solutions based on approximation algorithms for the well-known max n-cut problem and the related max n-section problem on hypergraphs. Our algorithms, when applied to a number of sample cases give more than a 2-fold performance improvement over random partitioning. Contact:cenk@cs.sfu.ca
Collapse
Affiliation(s)
- Iman Hajirasouliha
- Lab for Computational Biology, Simon Fraser University, Burnaby, BC, Canada
| | | | | | | |
Collapse
|
252
|
Dolan PC, Denver DR. TileQC: a system for tile-based quality control of Solexa data. BMC Bioinformatics 2008; 9:250. [PMID: 18507856 PMCID: PMC2443380 DOI: 10.1186/1471-2105-9-250] [Citation(s) in RCA: 29] [Impact Index Per Article: 1.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/31/2008] [Accepted: 05/28/2008] [Indexed: 02/07/2023] Open
Abstract
Background Next-generation DNA sequencing technologies such as Illumina's Solexa platform and Roche's 454 approach provide new avenues for investigating genome-scale questions. However, they also present novel analytical challenges that must be met for their effective application to biological questions. Results Here we report the availability of tileQC, a tile-based quality control system for Solexa data written in the R language. TileQC provides a means of recognizing bias and error in Solexa output by graphically representing data generated by flow cell tiles. The data represented in the images is then made available in the R environment for further analysis and automation of error detection. Conclusion TileQC offers a highly adaptable and powerful tool for the quality control of Solexa-based DNA sequence data.
Collapse
Affiliation(s)
- Peter C Dolan
- Department of Zoology and Center for Genome Research and Biocomputing, Oregon State University, Corvallis, Oregon 97331, USA.
| | | |
Collapse
|
253
|
Strausberg RL, Levy S, Rogers YH. Emerging DNA sequencing technologies for human genomic medicine. Drug Discov Today 2008; 13:569-77. [PMID: 18598911 DOI: 10.1016/j.drudis.2008.03.025] [Citation(s) in RCA: 35] [Impact Index Per Article: 2.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/14/2008] [Revised: 03/24/2008] [Accepted: 03/31/2008] [Indexed: 01/22/2023]
Abstract
The completion of draft sequences of the human genome represented a remarkable achievement for automated DNA sequencing based on Sanger technology. However, the future requires substantial leaps in sequencing technology such that whole genome sequencing will become a standard component of biomedical research and patient care. In this review we describe current advances that are in early stages of development, but that point toward technology that will enable the onset of genomic medicine encompasses strategies for preventative medicine and intervention based on complete knowledge of an individual's genome.
Collapse
|
254
|
Wendl MC, Wilson RK. Aspects of coverage in medical DNA sequencing. BMC Bioinformatics 2008; 9:239. [PMID: 18485222 PMCID: PMC2430974 DOI: 10.1186/1471-2105-9-239] [Citation(s) in RCA: 26] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/08/2007] [Accepted: 05/16/2008] [Indexed: 11/25/2022] Open
Abstract
Background DNA sequencing is now emerging as an important component in biomedical studies of diseases like cancer. Short-read, highly parallel sequencing instruments are expected to be used heavily for such projects, but many design specifications have yet to be conclusively established. Perhaps the most fundamental of these is the redundancy required to detect sequence variations, which bears directly upon genomic coverage and the consequent resolving power for discerning somatic mutations. Results We address the medical sequencing coverage problem via an extension of the standard mathematical theory of haploid coverage. The expected diploid multi-fold coverage, as well as its generalization for aneuploidy are derived and these expressions can be readily evaluated for any project. The resulting theory is used as a scaling law to calibrate performance to that of standard BAC sequencing at 8× to 10× redundancy, i.e. for expected coverages that exceed 99% of the unique sequence. A differential strategy is formalized for tumor/normal studies wherein tumor samples are sequenced more deeply than normal ones. In particular, both tumor alleles should be detected at least twice, while both normal alleles are detected at least once. Our theory predicts these requirements can be met for tumor and normal redundancies of approximately 26× and 21×, respectively. We explain why these values do not differ by a factor of 2, as might intuitively be expected. Future technology developments should prompt even deeper sequencing of tumors, but the 21× value for normal samples is essentially a constant. Conclusion Given the assumptions of standard coverage theory, our model gives pragmatic estimates for required redundancy. The differential strategy should be an efficient means of identifying potential somatic mutations for further study.
Collapse
Affiliation(s)
- Michael C Wendl
- Genome Sequencing Center and Department of Genetics, Washington University, St Louis MO 63108, USA.
| | | |
Collapse
|
255
|
Simple tools for assembling and searching high-density picolitre pyrophosphate sequence data. SOURCE CODE FOR BIOLOGY AND MEDICINE 2008; 3:5. [PMID: 18423012 PMCID: PMC2374781 DOI: 10.1186/1751-0473-3-5] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 11/16/2007] [Accepted: 04/18/2008] [Indexed: 11/16/2022]
Abstract
Background The advent of pyrophosphate sequencing makes large volumes of sequencing data available at a lower cost than previously possible. However, the short read lengths are difficult to assemble and the large dataset is difficult to handle. During the sequencing of a virus from the tsetse fly, Glossina pallidipes, we found the need for tools to search quickly a set of reads for near exact text matches. Methods A set of tools is provided to search a large data set of pyrophosphate sequence reads under a "live" CD version of Linux on a standard PC that can be used by anyone without prior knowledge of Linux and without having to install a Linux setup on the computer. The tools permit short lengths of de novo assembly, checking of existing assembled sequences, selection and display of reads from the data set and gathering counts of sequences in the reads. Results Demonstrations are given of the use of the tools to help with checking an assembly against the fragment data set; investigating homopolymer lengths, repeat regions and polymorphisms; and resolving inserted bases caused by incomplete chain extension. Conclusion The additional information contained in a pyrophosphate sequencing data set beyond a basic assembly is difficult to access due to a lack of tools. The set of simple tools presented here would allow anyone with basic computer skills and a standard PC to access this information.
Collapse
|
256
|
Zerbino DR, Birney E. Velvet: algorithms for de novo short read assembly using de Bruijn graphs. Genome Res 2008; 18:821-9. [PMID: 18349386 DOI: 10.1101/gr.074492.107] [Citation(s) in RCA: 7073] [Impact Index Per Article: 442.1] [Reference Citation Analysis] [Abstract] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 02/06/2023]
Abstract
We have developed a new set of algorithms, collectively called "Velvet," to manipulate de Bruijn graphs for genomic sequence assembly. A de Bruijn graph is a compact representation based on short words (k-mers) that is ideal for high coverage, very short read (25-50 bp) data sets. Applying Velvet to very short reads and paired-ends information only, one can produce contigs of significant length, up to 50-kb N50 length in simulations of prokaryotic data and 3-kb N50 on simulated mammalian BACs. When applied to real Solexa data sets without read pairs, Velvet generated contigs of approximately 8 kb in a prokaryote and 2 kb in a mammalian BAC, in close agreement with our simulated results without read-pair information. Velvet represents a new approach to assembly that can leverage very short reads in combination with read pairs to produce useful assemblies.
Collapse
Affiliation(s)
- Daniel R Zerbino
- EMBL-European Bioinformatics Institute, Wellcome Trust Genome Campus, Hinxton, Cambridge CB10 1SD, United Kingdom
| | | |
Collapse
|
257
|
Butler J, MacCallum I, Kleber M, Shlyakhter IA, Belmonte MK, Lander ES, Nusbaum C, Jaffe DB. ALLPATHS: de novo assembly of whole-genome shotgun microreads. Genome Res 2008; 18:810-20. [PMID: 18340039 DOI: 10.1101/gr.7337908] [Citation(s) in RCA: 533] [Impact Index Per Article: 33.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/24/2022]
Abstract
New DNA sequencing technologies deliver data at dramatically lower costs but demand new analytical methods to take full advantage of the very short reads that they produce. We provide an initial, theoretical solution to the challenge of de novo assembly from whole-genome shotgun "microreads." For 11 genomes of sizes up to 39 Mb, we generated high-quality assemblies from 80x coverage by paired 30-base simulated reads modeled after real Illumina-Solexa reads. The bacterial genomes of Campylobacter jejuni and Escherichia coli assemble optimally, yielding single perfect contigs, and larger genomes yield assemblies that are highly connected and accurate. Assemblies are presented in a graph form that retains intrinsic ambiguities such as those arising from polymorphism, thereby providing information that has been absent from previous genome assemblies. For both C. jejuni and E. coli, this assembly graph is a single edge encompassing the entire genome. Larger genomes produce more complicated graphs, but the vast majority of the bases in their assemblies are present in long edges that are nearly always perfect. We describe a general method for genome assembly that can be applied to all types of DNA sequence data, not only short read data, but also conventional sequence reads.
Collapse
Affiliation(s)
- Jonathan Butler
- Broad Institute of MIT and Harvard, Cambridge, Massachusetts 02141, USA
| | | | | | | | | | | | | | | |
Collapse
|
258
|
Hernandez D, François P, Farinelli L, Osterås M, Schrenzel J. De novo bacterial genome sequencing: millions of very short reads assembled on a desktop computer. Genome Res 2008; 18:802-9. [PMID: 18332092 DOI: 10.1101/gr.072033.107] [Citation(s) in RCA: 483] [Impact Index Per Article: 30.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/24/2022]
Abstract
Novel high-throughput DNA sequencing technologies allow researchers to characterize a bacterial genome during a single experiment and at a moderate cost. However, the increase in sequencing throughput that is allowed by using such platforms is obtained at the expense of individual sequence read length, which must be assembled into longer contigs to be exploitable. This study focuses on the Illumina sequencing platform that produces millions of very short sequences that are 35 bases in length. We propose a de novo assembler software that is dedicated to process such data. Based on a classical overlap graph representation and on the detection of potentially spurious reads, our software generates a set of accurate contigs of several kilobases that cover most of the bacterial genome. The assembly results were validated by comparing data sets that were obtained experimentally for Staphylococcus aureus strain MW2 and Helicobacter acinonychis strain Sheeba with that of their published genomes acquired by conventional sequencing of 1.5- to 3.0-kb fragments. We also provide indications that the broad coverage achieved by high-throughput sequencing might allow for the detection of clonal polymorphisms in the set of DNA molecules being sequenced.
Collapse
Affiliation(s)
- David Hernandez
- Genomic Research Laboratory, Infectious Diseases Service, Geneva University Hospitals and the University of Geneva, CH-1211 Geneva 4, Switzerland.
| | | | | | | | | |
Collapse
|
259
|
Pop M, Salzberg SL. Bioinformatics challenges of new sequencing technology. Trends Genet 2008; 24:142-9. [DOI: 10.1016/j.tig.2007.12.006] [Citation(s) in RCA: 234] [Impact Index Per Article: 14.6] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/01/2007] [Revised: 12/18/2007] [Accepted: 12/19/2007] [Indexed: 12/24/2022]
|
260
|
Heath KD. The coevolutionary genetics of plant-microbe interactions. Joint annual meetings of the Society for the Study of Evolution (SSE), Society of Systematic Biologists (SSB), and American Society of Naturalists (ASN), Minneapolis, MN, USA, June 2008. THE NEW PHYTOLOGIST 2008; 180:268-270. [PMID: 19138218 DOI: 10.1111/j.1469-8137.2008.02633.x] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/27/2023]
Affiliation(s)
- Katy D Heath
- Department of Ecology and Evolutionary Biology, University of Toronto, Toronto, Canada (email )
| |
Collapse
|
261
|
Abstract
In the last year, high-throughput sequencing technologies have progressed from proof-of-concept to production quality. While these methods produce high-quality reads, they have yet to produce reads comparable in length to Sanger-based sequencing. Current fragment assembly algorithms have been implemented and optimized for mate-paired Sanger-based reads, and thus do not perform well on short reads produced by short read technologies. We present a new Eulerian assembler that generates nearly optimal short read assemblies of bacterial genomes and describe an approach to assemble reads in the case of the popular hybrid protocol when short and long Sanger-based reads are combined.
Collapse
|
262
|
Baker S, Holt K, Whitehead S, Goodhead I, Perkins T, Stocker B, Hardy J, Dougan G. A linear plasmid truncation induces unidirectional flagellar phase change in H:z66 positive Salmonella Typhi. Mol Microbiol 2007; 66:1207-18. [PMID: 17976161 PMCID: PMC2652032 DOI: 10.1111/j.1365-2958.2007.05995.x] [Citation(s) in RCA: 20] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 12/31/2022]
Abstract
The process by which bacteria regulate flagellar expression is known as phase variation and in Salmonella enterica this process permits the expression of one of two flagellin genes, fliC or fljB, at any one time. Salmonella Typhi (S. Typhi) is normally not capable of phase variation of flagellar antigen expression as isolates only harbour the fliC gene (H:d) and lacks an equivalent fljB locus. However, some S. Typhi isolates, exclusively from Indonesia, harbour an fljB equivalent encoded on linear plasmid, pBSSB1 that drives the expression of a novel flagellin named H:z66. H:z66+S. Typhi isolates were stimulated to change flagellar phase and genetically analysed for the mechanism of variation. The phase change was demonstrated to be unidirectional, reverting to expression from the resident chromosomal fliC gene. DNA sequencing demonstrated that pBSSB1 linear DNA was still detectable but that these derivatives had undergone deletion and were lacking fljA(z66) (encoding a flagellar repressor) and fljB(z66). The deletion end-point was found to involve one of the plasmid termini and a palindromic repeat sequence within fljB(z66), distinct to that found at the terminus of pBSSB1. These data demonstrate that, like some Streptomyces linear elements, at least one of the terminal inverted repeats of pBSSB1 is non-essential, but that a palindromic repeat sequence may be necessary for replication.
Collapse
Affiliation(s)
- Stephen Baker
- The Wellcome Trust Sanger Institute, The Wellcome Trust Genome Campus, Hinxton, Cambridgeshire CB10 1SA, UK.
| | | | | | | | | | | | | | | |
Collapse
|
263
|
Raes J, Foerstner KU, Bork P. Get the most out of your metagenome: computational analysis of environmental sequence data. Curr Opin Microbiol 2007; 10:490-8. [DOI: 10.1016/j.mib.2007.09.001] [Citation(s) in RCA: 130] [Impact Index Per Article: 7.6] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/02/2007] [Revised: 08/27/2007] [Accepted: 09/03/2007] [Indexed: 11/28/2022]
|
264
|
Dohm JC, Lottaz C, Borodina T, Himmelbauer H. SHARCGS, a fast and highly accurate short-read assembly algorithm for de novo genomic sequencing. Genome Res 2007; 17:1697-706. [PMID: 17908823 PMCID: PMC2045152 DOI: 10.1101/gr.6435207] [Citation(s) in RCA: 207] [Impact Index Per Article: 12.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/24/2022]
Abstract
The latest revolution in the DNA sequencing field has been brought about by the development of automated sequencers that are capable of generating giga base pair data sets quickly and at low cost. Applications of such technologies seem to be limited to resequencing and transcript discovery, due to the shortness of the generated reads. In order to extend the fields of application to de novo sequencing, we developed the SHARCGS algorithm to assemble short-read (25-40-mer) data with high accuracy and speed. The efficiency of SHARCGS was tested on BAC inserts from three eukaryotic species, on two yeast chromosomes, and on two bacterial genomes (Haemophilus influenzae, Escherichia coli). We show that 30-mer-based BAC assemblies have N50 sizes >20 kbp for Drosophila and Arabidopsis and >4 kbp for human in simulations taking missing reads and wrong base calls into account. We assembled 949,974 contigs with length >50 bp, and only one single contig could not be aligned error-free against the reference sequences. We generated 36-mer reads for the genome of Helicobacter acinonychis on the Illumina 1G sequencing instrument and assembled 937 contigs covering 98% of the genome with an N50 size of 3.7 kbp. With the exception of five contigs that differ in 1-4 positions relative to the reference sequence, all contigs matched the genome error-free. Thus, SHARCGS is a suitable tool for fully exploiting novel sequencing technologies by assembling sequence contigs de novo with high confidence and by outperforming existing assembly algorithms in terms of speed and accuracy.
Collapse
Affiliation(s)
- Juliane C. Dohm
- Max-Planck-Institute for Molecular Genetics, 14195 Berlin-Dahlem, Germany
| | - Claudio Lottaz
- Max-Planck-Institute for Molecular Genetics, 14195 Berlin-Dahlem, Germany
- Institute for Functional Genomics, Computational Diagnostics, University of Regensburg, 93053 Regensburg, Germany
| | - Tatiana Borodina
- Max-Planck-Institute for Molecular Genetics, 14195 Berlin-Dahlem, Germany
| | - Heinz Himmelbauer
- Max-Planck-Institute for Molecular Genetics, 14195 Berlin-Dahlem, Germany
- Corresponding author.E-mail ; fax 49-30-8413-1380
| |
Collapse
|
265
|
Jeck WR, Reinhardt JA, Baltrus DA, Hickenbotham MT, Magrini V, Mardis ER, Dangl JL, Jones CD. Extending assembly of short DNA sequences to handle error. Bioinformatics 2007; 23:2942-4. [PMID: 17893086 DOI: 10.1093/bioinformatics/btm451] [Citation(s) in RCA: 189] [Impact Index Per Article: 11.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/14/2022] Open
Abstract
UNLABELLED Inexpensive de novo genome sequencing, particularly in organisms with small genomes, is now possible using several new sequencing technologies. Some of these technologies such as that from Illumina's Solexa Sequencing, produce high genomic coverage by generating a very large number of small reads ( approximately 30 bp). While prior work shows that partial assembly can be performed by k-mer extension in error-free reads, this algorithm is unsuccessful with the sequencing error rates found in practice. We present VCAKE (Verified Consensus Assembly by K-mer Extension), a modification of simple k-mer extension that overcomes error by using high depth coverage. Though it is a simple modification of a previous approach, we show significant improvements in assembly results on simulated and experimental datasets that include error. AVAILABILITY http://152.2.15.114/~labweb/VCAKE
Collapse
Affiliation(s)
- William R Jeck
- Department of Biology, University of Carolina-Chapel Hill, Chapel Hill, NC 27599, USA.
| | | | | | | | | | | | | | | |
Collapse
|