Genome Sequencing Technologand Algorithms
For a listing of related Artech House titles, turn to the back of this book...
18 downloads
1092 Views
2MB Size
Report
This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
Report copyright / DMCA form
Genome Sequencing Technologand Algorithms
For a listing of related Artech House titles, turn to the back of this book.
Genome Sequencing Technology and Algorithms Sun Kim Haixu Tang Elaine R. Mardis Editors
artechhouse.com
Library of Congress Cataloging-in-Publication Data A catalog record for this book is available from the U.S. Library of Congress. British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library.
Cover design by Igor Valdman
ISBN 13: 978-1-59693-094-0
© 2008 ARTECH HOUSE, INC. 685 Canton Street Norwood, MA 02062 All rights reserved. Printed and bound in the United States of America. No part of this book may be reproduced or utilized in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage and retrieval system, without permission in writing from the publisher. All terms mentioned in this book that are known to be trademarks or service marks have been appropriately capitalized. Artech House cannot attest to the accuracy of this information. Use of a term in this book should not be regarded as affecting the validity of any trademark or service mark.
10 9 8 7 6 5 4 3 2 1
List of Contributors Chapter 1
Elaine R. Mardis, Washington University
Chapter 2
Baback Gharizadeh, Roxana Jalili, and Mostafa Ronaghi, Stanford University
Chapter 3
David Okou and Michael E. Zwick, Emory University School of Medicine
Chapter 4
Jay Shendure, University of Washington Gregory J. Porreca and George M. Church, Harvard Medical School
Chapter 5
Lewis J. Frey and Joyce A. Mitchell, University of Utah Victor Maojo, Universidad Politecnica de Madrid
Chapter 6
Sun Kim and Haixu Tang, Indiana University
Chapter 7
Sun Kim and Haixu Tang, Indiana University
Chapter 8
Jiacheng Chen and Steven Skiena, Stony Brook University
Chapter 9
Haixu Tang and Sun Kim, Indiana University
Chapter 10
Paola Bonizzoni and Gianluca Della Vedova, University di Milano-Bicocca Riccardo Dondi, University of Bergamo Jing Li, Case Western Reserve University
Chapter 11
Benjamin J. Raphael, Brown University Stas Volik, Colin C. Collins, University of California at San Francisco
Chapter 12
Curt Balch and Kenneth P. Nephew, Indiana University Tim H.-M. Huang, The Ohio State University
Chapter 13
Aleksandar Milosavljevic and Cristian Coarfa, Baylor College of Medicine
Contents Part I The New DNA Sequencing Technology
1
1
An Overview of New DNA Sequencing Technology
3
1.1
An Overview
3
1.1.1 1.1.2
Background 3 Rationale for Technology Development Toward Massively Parallel Scale DNA Sequencing 4
1.1.3
Goals of Massively Parallel Sequencing Approaches
1.2 1.2.1 1.2.2
Massively Parallel Sequencing by Synthesis Pyrosequencing 6 Principle of the Method 6 Pyrosequencing in a Microtiter Plate Format 7
1.2.3 1.2.4
The 454 GS-20 Sequencer Novel Applications Enabled by Massively Parallel Pyrosequencing
8
1.3
Massively Parallel Sequencing by Other Approaches
8
1.3.1 1.3.2 1.3.3
Sequencing by Synthesis with Reversible Terminators Ligation-Based Sequencing Sequencing by Hybridization
8 8 9
vii
6
7
viii
Genome Sequencing Technology and Algorithms
1.4
Survey of Future Massively Parallel Sequencing Methods
1.4.1 1.4.2
Sequencing Within a Zero-Mode Waveguide Nanopore Sequencing Approaches
9 10
References
11
2
Array-Based Pyrosequencing Technology
15
2.1
Introduction
15
2.2
Pyrosequencing Chemistry
16
2.3
Array-Based Pyrosequencing
17
2.4
454 Sequencing Chemistry
18
2.5 2.5.1 2.5.2
Applications of 454 Sequencing Technology Whole-Genome Sequencing Ultrabroad Sequencing
19 19 20
2.5.3
Ultradeep Amplicon Sequencing
20
2.6
Advantages and Challenges
20
2.7
Future of Pyrosequencing
21
References
21
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing
25
3.1
Introduction
25
3.2
DNA Sequencing by Hybridization with Resequencing Arrays
26
3.3
Resequencing Array Experimental Protocols
28
3.4
Analyzing Resequencing Array Data with ABACUS
29
3.5 3.5.1 3.5.2 3.5.3
Review of RA Applications Human Resequencing Mitochondrial DNA Resequencing Microbial Pathogen Resequencing
33 33 33 35
3.6
Further Challenges References
38 40
3
9
Contents
ix
4
Polony Sequencing
43
4.1
Introduction
43
4.2
Overview
44
4.3
Construction of Sequencing Libraries
45
4.4
Template Amplification with Emulsion PCR
46
4.5
Sequencing
48
4.6
Future Directions
49
References
50
Genome Sequencing: A Complex Path to Personalized Medicine
53
5.1
Introduction
53
5.2
Personalized Medicine
55
5.3
Heterogeneous Data Sources
56
5.4
Information Modeling
57
5.5
Ontologies and Terminologies
58
5.6
Applications
59
5.7
Conclusion References
71 72
Part II Genome Sequencing and Fragment Assembly
77
6
Overview of Genome Assembly Techniques
79
6.1 6.1.1
Genome Sequencing by Shotgun-Sequencing Strategy A Procedure for Whole-Genome Shotgun (WGS) Sequencing
79
5
6.2 6.2.1 6.3 6.3.1
80
Trimming Vector and Low-Quality Sequences The Trimming Vector and Low-Quality Sequences Problem
82 82
Fragment Assembly The Fragment Assembly Problem
84 84
x
Genome Sequencing Technology and Algorithms
6.4
Assembly Validation
85
6.4.1
The Assembly Validation Problem
85
6.5
Scaffold Generation
87
6.5.1 6.5.2 6.5.3
The Scaffold Generation Problem Bambus GigAssembler
89 89 93
6.6
Finishing
94
6.7
Three Strategies for Whole-Genome Sequencing
94
6.8 6.8.1
Discussion A Thought on an Exploratory Genome Sequencing Framework
95
Acknowledgments
97
References
97
96
7
Fragment Assembly Algorithms
101
7.1
TIGR Assembler
102
7.1.1 7.1.2 7.1.3
Merging Fragments with Assemblies Building a Consensus Sequence Handling Repetitive Sequences
102 102 103
7.2
Phrap
103
7.3 7.3.1
CAP3 Automatics Clipping of 5’ and 3’ Poor Quality Regions
104 104
7.3.2 7.3.3
Computation and Evaluation of Overlaps 104 Use of Mate-Pair Constraints in Construction of Contigs 105
7.4 7.4.1 7.4.2 7.4.3 7.4.4 7.4.5
Celera Assembler Kececioglu and Myers Approach The Design Principle of the Celera Whole-Genome Assembler Overlapper Unitigger Scaffolder
107 108 108 109
7.5 7.5.1
Arachne Contig Assembly
110 111
105 105
Contents
xi
7.5.2
Detecting Repeat Contigs and Repeat Supercontigs
111
7.6 7.6.1
EULER Idury-Waterman Algorithm
112 112
7.6.2
An Overview of EULER
113
7.6.3 7.6.4
Error Correction and Data Corruption Eulerian Superpath
113 114
7.6.5
Use of Mate-Pair Information
115
7.7 7.7.1
Other Approaches to Fragment Assembly A Genetic Algorithm Approach
116 116
7.7.2
A Structured Pattern-Matching Approach
117
7.8
Incompleteness of the Survey
119
Acknowledgments References
120 120
Assembly for Double-Ended Short-Read Sequencing Technologies
123
8.1
Introduction
123
8.2
Short-Read Sequencing Technologies
125
8.3 8.3.1
Assembly for Short-Read Sequencing Algorithmic Methods
128 129
8.3.2
Simulation Results
129
8.4 8.4.1
Developing a Short-Read-Pair Assembler Analysis References
132 135 140
Part III Beyond Conventional Genome Sequencing
143
Genome Characterization in the Post–Human Genome Project Era
145
9.1
Genome Resequencing and Comparative Assembly
146
9.2
Genotyping Versus Haplotyping
147
9.3
Large-Scale Genome Variations
147
8
9
xii
Genome Sequencing Technology and Algorithms
9.4
Epigenomics: Genetic Variations Beyond Genome Sequences
148
9.5
Conclusion References
149 149
10
The Haplotyping Problem: An Overview of Computational Models and Solutions
151
10.1
Introduction
151
10.2
Preliminary Definitions
153
10.3 10.3.1
Inferring Haplotypes in a Population The Inference Problem: A General Rule
154 156
10.3.2 10.3.3
The Pure Parsimony Haplotyping Problem The Inference Problem by the Coalescent Model
158 158
10.3.4 10.3.5
Xor-Genotyping Incomplete Data
161 162
10.4
Inferring Haplotypes in Pedigrees
163
10.5
Inferring Haplotypes from Fragments
169
10.6
A Glimpse over Statistical Methods
175
10.7
Discussion Acknowledgments
177 178
References
178
11
Analysis of Genomic Alterations in Cancer
183
11.1 11.1.1
Introduction Measurement of Copy Number Changes by Array Hybridization Measurement of Genome Rearrangements by End Sequence Profiling
183
11.2
Analysis of ESP Data
188
11.3
Combination of Techniques
191
11.4
Future Directions References
191 192
11.1.2
185 187
Contents 12
xiii
High-Throughput Assessments of Epigenomics in Human Disease
197
12.1
Introduction
197
12.2 12.2.1 12.2.2
Epigenetic Phenomena That Regulate Gene Expression Methylation of Deoxycytosine Histone Modifications and Nucleosome Remodeling
198 198 198
12.2.3
Small Inhibitory RNA Molecules
199
12.3 12.3.1
Epigenetics and Disease Epigenetics and Developmental and Neurological Diseases
200 200
12.3.2
Epigenetics and Cancer
200
12.4 12.4.1
High-Throughput Analyses of Epigenetic Phenomena Gel-Based Approaches
201 201
12.4.2 12.4.3 12.4.4
Microarrays Cloning/Sequencing Mass Spectrometry
212 213 215
12.5
Conclusions Acknowledgments References
215 215 216
13
Comparative Sequencing, Assembly, and Anchoring
225
13.1
Comparing an Assembled Genome with Another Assembled Genome
226
13.2
Mutual Comparison of Genome Fragments
229
13.3 13.3.1
Comparing an Assembled Genome with Genome Fragments Applications Using Read Anchoring
230 230
13.3.2 13.3.3
Applications Employing Anchoring of Paired Ends Applications Utilizing Mapping of Clone Reads
232 233
13.4
Anchoring by Seed-and-Extend Versus Positional Hashing Methods
234
The UD-CSD Benchmark for Anchoring
237
13.5
xiv
Genome Sequencing Technology and Algorithms
13.6
Conclusions
239
References
241
About the Authors
245
Index
251
Part I The New DNA Sequencing Technology
1 An Overview of New DNA Sequencing Technology Elaine R. Mardis
1.1 An Overview 1.1.1
Background
The dideoxynucleotide termination DNA sequencing technology invented by Fred Sanger and colleagues, published in 1977, formed the basis for DNA sequencing from its inception through 2004 [1]. Originally based on radioactive labeling, the method was automated by the use of fluorescent labeling coupled with excitation and detection on dedicated instruments, with fragment separation by slab gel [2] and ultimately by capillary gel electrophoresis. A variety of molecular biology, chemistry, and enzymology-based improvements have brought Sanger’s approach to its current state of the art. By virtue of economies of scale, high-throughput automation and reaction optimization, large sequencing centers have decreased the cost of a fluorescent Sanger sequencing reaction to around $0.30. However, it is likely that only incremental cost decreases will continue to be achieved for Sanger sequencing in its current manifestation. This fact, coupled with the ever-increasing need for DNA sequencing toward a variety of biomedical (and other) studies, has resulted in a rapid phase of technology development of so-called next generation or massively parallel sequencing technologies, that will revolutionize DNA sequencing as we now know it. Along with this revolution will come a significant and potentially unanticipated impact
3
4
Genome Sequencing Technology and Algorithms
on sequencing-supportive infrastructures, namely, the computational hardware and software required to process and interpret these data. 1.1.2
Rationale for Technology Development Toward Massively Parallel Scale DNA Sequencing
It is perhaps interesting to evaluate the scientific underpinnings that have led to the recent revolution in DNA sequencing technology. With the completion of the reference human genome [3, 4], human geneticists and others began to question the nature and extent of genome-wide interindividual genomic variation. This concept of “strain-to-reference” comparison was not a novel one—certainly microbiologists had been studying the genomic differences between reference and pathogenic (clinical) strains of viruses and bacteria for many years, largely enabled by the ever-increasing availability of genome sequences for these organisms. Transitioning this concept to larger and more complex genomes simply is a matter of increasing the scale of comparison, since the human genome is approximately 1,000-fold larger than that of the average bacterium. It is also appropriate to note that much more focused strain-to-reference comparisons of human sequences have been pursued for many years in many studies, using PCR-based resequencing approaches. Here, PCR with genome-unique primers is utilized to selectively amplify the same region from many individual genomes and each resulting product is sequenced. A comparison of all sequences to the human reference can subsequently highlight common and rare mutations that may predispose to the disease state, predict outcome, or aid in the identification of specific treatments [5–13]. A first stab at understanding human diversity at the single-nucleotide level was embodied initially in 1999–2000 by the SNP Consortium efforts [14] and then scaled up considerably in 2002–2004 by the human “HapMap” project [15]. The latter project was significant not only in its accomplishments (over 1 million verified common human SNPs across four major human populations) but also in that it formed the basis for the development of high-throughput technologies for single nucleotide, genome-wide genotyping that could interrogate the many common human SNPs identified. For example, these approaches now enable the typing of more than 500,000 SNPs across the human genome for around $400 per sample. At the RNA level, DNA sequencing (long used for sequencing the ends of cloned mRNAs to produce expressed sequence tags or ESTs) was also being implemented to quantitate genome-wide gene expression levels for a given tissue or experimental condition by sequencing small RNA “tags” using an approach termed SAGE (serial analysis of gene expression) [16]. Mapping SAGE tag sequences back to a reference genome or transcriptome enabled identification of expressed genes and corresponding quantitative expression levels to be
An Overview of New DNA Sequencing Technology
5
ascertained [17–22] (for examples). One drawback of this powerful technique, especially compared to microarray technology, was the significant expense incurred to sequence the number of SAGE tags required to yield a meaningful result; a number that scaled with genome complexity. With genome-wide genotyping technology in-hand and providing ever-increasing numbers of SNPs per genotype, the interest in going beyond common single nucleotide variations (those SNPs found at more than 5% or greater frequency in the population, by definition), to characterize the range of variation in multiple base insertions and deletions, as well as inversions, rearrangements, and translocations began to increase. One approach to this scale of characterization was reported by Eichler and colleagues [23], and was a variation on an earlier approach that had utilized BAC (bacterial artificial chromosome) clone end sequencing to identify genome rearrangements [24]. In the Eichler approach, genomic DNA from a single CEPH individual (who also had been genotyped in the HapMap project) was used to generate a fosmid library. Next, the sequences obtained from the ends of about 1 million fosmid clones in this library were mapped back to the human reference sequence and the end mapping locations were interpreted as described next. Since fosmids package their recombinant genomes within a relatively tight size range of 35,000–50,000 bases, the expected separation between end sequences of a given insert lies in that range by definition (much more so than BACs, by contrast). Using this approach, one can identify fosmid ends that do not map both to the same chromosomal pseudomolecule in the human reference, indicating a translocation or other rearrangement has occurred. Another possibility is a fosmid end placement distance that is smaller than the expected range (the sampled genome is deleted relative to the reference genome) or is at a distance larger than expected (the sampled genome has an inserted sequence relative to the reference genome). Typically, one would then select these clones and sequence them in their entirety to better characterize the nature of the rearrangement, deletion or insertion, as was described in the Eichler manuscript. Again, although this is a very powerful method for elucidating genomic variation beyond SNP variation, significant sequencing costs are involved (around $1 million per genome). Beyond this sequencing-intensive approach, many groups [25–28] are now reporting analyses of copy number variation in individual human genomes, an offshoot of genome-wide SNP profiling on high-density microarray substrates that enable comparative genome hybridization and signal intensity analysis to ascertain regions of the genome that are exhibiting greater than two copies, in the case of amplification, and one or zero copies in the case of loss of heterozygosity or deletion.
6
1.1.3
Genome Sequencing Technology and Algorithms
Goals of Massively Parallel Sequencing Approaches
Ultimately, one major aim of massively parallel DNA sequencing instrumentation is to enable the large-scale sequencing of many human genomes in a accelerated timeframe (about 1 week per genome) at a cost approximating a high-end diagnostic assay (about $1,000 per genome). At the first pass, this will largely happen in research laboratories such as at genome centers or large pharmaceutical companies, and will involve disease-focused patient collections. Obviously, generating the data is only one part of the equation, but it must be done first. The secondary, more challenging goal is the analysis of this data on an individual genome basis and then, across all genomes in a given disease cohort, in correlation with other genomic and clinical data types. In addition to known genes, the interpretation of sequence data in nongenic sequence will become increasingly more informative as the overall knowledge of the functions of these regions of the human genome is increasingly elucidated. It is likely that with the technology at hand, however, basic research will not wait. What this means for human health is yet to be seen, but likely we will begin to distill out of these basic research activities the genomic hallmarks of disease, which can then be further coalesced into sequence-based diagnostic assays. These diagnostics will almost certainly not involve whole genome resequencing but rather will focus on the genomic hallmarks or biomarkers, perhaps using modified-scale instrumentation derived from today’s massively parallel instruments or perhaps using single-molecule detection methods that are presently under development.
1.2 Massively Parallel Sequencing by Synthesis Pyrosequencing 1.2.1
Principle of the Method
Conceptually and in practice, pyrosequencing is a completely novel approach from the standard Sanger dideoxynucleotide approach, initially reported by Nyren and colleagues [29], and later modified [30–34]. Figure 1 exemplifies the method in its current form. Basically, upon nucleotide incorporation by the polymerase, the released pyrophosphate is converted to ATP by action of the enzyme sulfurylase, providing firefly luciferase with the necessary energy source to convert luciferin to oxy-luciferin plus light. Since each template is queried with a single-nucleotide species in each step of pyrosequencing, detection of emitted light from this reaction can be directly correlated to the number of nucleotides incorporated, up to a point of nonlinear response which is typically greater than six nucleotides of the same identity (depending upon the sensitivity of the detector).
An Overview of New DNA Sequencing Technology 1.2.2
7
Pyrosequencing in a Microtiter Plate Format
The pyrosequencing concept was initially limited due to the buildup of unincorporated nucleotides and residual ATP between base additions. The inclusion of the apyrase enzyme to the pyrosequencing reaction cocktail overcame this limitation by its enzymatic action [33], and the pyrosequencing method was then translated into a commercially available microtiter plate-format instrument. Still, the microtiter plate-based assay has a limited read-length of around 10–16 nucleotides but has found widespread use for low-to-medium throughput genotyping. 1.2.3
The 454 GS-20 Sequencer
In 2004, pyrosequencing transitioned onto a massively parallel DNA sequencing instrument that achieved commercial release by 454 Life Sciences, Inc. [35]. The instrument embodies several novel approaches to DNA sequencing that tremendously streamline and parallelize the process from library construction through sequence detection, as described below. In this system, a genomic library is made by fragmenting the genomic DNA to about 500 bp, repairing the ends and ligating two 454-specific linkers to each genomic fragment. These fragments are coupled to Sepharose beads carrying covalently linked oligonucleotides complementary to the fragment library’s ligated linkers. This bead/DNA mixture is emulsified in an oil suspension containing aqueous PCR reactants, enabling the amplification of millions of unique fragment-bead combinations in a large-batch PCR format. The Sepharose beads that contain amplified DNA are prepared for the sequencing reaction by denaturation of the unattached strand and annealing of a sequencing primer, and then are pipetted into a PicoTiterPlate (PTP) device. The PTP is composed of hundreds of thousands of fused fiber optic strands, the ends of which are hollowed out to a diameter sufficient to contain a single Sepharose bead. Smaller magnetic beads, to which pyrosequencing (sulfurylase and luciferase) enzymes are covalently attached, are added into the PTP. The PTP fits into a flow-cell device that positions it against a high-sensitivity CCD camera in the 454 GS-20 sequencing instrument. Pyrosequencing follows, whereby sequential flows of each dNTP, separated by an imaging step and a wash step, take place. At each well address in the PTP, the incorporation of one or more nucleotides into the synthesized strand on each bead is captured by the CCD camera, which records positional information about each well address throughout the sequencing process. A post-run bioinformatic pipeline processes the raw pyrosequencing data into approximately 200,000 sequencing reads of about 100 bp each. Recent improvements to the 454 system have enabled increased read-lengths, averaging around 400,000 reads of 250-bp read-length per 7-hour run.
8
1.2.4
Genome Sequencing Technology and Algorithms
Novel Applications Enabled by Massively Parallel Pyrosequencing
The advent of massively parallel sequencing, ushered in by the availability of 454 pyrosequencing, has enabled genome scientists to pursue applications for DNA sequencing at levels that heretofore were often not possible, due to cost and timeline. These include SAGE profiling [36], cDNA sequencing [V. Magrini, personal communication, 2006], metagenomics [37], nucleosome positioning [38], and others. The increasing efficiency of the instrument, coupled with the availability of paired end read sequencing, predicts that the instrument will continue to inspire scientists to more and varied ingenuity in 454-based approaches.
1.3 Massively Parallel Sequencing by Other Approaches 1.3.1
Sequencing by Synthesis with Reversible Terminators
In addition to the 454 pyrosequencing chemistry, several companies and academic groups are working to develop massively parallel sequencing instrumentation that uses reversible dye terminator chemistry for DNA sequencing. To date only one has achieved commercial availability, which is the platform offered by Solexa, LTD (now a wholly owned subsidiary of Illumina, Inc.). Although this platform has a similar initial library construction procedure as that outlined for 454, once linker ligated genomic fragments are produced, they are amplified in situ following hybridization to a complementary oligo that is covalently linked to a glass slide (“flow cell”) surface. The amplified fragments, or clusters, are denatured, annealed with a sequencing primer, and placed onto the sequencing instrument for sequencing by synthesis (SBS) using 3’-blocked fluorescent-labeled deoxynucleotides. Each synthesis step includes single nucleotide incorporation, washing to remove unincorporated nucleotides, imaging of the entire flow cell, deblocking of the 3’ – OH ends of each synthesized strand, and washing. Using this approach, at present a 4-day run on the Solexa instrument results in around 50 to 60 million sequences of 40 to 50 base pairs each, for a total of around 1 Gb of sequence (following data quality filtering). 1.3.2
Ligation-Based Sequencing
An important variant to polymerase-based methods for massively parallel sequencing is an approach that depends upon the high specificity of DNA ligase to mediate the sequencing of genomic fragments. This approach builds on previous genotyping methods such as the ligation chain reaction (LCR) [39–41] and oligonucleotide ligation assay (OLA) [42] that rely on the specificity of DNA ligase to join the DNA backbone. Ligation-based sequencing is covered in great detail later in this book, and will form the core technology for a next
An Overview of New DNA Sequencing Technology
9
generation sequencing instrument scheduled to be introduced in 2007 by Applied Biosystems [H. Fiske, personal communication, 2007]. 1.3.3
Sequencing by Hybridization
The same technology that has enabled genome-wide surveys of gene expression by the hybridization of single-stranded cDNA copies of messenger RNA species [43] more recently has been utilized for a variant of genome resequencing typically referred to as “sequencing by hybridization.” Originally described early in the brief history of genome sequencing [44–47], methods to generate arrays of oligonucleotides of sufficient depth to address even single human chromosomes were not technologically feasible at that time, and so the method was not applicable to most genomes of interest. More recently, sequencing by hybridization has taken the form of whole genome genotyping of SNPs, using a variety of commercially available oligonucleotide-based approaches, such as Illumina, Affymetrix, and Nimblegen [48–50]. Since the technology to create ever-increasing densities of oligonucleotides on solid supports is rapidly improving and costs are falling, sequencing by hybridization offers an attractive first pass at characterizing genomes in advance of sequencing. Methods to extract additional information from genome-wide SNP typing microarrays are now enhancing the data value from these experiments by offering information about large-scale amplifications and deletions, as well as loss of heterozygosity (LOH). Additional historical and practical aspects of sequencing by hybridization are covered later in this book.
1.4 Survey of Future Massively Parallel Sequencing Methods Several DNA sequencing approaches of interest that will likely not be available in the near term bear mentioning in this introduction because of the incredible potential they may offer for genome sequencing at throughputs one to two orders of magnitude higher than the methods discussed in this book, as well as at high accuracy and high sequence contiguity. Concomitantly, they are the highest risk approaches presently being pursued in genome sequencing technology development. 1.4.1
Sequencing Within a Zero-Mode Waveguide
The basis for DNA sequencing in a zero-mode waveguide was first spelled out in a seminal paper by Levene et al. [51]. This paper described a sequencing reaction and detection environment, the zero-mode waveguide, that more closely correlates with the observation volumes necessary for many single-molecule detection technologies while enabling substrate concentrations to be held
10
Genome Sequencing Technology and Algorithms
optimal for the enzymological assay being performed. As described, zero-mode waveguides would be formed by electron beam lithography, followed by reactive ion etching in a metal film deposited on a microscope coverslip (in other words, the 1 × 1-inch-thin glass typically placed over samples on a microscope slide). Since each coverslip could potentially contain millions of waveguides, the resulting assay would have the potential of massive parallelism. For direct observations of single molecules, enzymes (such as DNA polymerase) could be adsorbed onto the bottom of the waveguides and provided with necessary substrates and reactants, while being monitored from below by a microscope objective that both provides the necessary illumination and collects emitted light through the same objective. Since the waveguide provides a limited illumination volume, it is much more likely that the signal of a nucleotide in the active site of the enzyme would be detected as opposed to freely diffusing labeled nucleotides. Although the latter will provide a background fluorescence due to weakly illuminated molecules, it will be essentially constant and therefore readily subtracted. Using fluorescence-coupled spectroscopy, the authors were able to observe the incorporation of coumarin-dCTP into an M13 singlestranded DNA template by immobilized mutant T7 polymerase [51]. This work has set the stage for an attempt to commercialize the zero-mode waveguide technology for DNA sequencing (and perhaps other applications) by Pacific Biosciences (Sunnyvale, California). The potential advantages of this approach for DNA sequencing include very long read-lengths of unlabeled single-template molecules with very high accuracy, in a highly multiplexed fashion. Although technically challenging, this is one approach that could potentially revolutionize DNA sequencing and its routine application in biology as well as in diagnostic and prognostic medicine. 1.4.2
Nanopore Sequencing Approaches
The Coulter counter [52] was no doubt the inspiration for the use of nanopores to sequence DNA, since it works to separate electrolyte solution-suspended particles by drawing them through a channel between two reservoirs. As a particle enters the channel, it increases the electrical impedance of the channel and therefore affects a current drop when a voltage is being passed across the channel. Current research on nanopore-based sequencing utilizes one of two types of nanopores: protein-based or synthetic. Much of the initial nanopore DNA sequencing work was performed using the bacterial protein α-hemolysin [53], a transmembrane protein that inserts into the lipid bilayer. However, these studies also have largely demonstrated that α-hemolysin pores are limited by size, variation, and stability. Hence, synthetic nanopores are currently being widely investigated for DNA-based analysis, using a wide variety of detection approaches [54–56]. The promise of nanopores includes single-molecule sequencing with
An Overview of New DNA Sequencing Technology
11
very long read-lengths, potentially without the requirement for labeling the DNA. Thousands to millions of nanopores could be contained in a single device, allowing a very high sequencing capacity in a very low cost device. The drawbacks of nanopores for sequencing so far include low sensitivity to detect signals that can be used to distinguish the identity of individual nucleotides, and difficulty forcing DNA through the pores in a uniformly single-stranded fashion, due to its tendency to form hairpins and other structures. If these limitations can be overcome, however, the possible application of nanopores to very inexpensive, very long read sequencing would undoubtedly usher in a revolution in DNA sequencing.
References [1] Sanger, F., S. Nicklen, and A. R. Coulson, “DNA Sequencing with Chain-Terminating Inhibitors,” Proc. Natl. Acad. Sci. USA, Vol. 74, No. 12, 1977, pp. 5463–5467. [2] Smith, L. M., et al., “Fluorescence Detection in Automated DNA Sequence Analysis,” Nature, Vol. 321, No. 6071, 1986, pp. 674–679. [3] Lander, E. S., et al., “Initial Sequencing and Analysis of the Human Genome,” Nature, Vol. 409, No. 6822, 2001, pp. 860–921. [4] International Human Genome Sequencing Consortium, “Finishing the Euchromatic Sequence of the Human Genome,” Nature, Vol. 431, No. 7011, 2004, pp. 931–945. [5] Akey, J. M., et al., “Population History and Natural Selection Shape Patterns of Genetic Variation in 132 Genes,” PLoS Biol., Vol. 2, No. 10, 2004, p. e286. [6] Livingston, R. J., et al., “Pattern of Sequence Variation Across 213 Environmental Response Genes,” Genome Res., Vol. 14, No. 10A, 2004, pp. 1821–1831. [7] Wilson, R. K., et al., “Mutational Profiling in the Human Genome,” Cold Spring Harb. Symp. Quant. Biol., Vol. 68, 2003, pp. 23–29. [8] Fullerton, S. M., et al., “Apolipoprotein E Variation at the Sequence Haplotype Level: Implications for the Origin and Maintenance of a Major Human Polymorphism,” Am. J. Hum. Genet., Vol. 67, No. 4, 2000, pp. 881–900. [9] Nickerson, D. A., et al., “Sequence Diversity and Large-Scale Typing of SNPs in the Human Apolipoprotein E Gene,” Genome Res., Vol. 10, No. 10, 2000, pp. 1532–1545. [10] Rieder, M. J., and D. A. Nickerson, “Hypertension and Single Nucleotide Polymorphisms,” Curr. Hypertens. Rep., Vol. 2, No. 1, 2000, pp. 44–49. [11] Zhu, X., et al., “Localization of a Small Genomic Region Associated with Elevated ACE,” Am. J. Hum. Genet., Vol. 67, No. 5, 2000, pp. 1144–1153. [12] Levine, R. L., et al., “Activating Mutation in the Tyrosine Kinase JAK2 in Polycythemia Vera, Essential Thrombocythemia, and Myeloid Metaplasia with Myelofibrosis,” Cancer Cell, Vol. 7, No. 4, 2005, pp. 387–397.
12
Genome Sequencing Technology and Algorithms
[13] Thomas, R. K., et al., “Detection of Oncogenic Mutations in the EGFR Gene in Lung Adenocarcinoma with Differential Sensitivity to EGFR Tyrosine Kinase Inhibitors,” Cold Spring Harb. Symp. Quant. Biol., Vol. 70, 2005, pp. 73–81. [14] Sachidanandam, R., et al., “A Map of Human Genome Sequence Variation Containing 1.42 Million Single Nucleotide Polymorphisms,” Nature, Vol. 409, No. 6822, 2001, pp. 928–933. [15] The International Human Genome Sequencing Consortium, “A Haplotype Map of the Human Genome,” Nature, Vol. 437, No. 7063, 2005, pp. 1299–1320. [16] Velculescu, V. E., B. Vogelstein, and K. W. Kinzler, “Analysing Uncharted Transcriptomes with SAGE,” Trends Genet., Vol. 16, No. 10, 2000, pp. 423–425. [17] Funaguma, S., et al., “SAGE Analysis of Early Oogenesis in the Silkworm, Bombyx Mori,” Insect Biochem. Mol. Biol., Vol. 37, No. 2, 2007, pp. 147–154. [18] McIntosh, S., et al., “SAGE of the Developing Wheat Caryopsis,” Plant Biotechnol. J., Vol. 5, No. 1, 2007, pp. 69–83. [19] Gibbings, J. G., et al., “Global Transcript Analysis of Rice Leaf and Seed Using SAGE Technology,” Plant Biotechnol. J., Vol. 1, No. 4, 2003, pp. 271–285. [20] Gowda, M., et al., “Deep and Comparative Analysis of the Mycelium and Appressorium Transcriptomes of Magnaporthe Grisea Using MPSS, RL-SAGE, and Oligoarray Methods,” BMC Genomics, Vol. 7, 2006, p. 310. [21] Berthier, D., et al., “Bovine Transcriptome Analysis by SAGE Technology During an Experimental Trypanosoma Congolense Infection,” Ann. NY Acad. Sci., Vol. 1081, 2006, pp. 286–299. [22] Rosinski-Chupin, I., et al., “SAGE Analysis of Mosquito Salivary Gland Transcriptomes During Plasmodium Invasion,” Cell Microbiol., Vol. 9, No. 3, 2007, pp. 708–724. [23] Tuzun, E., et al., “Fine-Scale Structural Variation of the Human Genome,” Nat. Genet., Vol. 37, No. 7, 2005, pp. 727–732. [24] Volik, S., et al., “End-Sequence Profiling: Sequence-Based Analysis of Aberrant Genomes,” Proc. Natl. Acad. Sci. USA, Vol. 100, No. 13, 2003, pp. 7696–7701. [25] Pfeifer, D., et al., “Genome-Wide Analysis of DNA Copy Number Changes and LOH in CLL Using High-Density SNP Arrays,” Blood, Vol. 109, No. 3, 2007, pp. 1202–1210. [26] Komura, D., et al., “Genome-Wide Detection of Human Copy Number Variations Using High-Density DNA Oligonucleotide Arrays,” Genome Res., Vol. 16, No. 12, 2006, pp. 1575–1584. [27] Redon, R., et al., “Global Variation in Copy Number in the Human Genome,” Nature, Vol. 444, No. 7118, 2006, pp. 444–454. [28] Kotliarov, Y., et al., “High-Resolution Global Genomic Survey of 178 Gliomas Reveals Novel Regions of Copy Number Alteration and Allelic Imbalances,” Cancer Res., Vol. 66, No. 19, 2006, pp. 9428–9436.
An Overview of New DNA Sequencing Technology
13
[29] Nyren, P., B. Pettersson, and M. Uhlen, “Solid Phase DNA Minisequencing by an Enzymatic Luminometric Inorganic Pyrophosphate Detection Assay,” Anal. Biochem., Vol. 208, No. 1, 1993, pp. 171–175. [30] Ahmadian, A., et al., “Single-Nucleotide Polymorphism Analysis by Pyrosequencing,” Anal. Biochem., Vol. 280, No. 1, 2000, pp. 103–110. [31] Ahmadian, A., et al., “Analysis of the p53 Tumor Suppressor Gene by Pyrosequencing,” Biotechniques, Vol. 28, No. 1, 2000, pp. 140–4, 146–7. [32] Ronaghi, M., et al., “PCR-Introduced Loop Structure as Primer in DNA Sequencing,” Biotechniques, Vol. 25, No. 5, 1998, pp. 876–878, 880–882, 884. [33] Ronaghi, M., M. Uhlen, and P. Nyren, “A Sequencing Method Based on Real-Time Pyrophosphate,” Science, Vol. 281, No. 5375, 1998, pp. 363, 365. [34] Ronaghi, M., et al., “Real-Time DNA Sequencing Using Detection of Pyrophosphate Release,” Anal. Biochem., Vol. 242, No. 1, 1996, pp. 84–89. [35] Margulies, M., et al., “Genome Sequencing in Microfabricated High-Density Picolitre Reactors,” Nature, Vol. 437, No. 7057, 2005, pp. 376–380. [36] Bainbridge, M. N., et al., “Analysis of the Prostate Cancer Cell Line LNCaP Transcriptome Using a Sequencing-by-Synthesis Approach,” BMC Genomics, Vol. 7, 2006, p. 246. [37] Turnbaugh, P. J., et al., “An Obesity-Associated Gut Microbiome with Increased Capacity for Energy Harvest,” Nature, Vol. 444, No. 7122, 2006, pp. 1027–1031. [38] Johnson, S. M., et al., “Flexibility and Constraint in the Nucleosome Core Landscape of Caenorhabditis Elegans Chromatin,” Genome Res., Vol. 16, No. 12, 2006, pp. 1505–1516. [39] Wiedmann, M., et al., “Ligase Chain Reaction (LCR)—Overview and Applications,” PCR Methods Appl., Vol. 3, No. 4, 1994, pp. S51–S64. [40] Wu, D. Y., and R. B. Wallace, “The Ligation Amplification Reaction (LAR)—Amplification of Specific DNA Sequences Using Sequential Rounds of Template-Dependent Ligation,” Genomics, Vol. 4, No. 4, 1989, pp. 560–569. [41] Barany, F., “The Ligase Chain Reaction in a PCR World,” PCR Methods Appl., Vol. 1, No. 1, 1991, pp. 5–16. [42] Nickerson, D. A., et al., “Automated DNA Diagnostics Using an ELISA-Based Oligonucleotide Ligation Assay,” Proc. Natl. Acad. Sci. USA, Vol. 87, No. 22, 1990, pp. 8923–8927. [43] Brown, P. O., and D. Botstein, “Exploring the New World of the Genome with DNA Microarrays,” Nat. Genet., Vol. 21, No. 1, Suppl., 1999, pp. 33–37. [44] Drmanac, R., et al., “DNA Sequence Determination by Hybridization: A Strategy for Efficient Large-Scale Sequencing,” Science, Vol. 260, No. 5114, 1993, pp. 1649–1652. [45] Lipshutz, R. J., “Likelihood DNA Sequencing by Hybridization,” J. Biomol. Struct. Dyn., Vol. 11, No. 3, 1993, pp. 637–653.
14
Genome Sequencing Technology and Algorithms
[46] Gunderson, K. L., et al., “Mutation Detection by Ligation to Complete N-Mer DNA Arrays,” Genome Res., Vol. 8, No. 11, 1988, pp. 1142–1153. [47] Broude, N. E., et al., “Enhanced DNA Sequencing by Hybridization,” Proc. Natl. Acad. Sci. USA, Vol. 91, No. 8, 1994, pp. 3072–3076. [48] Lipshutz, R. J., et al., “Using Oligonucleotide Probe Arrays to Access Genetic Diversity,” Biotechniques, Vol. 19, No. 3, 1995, pp. 442–447. [49] Wang, D. G., et al., “Large-Scale Identification, Mapping, and Genotyping of SingleNucleotide Polymorphisms in the Human Genome,” Science, Vol. 280, No. 5366, 1988, pp. 1077–1082. [50] Albert, T. J., et al., “Light-Directed 5’—>3’ Synthesis of Complex Oligonucleotide Microarrays,” Nucleic Acids Res., Vol. 31, No. 7, 2003, p. e35. [51] Levene, M. J., et al., “Zero-Mode Waveguides for Single-Molecule Analysis at High Concentrations,” Science, Vol. 299, No. 5607, 2003, pp. 682–686. [52] DeBlois, R. W., “Counting and Sizing of Submicron Particles by Resistive Pulse Technique,” Rev. Sci. Instrum., Vol. 41, 1970, p. 909. [53] Song, L., et al., “Structure of Staphylococcal Alpha-Hemolysin: A Heptameric Transmembrane Pore,” Science, Vol. 274, No. 5294, 1996, pp. 1859–1866. [54] Heng, J. B., et al., “The Electromechanics of DNA in a Synthetic Nanopore,” Biophys. J., Vol. 90, No. 3, 2006, pp. 1098–1106. [55] Meller, A., et al., “Rapid Nanopore Discrimination Between Single Polynucleotide Molecules,” Proc. Natl. Acad. Sci. USA, Vol. 97, No. 3, 2000, pp. 1079–1084. [56] Fologea, D., et al., “Detecting Single Stranded DNA with a Solid State Nanopore,” Nano. Lett., Vol. 5, No. 10, 2005, pp. 1905–1909.
2 Array-Based Pyrosequencing Technology Baback Gharizadeh, Roxana Jalili, and Mostafa Ronaghi
With the completion draft of the human genome, we are entering a new era in the biological sciences with the DNA sequencing as one of the main catalysts. In the DNA sequencing field, pyrosequencing has emerged as a technology for de novo high-throughput whole genome sequencing. The method is based on the principle of sequencing-by-synthesis and pyrophosphate detection through a series of enzymatic reactions to generate luminescence sequence peak signals. Pyrosequencing is being used from single nucleotide to whole genome sequencing and the method is commercially available for low throughput sequencing by Biotage and high-throughput sequencing by 454 Life Sciences (currently owned by Roche). In this chapter we describe the methodologies, applications and discuss current developments, which would decrease the cost of sequencing by another two orders of magnitude within the next 5 years.
2.1 Introduction DNA sequencing is a key tool to determine nucleic acids sequence and is applied in biosciences from single-nucleotide polymorphism (SNP) genotyping to whole-genome sequencing. Due to its widespread applications, an extensive number of different sciences have been benefiting from DNA sequencing from molecular biology, medicine, diagnostics, genetics, biotechnology, pharmacology, and forensics to archeology and anthropology. Moreover, DNA sequencing is promoting new discoveries that are revolutionizing the conceptual foundations of many fields. 15
16
Genome Sequencing Technology and Algorithms
High throughput and affordable DNA-sequencing techniques would undoubtedly continue the stream of the revolution initiated by the Human Genome Project. Recent impressive advances in DNA-sequencing technologies have accelerated the detailed analysis of genomes from many organisms. We have been observing numerous reports of complete or draft versions of the genome sequence of several well-studied, multicellular organisms. The Human Genome Project was made achievable by a significant reduction in DNA sequencing cost by three orders of magnitude; a further cost reduction of two to three would launch a new era of DNA sequencing applications from short DNA reads to whole-genome sequencing. The chain termination sequencing method, also known as Sanger sequencing, developed by Frederick Sanger and colleagues [1], has been the most widely used sequencing method since its advent in 1977, and still is extensively in use. The remarkable advances in chemistry, automation, and data acquisition to the Sanger sequencing method has made it into a simple and elegant technique, central to almost all past and current genome-sequencing projects of any significant scale. Despite all these grand advantages, there are limitations in this method, which could be complemented with other techniques. Among the current state-of-the-art DNA-sequencing techniques, pyrosequencing [2, 3] has emerged, which is being used for a wide variety of applications. In the beginning, the method was only restricted to SNP genotyping [4] and short reads [5, 6] when it was introduced in 1997 but it is now being used for broader applications. The original pyrosequencing method is based on conventional PCR and a four-enzyme system sequencing 96 samples at a time (http://www.biotage.com). Later on, this method was developed further to a high-throughput micorfluidics format by 454 Life Sciences (http://www. 454.com), which was acquired by Roche recently. Several groups are working on further development of this technology for different applications, which will be discussed in this chapter.
2.2 Pyrosequencing Chemistry Pyrosequencing technology is based on the sequencing-by-synthesis principle and employs a cascade of four enzymes to accurately determine nucleic acid sequences during DNA synthesis. In pyrosequencing, the sequencing primer is hybridized to a single-stranded biotin-labeled DNA template (post-PCR alkali treated) and mixed with the enzymes: DNA polymerase, ATP sulfurylase, luciferase and apyrase, and the substrates adenosine 5’ phosphosulfate (APS), luciferin and deoxynucleotide triphosphates (dNTPs). Cycles of four dNTPs are separately dispensed to the reaction mixture iteratively. After each nucleotide
Array-Based Pyrosequencing Technology
17
dispensation, DNA polymerase catalyzes the incorporation of complimentary dNTP into the template strand. Each nucleotide incorporation event is followed by release of inorganic pyrophosphate (ppi) in a quantity equimolar to the amount of incorporated nucleotide. ATP sulfurylase quantitatively converts ppi to ATP in the presence of APS. The generated ATP drives the luciferase-mediated conversion of luciferin to oxyluciferin, producing visible light in amounts that are proportional to the amount of ATP. The light in the luciferase-catalyzed reaction is then detected by a photon-detection device such a charge-coupled device (CCD) camera, CMOS image sensor, or photomultiplier tube. The generated light is observed as a peak signal in the pyrogram or flowgram (corresponding to electropherogram in dideoxy sequencing). Each signal peak is proportional to the number of nucleotides incorporated (e.g., a triple dCTP nucleotide incorporation generates a triple higher peak). Apyrase is a nucleotidedegrading enzyme, which continuously degrades ATP and nonincorporated dNTPs in the reaction mixture. There is a certain time interval between each nucleotide dispensation to allow complete degradation. For this reason, dNTP addition is performed one at a time. During this synthesis process, the DNA strand is extended by complementary nucleotides, and the DNA sequence is demonstrated by the signal peaks in a pyrogram on a computer monitor. Base-callings are performed with integrated software with features for related SNP and sequencing analysis. Pyrosequencing was earlier limited to sequencing of short stretches of DNA, due to the inhibition of apyrase. The natural dATP was a substrate for luciferase, resulting in false sequence signals. dATP was substituted by dATP-α-S [2]. Higher concentrations of this nucleotide had an inhibitory effect on apyrase catalytic activity, causing nonsynchronized extension. The dATP-α-S consisted of two isomers: Sp and Rp. The Rp isomer was not incorporated in the DNA template as it was not a substrate for DNA polymerase, and its presence in the sequencing reaction simply inhibited apyrase activity. By introducing the dATP-α-S SP isomer, substantial longer reads were achieved [7]. This improvement had a major impact on pyrosequencing read-length and allowed sequencing of over one-hundred bases and opened many avenues for numerous applications.
2.3 Array-Based Pyrosequencing Pyrosequencing has been developed into a massively parallel microfluidic sequencing platform [8] by 454 Life Sciences Corporation (Branford, Connecticut). The first generation of 454 sequencing platform (GS20) is capable of sequencing 100 bases in average and generates between 20 to 50 megabases (depending on the protocol) of raw DNA sequence in less than 5 hours. The
18
Genome Sequencing Technology and Algorithms
company has recently released a GS FLX platform, which enables longer reads of 200–300 bases generating over 100-megabases per run. Based on the same platform, read-length distribution around 500 nucleotides has also been achieved. This read-length will open the doors for direct shotgun sequencing of complex genomes circumventing laborious library construction for de novo genome sequencing.
2.4 454 Sequencing Chemistry The 454 sequencing method uses a three-enzyme pyrosequencing chemistry in a microfluidic format (apyrase is not used except in the washing buffer). The detection enzymes are immobilized on beads and the substrates luciferin, APS, and nucleotides are flowed into the system. For sequencing of large fragments and whole genome, 454 sequencing consist of four steps. 1. Library preparation where whole-genomic DNA or large fragments (usually over 2 kb) are nebulized into small fragments preferably with majority in the 300–800 bp range by high nitrogen gas pressure. The fragmented DNA is then blunt-ended and polished by DNA end repair for adapter ligation. There are two 44-mer double-stranded adapters that are blunt-ended on one side and consist of 20-bases PCR primer, 20-bases sequencing primer, and 4-base key sequences (for initial sequence quality monitoring) with one of the adapters biotin-labeled. The adapters provide sequences for both amplification and sequencing of the immobilized DNA fragments. After ligation and nick repair, the nonbiotin labeled fragments are separated, single stranded by alkali treatment and used as DNA library. 2. The second step is emulsion PCR, where the ssDNA library is hybridized to complementary strand immobilized on sepharose capture beads and distributed to water-in-oil emulsion and PCR reaction mixture, which are then mixed by a high-speed shaker to form emulsions. The theoretical distribution ratio of beads and ssDNA is 1:1 for the clonal amplification. After the PCR reaction, the microreactors are broken and the beads are captured by filtration. The biotin-labeled amplicon positive beads are then enriched by using streptavidin magnetic beads and are single stranded. 3. Sequencing step where the ssDNA positive beads (23 µm in diameter) are incubated with DNA polymerase and single-strand binding protein (SSB), after that distributed into the wells on an optical faceplate called PicoTiterPlate, which contains 1.6 million wells (each well is 44 µm in diameter and has the capacity for one bead). After adding
Array-Based Pyrosequencing Technology
19
the DNA beads and enzyme beads (ATP sulfurylase and luciferase), the packing beads are layered onto the wells and the plate is centrifuged for bead deposition. The packing beads ensure that the DNA beads are kept in place during DNA sequencing and minimize DNA bead loss during the liquid flow. The PicoTiterPlate is placed into the instrument for sequencing. 4. Generated sequence signals are recorded as images for data analysis. The signal processing, base-callings, assembly, mapping, and variance detections are performed by integrated software. For amplicon sequencing there is no need for library preparation and adapter ligation. Instead 19-mer sequences are added to the PCR primers, which function as amplification and sequencing primers. Amplicons can be sequenced one-directional or bidirectional.
2.5 Applications of 454 Sequencing Technology The 454 sequencing technology is the only commercially available technology that can be used for high-throughput de novo sequencing generating readlength as long as 200–300 bases with a 500-base-sequencing platform in the pipeline. The method can generally be categorized for whole-genome sequencing, broad sequencing, and deep sequencing. 2.5.1
Whole-Genome Sequencing
454 sequencing has been used widely for whole-genome sequencing generally for short genomes such as de novo bacterial [9–11] and BAC/PAC/cosmid/ forsmid [12, 13] sequencing basically because of their ease of assembly. Due to high number of sequence repeat regions in mammalian genomes, the 100-base GS 20 has not been as suitable as Sanger sequencing for complex genomes. The 454 longer read platform FLX (and the coming generation producing 500 bases) along with paired-end technology [14] and its upcoming improvements are making this technique suitable for sequencing complex genomes. The 454 sequencing is now being used for evolutionary anthropology by The Max Planck Institute to sequence Neanderthal genome [15, 16], which is one of the closest to human genome. The sequencing of the ancient Neanderthal genome is specially challenging as it is highly fragmented, which has just been enabled by pyrosequencing. This sequencing project is currently being taken place at the 454 Sequencing Center. Moreover, the whole human genome of a Nobel Prize–winning scientist is also being sequenced at the same center.
20
2.5.2
Genome Sequencing Technology and Algorithms
Ultrabroad Sequencing
The 454 sequencing is now currently being utilized for many different applications such as large pools of cDNA [17–19], small RNA, and micro-RNA [20–23], ditag/SAGE libraries [14, 24] as well as other amplicon pools [25], paleogenomics and metagenomics [26–29]. Moreover, using DNA tags or barcodes [30] could be a great advantage in reducing the cost of sequencing, which allows en masse sequencing of pooled amplicons from different samples. By using bioinformatic tools one can easily sort out the amplicon sequences by the identification tags or barcodes.
2.5.3
Ultradeep Amplicon Sequencing
The ultradeep sequencing allows detection of low-frequency mutations [30–32]. This is generally not possible by conventional Sanger sequencing as it can only detect mutations down to 20%. Screening the low-frequency mutations is important for many studies such as drug resistance or antibiotic resistance as well as finding novel mutations in heterogeneous samples.
2.6 Advantages and Challenges The 454 sequencing technology is the only commercially available high-throughput sequencing platform for de novo sequencing with lower cost than Sanger sequencing. It relies on clonal amplification, which allows sequencing of unclonable regions. Moreover, GC content is generally not an issue in pyrosequencing [33]. It has the ability to detect low-frequency mutations, which cannot be detected by Sanger sequencing [32]. Detection of low-frequency mutations is a valuable tool for clinical cancer and drug-resistance research. The 454 sequencing has been limited to average sequences of 100-bases read-length, however, by the new developments in chemistry and software algorithms, the read-length is being expanded to 500 bases. This will facilitate sequencing of highly repetitive regions and complex genomes with the ability to assemble the “left-out” contigs. Homopolymers are the main challenge affecting the accuracy of the 454 sequencing technology. The main challenge is caused by dATP-α-S when incorporated in homopolymer Ts (more than 4 to 5). Homopolymer strings (mainly homopolymeric T) regions can reduce synchronized extension causing nonuniform sequence peak heights, affecting the read-length and possibly causing sequence errors [7]. This problem could be resolved by engineering more efficient DNA polymerases or a luciferase that does not recognize natural dATP as a substrate.
Array-Based Pyrosequencing Technology
21
2.7 Future of Pyrosequencing While pyrosequencing chemistry will be improved to extend the read-length, progress in detection, microfluidics, and base-calling will be critical for further advancement of this technology for different applications at low cost. In addition, upstream processes should be integrated to reduce the cost, shorten the time for sample preparation and minimize human intervention for accurate pyrosequencing. Currently the cost of the machine is about $500,000 and sequencing of mammalian-size genome would cost more than $2 million. Both the cost of instrumentation and reagents should decrease by tenfold and a hundredfold, respectively. Our group has been working on developing methodologies, which could dramatically reduce instrumentation cost. More specifically, we have developed a new detection scheme based on CMOS image sensor [34], which uses standard semiconductor manufacturing techniques, with higher sensitivity than CCD-camera operating at room temperature with a 2-V battery. Furthermore, analog-to-digital conversion and digital signal processing units have been integrated with image sensor to maximize the efficiency of detection. We have integrated this CMOS system with the fluidics to successfully pyrosequence mixtures of PCR products. As CMOS can be customized and offers high sensitivity, there is room for further miniaturization. A 9-megapixel CMOS has now been designed which would enable sequencing of 9 million reaction wells simultaneously. Sequencing 500 nucleotides with an overall 60% efficiency of the system would potentially produce ∼1× of mammalian genome in a single run. As this integrated system is very compact, a superscalar version of such device containing 20 chips can be envisioned for even more high-throughput settings. For lower throughput version of pyrosequencing, Advanced Liquid Logic, Inc., (http://www.liquid-logic.com), has implemented digital microfluidics based on electrowetting to perform pyrosequencing on a flat chip. Sample preparation including PCR and DNA immobilization can potentially be performed on the sequencing chip. The chip is fully programmable enabling various sequencing applications on the same platform. This device could serve for diagnostics, point-of-care, and biodefence applications. In conclusion, we believe that pyrosequencing technology is scalable and can be further miniaturized. A cost of $10,000 per de novo mammalian genome could be available within the next 5 to 7 years.
References [1]
Sanger, F., S. Nicklen, and A. R. Coulson, “DNA Sequencing with Chain-Terminating Inhibitors,” Proc. Natl. Acad. Sci. USA, Vol. 74, 1977, pp. 5463–5467.
22
Genome Sequencing Technology and Algorithms
[2] Ronaghi, M., et al., “Real-Time DNA Sequencing Using Detection of Pyrophosphate Release,” Analytical Biochemistry, Vol. 242, 1996, pp. 84–89. [3] Ronaghi, M., M. Uhlen, and P. Nyren, “A Sequencing Method Based on Real-Time Pyrophosphate,” Science, Vol. 281, 1998, pp. 363, 365. [4] Ahmadian, A., et al., “Single-Nucleotide Polymorphism Analysis by Pyrosequencing,” Analytical Biochemistry, Vol. 280, 2000, pp. 103–110. [5] Gharizadeh, B., et al., “Typing of Human Papillomavirus by Pyrosequencing,” Lab Invest., Vol. 81, 2001, pp. 673–679. [6] Nordstrom, T., et al., “Method Enabling Fast Partial Sequencing of cDNA Clones,” Analytical Biochemistry, Vol. 292, 2001, pp. 266–271. [7] Gharizadeh, B., et al., “Long-Read Pyrosequencing Using Pure 2’-Deoxyadenosine-5’-O’(1-Thiotriphosphate) Sp-Isomer,” Analytical Biochemistry, Vol. 301, 2002, pp. 82–90. [8] Margulies, M., et al., “Genome Sequencing in Microfabricated High-Density Picolitre Reactors,” Nature, Vol. 437, 2005, pp. 376–380. [9] Goldberg, S. M., et al., “A Sanger/Pyrosequencing Hybrid Approach for the Generation of High-Quality Draft Assemblies of Marine Microbial Genomes,” Proc. Natl. Acad. Sci. USA, Vol. 103, 2006, pp. 11240–11245. [10] Hofreuter, D., et al., “Unique Features of a Highly Pathogenic Campylobacter Jejuni Strain,” Infect Immun., Vol. 74, 2006, pp. 4694–4707. [11] Oh, J. D., et al., “The Complete Genome Sequence of a Chronic Atrophic Gastritis Helicobacter Pylori Strain: Evolution During Disease Progression,” Proc. Natl. Acad. Sci. USA, Vol. 103, 2006, pp. 9999–10004. [12] Moore, M. J., et al., “Rapid and Accurate Pyrosequencing of Angiosperm Plastid Genomes,” BMC Plant Biol., Vol. 6, 2006, p. 17. [13] Wicker, T., et al., “454 Sequencing Put to the Test Using the Complex Genome of Barley,” BMC Genomics, Vol. 7, 2006, p. 275. [14] Ng, P., et al., “Multiplex Sequencing of Paired-End Ditags (MS-PET): A Strategy for the Ultra-High-Throughput Analysis of Transcriptomes and Genomes,” Nucleic Acids Res., Vol. 34, 2006, p. e84. [15] Green, R. E., et al., “Analysis of One Million Base Pairs of Neanderthal DNA,” Nature, Vol. 444, 2006, pp. 330–336. [16] Noonan, J. P., et al., “Sequencing and Analysis of Neanderthal Genomic DNA,” Science, Vol. 314, 2006, pp. 1113–1118. [17] Cheung, F., et al., Sequencing Medicago Truncatula Expressed Sequenced Tags Using 454 Life Sciences Technology,” BMC Genomics, Vol. 7, 2006, p. 272. [18] Emrich, S. J., et al., “Gene Discovery and Annotation Using LCM-454 Transcriptome Sequencing,” Genome Res., Vol. 17, 2007, pp. 69–73. [19] Weber, A. P., et al., “Sampling the Arabidopsis Transcriptome with Massively-Parallel Pyrosequencing,” Plant Physiol., 2007.
Array-Based Pyrosequencing Technology
23
[20] Axtell, M. J., et al., “A Two-Hit Trigger for siRNA Biogenesis in Plants,” Cell, Vol. 127, 2006, pp. 565–577. [21] Girard, A., et al., “A Germline-Specific Class of Small RNAs Binds Mammalian Piwi Proteins,” Nature, Vol. 442, 2006, pp. 199–202. [22] Lu, C., et al., “MicroRNAs and Other Small RNAs Enriched in the Arabidopsis RNA-Dependent RNA Polymerase-2 Mutant,” Genome Res., Vol. 16, 2006, pp. 1276–1288. [23] Pak, J., and A. Fire, “Distinct Populations of Primary and Secondary Effectors During RNAi in C. Elegans,” Science, Vol. 315, 2007, pp. 241–244. [24] Nielsen, K. L., A. L., Hogh, and J. Emmersen, “DeepSAGE—Digital Transcriptomics with High Sensitivity, Simple Experimental Protocol and Multiplexing of Samples,” Nucleic Acids Res., Vol. 34, 2006, p. e133. [25] Albert, I., et al., “Translational and Rotational Settings of H2A.Z Nucleosomes Across the Saccharomyces Cerevisiae Genome,” Nature, Vol. 446, 2007, pp. 572–576. [26] Edwards, R. A., et al., “Using Pyrosequencing to Shed Light on Deep Mine Microbial Ecology,” BMC Genomics, Vol. 7, 2006, p. 57. [27] Krause, L., et al., “Finding Novel Genes in Bacterial Communities Isolated from the Environment,” Bioinformatics, Vol. 22, 2006, pp. e281–e289. [28] Sogin, M. L., et al., “Microbial Diversity in the Deep Sea and the Underexplored ‘Rare Biosphere,’” Proc. Natl. Acad. Sci. USA, Vol. 103, 2006, pp. 12115–12120. [29] Turnbaugh, P. J., et al., “An Obesity-Associated Gut Microbiome with Increased Capacity for Energy Harvest,” Nature, Vol. 444, 2006, pp. 1027–1031. [30] Binladen, J., et al., “The Use of Coded PCR Primers Enables High-Throughput Sequencing of Multiple Homolog Amplification Products by 454 Parallel Sequencing,” PLoS ONE, Vol. 2, 2007, p. e197. [31] Thomas, R. K., et al., “Sensitive Mutation Detection in Heterogeneous Cancer Specimens by Massively Parallel Picoliter Reactor Sequencing,” Nat. Med., Vol. 12, 2006, pp. 852–855. [32] Wang, C., et al., “Characterization of Mutation Spectra with Ultra-Deep Pyrosequencing: Application to HIV-1 Drug Resistance,” Genome Res., Vol. 17, No. 8, August 2007, pp. 1195–1201. [33] Ronaghi, M., et al., “Analyses of Secondary Structures in DNA by Pyrosequencing,” Analytical Biochemistry, Vol. 267, 1999, pp. 65–71. [34] Eltoukhy, H., K. Salama, and A. El Gamal, “A 0.18µm CMOS Luminescence Detection Lab-on-Chip,” IEEE Journal of Solid State Circuits, Vol. 41, 2004, pp. 651–662.
3 The Role of Resequencing Arrays in Revolutionizing DNA Sequencing David Okou and Michael E. Zwick
3.1 Introduction Genomics technologies that enable rapid, accurate, and cost-effective DNA sequencing promise to revolutionize genetic research. At the same time, these technologies will usher in a new era of patient care, with an increasing focus on predictive health and individualized genomic medicine. The Human Genome Project’s (HGP) resounding success [1] and its numerous innovations [2], combined with the pressure of direct competition from a commercial company [3], have fostered an environment in which ever-greater quantities of DNA are being sequenced at an ever-decreasing cost [4]. Yet all scientific revolutions tend to change the research landscape in unanticipated ways, and the HGP is no exception. While remarkably efficient, the costs, infrastructure, and personnel required to maintain a traditional, large-scale industrial DNA-sequencing center that uses gel electrophoresis and Sanger-sequencing chemistry may not be scalable to the degree necessary to meet future research and medical application needs [4]. Consequently, the focus of genomics is shifting to a number of exciting new technologies that offer drastic cost reductions, while at the same time dramatically increasing data production [4]. A characteristic these technologies share, and one not often factored into cost-reduction estimates, is that their space, personnel, and infrastructure requirements are a fraction of those
25
26
Genome Sequencing Technology and Algorithms
necessary for the traditional industrial model. Therefore, the prospect of a genome-sequencing center in every lab is increasingly within reach. Resequencing arrays (RAs) are one example of a next generation DNA sequencing technology that can enable individual laboratories to generate vast quantities of genome sequence rapidly and in a cost-effective fashion. This chapter first provides an overview of how RAs determine a DNA sequence. A discussion of basic experimental protocols and methods of RA data analysis follows. Finally, the chapter concludes with a review of several diverse studies that demonstrate how RAs can be employed for DNA sequencing.
3.2 DNA Sequencing by Hybridization with Resequencing Arrays The term “resequencing” refers to the act of sequencing a gene, genomic region, or genome in multiple different individuals in order to identify genetic variation. Resequencing arrays accomplish this task by hybridizing target DNA from a single individual to a set of custom-designed oligonucleotide probes located on a solid surface. When target DNA is hybridized to a RA, interactions with complementary probe oligonucleotides act either to query the identity of a given base (haploid) or to determine a genotype (diploid), depending on the target DNA source. With a high-quality genome reference sequence in hand, RAs can be custom-designed to resequence the unique genomic sequences of any organism. The great power of this approach arises from the fact that high-density oligonucleotide (oligo) RAs possess a very large number of oligos and can be processed by a single individual within a single laboratory [5, 6]. RAs query a given base by using overlapping oligonucleotide probes, tiled at a 1-base-pair (bp) resolution. The oligonucleotide probes, referred to as features, are typically 25–base-pairs long. Both the forward and reverse strands are interrogated, so sequencing a single base requires a total of 8 features. A set of four features contains oligonucleotides identical to the forward reference strand, except at position 13 (the base to be queried), where there is either A, C, G, or T. The remaining four features are similarly designed for the complementary strand (Figure 3.1). When a labeled DNA sample, called a target, is hybridized to these eight features on the array, the two features complementary to the reference sequence (forward and reverse complement) will yield the highest signal. If, however, the target DNA contains a variant base at position 13, the two features complementary to that variant base will yield the highest signal (Figure 3.2). Given eight features for each base, interrogation of an L-length duplex strand would require 8L oligonucleotide probes. Two companies currently manufacture high-density oligonucleotide RAs: Affymetrix, Inc. and NimbleGen Systems, Inc. Affymetrix’s GeneChip technology uses a series of masks and photolithography to manufacture microarrays
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing
27
Reference genomic DNA
Probes tiled at 1-bp resolution
Probe features Synthesized on RA
Reference sequence Base queried
Figure 3.1 A description of the concept and design of resequencing arrays.
Genome
Haploid
Diploid
Target DNA: production and fragmentation
RA hybridization, wash, scan Probes
Probes
Fwd Rev
Data analysis (ABACUS)
Fwd Rev
A C G
A C G
T
T
Haploid Base call: A
Diploid Genotype: A/G
Figure 3.2 Overview of the basic resequencing array protocol.
containing oligos with a length of 25 bp [7]. The current commercially available RAs with an 8-micron feature size contain about 2.4 million distinct oligos. These RAs can resequence approximately 300 kb per chip (2.4 million 8-micron features/eight features per queried base). Because Affymetrix’s technology synthesizes oligos on entire wafers that are subsequently broken into individual RAs, a typical order of 45 chips can resequence up to 13.5 megabases (Mb). The small feature size and concomitant high density of Affymetrix RAs is an appealing strength of their platform. NimbleGen Systems, Inc., on the other hand, uses maskless photolithography to manufacture microarrays that contain about
28
Genome Sequencing Technology and Algorithms
385,000 16-micron features [8]. These RAs can resequence approximately 48 kb per chip. There are two advantages to the Nimblecen Systems approach: they can manufacture single arrays, and they can put oligos of different lengths on a single chip. Oligos of different lengths on a single RA enable more precise matching of melting temperatures between target and probe DNA. Regardless of the RA manufacturer, decreasing probe feature size and increasing microarray density is a very fertile area for research and development, and in all likelihood, further progress in these areas will continue to enhance RA capabilities.
3.3 Resequencing Array Experimental Protocols RAs generate the highest quality data when target DNA sequences that correspond to the complementary probe oligos are unique [5, 6]. Common bioinformatics procedures that identify repetitive sequences underlie RA design, regardless of the targeted organism. Unique DNA sequences can be readily identified and obtained from publicly available DNA sequence repositories using tools like the UCSC Genome Bioinformatics site [9]. Also, genome repeat masking (i.e., RepeatMasker, available at http://www.repeatmasker.org/) is another good alternative. RepeatMasker identifies and masks common repetitive sequences and simple sequence repeats [10]. The unique sequences that remain are then candidates for RA probe selection. In order to use RA space most efficiently, a typical design requires that unique sequences be longer than 50 bp to be tiled on the microarray, while repetitive sequences should be longer than 50 bp to be excluded. However, these guidelines can be relaxed or tightened depending on the specific RA application. This approach is employed because, during RA synthesis, the first and last 12 bases of each unique sequence fragment are not full-length (25-bp) oligos on the chip; hence they do not provide useful base-calling information. These oligos do, however, take up space on the RA, thereby reducing the total number of bases that can be resequenced. Once the desired unique sequences have been identified, they are placed in a flat text multi-FASTA file (each unique fragment is in a separate FASTA text block) that is provided to the chip manufacturer. The RAs are then manufactured as discussed previously. The greatest technical challenge posed by resequencing with RAs lies in isolating target DNA. RAs can resequence either haploid or diploid target DNA. In both cases, the methods of target DNA isolation are identical. Target DNA from relatively simple microbial genomes can be obtained either by using long PCR (LPCR) of selected genomic regions [6] or, even more simply, via whole-genome amplification (WGA) of the entire genome. Larger, more complex eukaryotic genomes present a more significant challenge. LPCR is currently the preferred method of target DNA production and has been used in a project
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing
29
that generated 160 MB of human genomic sequence. LPCR target DNA products are quantified and pooled by individual for a given chip design. A modern robotic infrastructure can further automate this process, but scaling this process while simultaneously amplifying the majority of the target genome sequences (>90%) is a significant obstacle. How to improve methods of target DNA production from complex eukaryotic genomes is an active area of research. Clone-based methodologies are a promising approach that may be more scalable [11, 12], although these methods still require substantial effort and quality control in the course of isolating target DNA products. Isolated target DNA requires processing prior to RA hybridization. The first step is to fragment the target DNA to products that are 20 to 200 bases long. This is typically performed enzymatically using DNAse I and should be followed by gel confirmation of digestion. This step in the experimental protocol is critical, since target DNA overdigestion and underdigestion both lead to poor RA performance. After digestion, the target DNA fragments are labeled and then hybridized to the RA overnight. The chip is then washed and scanned, which generates a high-definition image of the RA. At this point, the chip image is ready to be analyzed.
3.4 Analyzing Resequencing Array Data with ABACUS Determining the DNA sequence from a RA requires analysis of the chip image for each queried base. Initial studies using high-density oligonucleotide microarrays used for single nucleotide polymorphism (SNP) discovery and genotyping relied on manual examination and visual inspection of the chip images by the human eye [13–20]. While these initial studies held out great promise, they also suffered from major shortcomings. The reliance on human inspection of each chip was inherently not scalable, was subject to variation among individual viewers, and tended to bias the resulting base (haploid target) and genotype (diploid target) calls. For example, human inspectors tended to identify common SNPs more often than rare SNPs. Equally problematic, the initial large-scale microarray experiments reported SNP false-positive detection rates between 12% and 45% [19, 21]. While these numbers certainly seemed high, because each chip scans a large number of sites, these initial experiments suggested that microarray-based variation detection and genotyping in fact achieves an accuracy between 99.93% and 99.99% [19–21]. The paradox of high false-positive SNP detection rates paired with seemingly high RA accuracy exposes a significant problem that faces any resequencing technology [5]. A simple thought experiment can clarify this situation. If we propose a hypothetical technology that can determine the sequence of bases with an accuracy of 99.9%, then we would expect to observe 10 errors
30
Genome Sequencing Technology and Algorithms
for every 10,000 bases resequenced. Naturally occurring rates of genetic variation in populations of virtually any organism one can examine are relatively low; thus, most resequenced bases are monomorphic. For example, in humans, the average level of variation is about eight differences per 10,000 bases [22]. Hence, if we resequence 10,000 bases with our 99.9% accurate resequencing technology, we would expect to identify eight true variants and make ten errors. This corresponds to an SNP false-positive detection rate of 55%, a result that demonstrates the need for all resequencing technologies to have very high accuracy in order to detect the generally rare but quite real genetic variants found in genomes. The conundrum of high RA error rates combined with the reliance on human visual inspection hinted that RAs might prove inadequate as an effective resequencing technology. To address these challenges, researchers developed ABACUS (Adaptive Background genotype calling scheme) [5]. ABACUS is an objective statistical framework designed to distinguish base (haploid target)/genotype (diploid target) calls, which can be made with extraordinary accuracy, from those that are less reliable. Because RAs are extraordinarily accurate on the vast majority of queried bases, significantly increasing RA data accuracy becomes possible. Furthermore, the analysis is automated and does not require any human visual inspection of the chip images. ABACUS assigns a quality score to every base/genotype call that corresponds to the level of support at each resequenced base. This approach is similar to the one undertaken for traditional DNA sequencing [23, 24]. To assess data quality, both replicate experiments and accuracy estimates are performed. RA data has been shown to be highly reproducible in replicate experiments consisting of independent amplification of identical samples followed by hybridization to distinct microarrays of the same design [5]. In an autosomal (diploid target) replicate experiment, 813,295 out of 813,295 genotypes were called identically (including 351 heterozygotes); at X-linked loci in males (haploid target), 841,236 out of 841,236 sites were called identically. If repeatability could be equated to accuracy, then this level of repeatability in haploid and diploid genotype calls would correspond to a phred score of at least 54 (assuming a binomial error probability of P; in relating P-values to phred scores, note that phred = −10 log10P) [23, 24]. Although repeatability can certainly suggest accuracy, it is also possible that systematic but repeatable errors might remain undetected. Therefore, using independent resequencing/genotyping technologies, accuracy was also assessed via two separate means. For haploid target data, a 6x-shotgun resequencing on a single individual sample yielded 17,423 base calls that were identical to the ABACUS calls. To assess the accuracy at segregating sites in diploids (nonsegregating sites identical to the reference are exceedingly likely to be correct, since overall polymorphism rates are so low), 1,938 genotypes were
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing
31
obtained at 108 segregating sites. The accuracy of diploid genotypes at segregating autosomal sites was confirmed for 1,515 of 1,515 homozygous calls, and for 420 out of 423 (99.29%) heterozygotes [5]. These results indicated that genotyping accuracy at segregating sites was greater than 99.8% (and this of course does not take into account the nonsegregating sites also likely to be called correctly). A subset of these SNPs was investigated to assess the accuracy of SNP detection: 108 out of 108 SNPs were experimentally confirmed, and an additional 371 SNPs were confirmed electronically. This indicated that RAs can be used for both detection and genotyping of variation simultaneously, and that the base-calling accuracy reaches or exceeds most other widely available stand-alone technologies. Furthermore, because ABACUS provides a quality score for individual bases (haploid targets)/genotypes (diploid targets), investigators can focus attention on those sites providing accurate information. Haploid quality scores, which are those relevant to resequencing X-chromosome loci in human males and microbial genomes, for example, are higher on average than those for diploid data (Figure 3.3). RAs can also detect insertion/deletion (indel) variation in haploid targets. Currently, ABACUS is not designed to detect indel variation in diploid targets. This initial application of ABACUS demonstrated greater than 99.9999% accuracy on more than 80% of the genotype calls in a 7%
6%
Percent of total bases resequenced
Diploid Haploid 5%
4%
3%
2%
1%
0% 5
25
45
65
85
105 125
145
165
185
205
225 245 265
285
305
Quality score (log10)
Figure 3.3 Quality score (log10) distribution for haploid and diploid resequenced bases [5].
32
Genome Sequencing Technology and Algorithms
single experiment using Affymetrix RAs [5]. This work established that RAs could be an effective resequencing platform. Improving the overall call rate above 80% for single experiments then became a priority. After scanning a RA, the first step in data analysis is determining the position of features on the chip. This process is called grid alignment. Grid alignment is followed by the extraction of the raw data from each RA image that is subsequently used for base calling by ABACUS. When ABACUS was developed, grid alignment required manual intervention by a laboratory technician, who would determine the positions of the four corners of a grid by eye. The single grid placed by the technician encompassed the entire RA image, effectively assuming a “globally perfect” grid alignment. Once the grid was placed over the RA image, the intensity data could then be extracted for analysis by ABACUS. This process, in addition to being laborious, led to varying degrees of misalignment on portions of (and in some cases, entire) RAs. Data extracted from RAs with misaligned grids raised error rates. Increasing the quality score threshold could eliminate errors, but at the cost of reduced rates of base/genotype calling. The problems associated with manual grid alignment were eventually solved by software that performs automated grid alignment on RA image files [D. J. Cutler and M. Zwick, personal communication, 2006]. The software makes no “globally perfect” assumption, but instead assumes a locally perfect alignment. Micromisalignments, when undetected, can correspond to very weak heterozygotes when resequencing diploid targets. These errors are minimized with a locally perfect method of grid alignment. Figure 3.4 provides an example of the way local grid alignment can improve data quality. At the same time, automated grid alignment allowed for a reduction of the quality score threshold, increasing call rates to more than 90% of sites. Currently, automated grid alignment followed by ABACUS base calling requires less than 1 minute per Global grid alignment
Local grid alignment
Figure 3.4 Local grid alignment (right) extracts RA data more accurately than global grid alignment (left).
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing
33
microarray on a standard desktop computer. All of these tools have been implemented in a free, open-source software package called RATools, which is publicly available at http://www.dpgp.org/RA/ra.htm. RATools works equally well with RAs manufactured by Affymetrix or Nimblecen Systems, Inc.
3.5 Review of RA Applications Resequencing arrays have been used successfully in a variety of systems and projects. As this new technology advances, an increasingly diverse collection of RA projects has ensued. Here we review a few select applications of RA technology. 3.5.1
Human Resequencing
High-throughput RAs were applied to an experiment encompassing 32-autosomal and eight X-linked genomic regions, each consisting of approximately 50 kb of unique sequence spanning a 100-kb region, in 40 humans [M. Zwick, personal communication, 2007]. The regions resequenced included unique coding and noncoding sequences. Long PCR was used to generate target DNA for RA hybridization. Using thresholds identical to those described previously, approximately 1.6 MB of DNA sequence was determined for each of the 40 individuals. In total, 6,040 SNPs were identified, corresponding to human genetic variation levels determined by other sequencing technologies. The SNPs that were discovered consisted of both common and rare variants. A pronounced excess of rare variants, relative to the number predicted by the neutral theory, was observed in the genomic regions resequenced. These data demonstrated that the RAs can be a viable resequencing platform that is capable of identifying both common and rare SNPs in large-scale resequencing projects focused on complex eukaryotic genomes. 3.5.2
Mitochondrial DNA Resequencing
Mitochondrial DNA mutations are commonly found in cancers, but until recently, strategies for using the mitochondrial genome as a cancer-screening tool were limited by the lack of a high-throughput platform for mutation detection. Maitra et al. [25] used a RA to rapidly sequence the human mitochondrial genome in order to detect mutations linked to cancers. The first generation of the MitoChip (v1.0, released in 2004) could sequence more than 29 kb of double-stranded DNA in a single assay. Both strands of the entire human mitochondrial coding sequence (15,451 bp) were arrayed on the MitoChip; both strands of an additional 12,935 bp (84% of coding DNA) were also arrayed in duplicate. Using ABACUS and a total threshold quality score of 30 [5], the Affymetrix GeneChip DNA Analysis software successfully assigned base calls at
34
Genome Sequencing Technology and Algorithms
96.0% of nucleotide positions [25]. Replicate experiments demonstrated more than 99.99% reproducibility of base calls both within and between chips using array-based sequencing (Table 3.1). There were no significant differences in the percentage of genotype calls among mitochondrial DNA extracted from lymphocytes, cell lines, primary tumors, or body fluids. The second generation MitoChip (v2.0 released in 2006) has a smaller feature size (50 kb of sequence, compared to 32 kb) and includes redundant tiling features, enabling researchers to detect potential insertion-deletion mutations and nearly three-dozen variations in the noncoding D-loop region. These regions were not directly detectable using the original MitoChip [26]. Using RAs to resequence mitochondrial genomes accomplished three key objectives. First, the number of polymerase chain reactions (PCR) required to sequence the entire mitochondrial DNA was reduced to three (from 20 to 40 individual reactions). Second, the amount of starting template needed was reduced to just 10 nanograms (100 nanograms cited [25]). And finally, sequencing the entire mitochondria on a single chip eliminates the need to visually inspect traditional chromatograms. The ability of array-based mitochondrial genome resequencing to detect mitochondrial mutations in samples of body fluids obtained from cancer patients attests to its promise as a tool for the early detection of cancer and other disorders in human clinical samples.
Table 3.1 Summary of Replicate Experiments Total samples analyzed in replicate
13
Total samples analyzed for replicate experiments
26
Within chip reproducibility Mitochondrial base pairs tiled in duplicate per chip
12,935 bp
Total within-chip duplicate base pairs analyzed
26*12,935 = 336,310 bp
Total within-chip duplicate base pairs called
311,814 bp (92.71%)
Discordant called within chips
8 bp (0.0025%)
Between-chip reproducibility Total mitochondrial base pairs tiled per chip
28,386 bp
Total base pairs analyzed in one set of 13 chips
13*28,386 = 369,018 bp
Total base pairs assigned in first set of chips
350,010 bp (94.84%)
Total base pairs assigned in second set of chips
355,086 bp (96.22%)
Total base pairs assigned in both sets
345,094 bp (93.51%)
Discordant bases calls between chips
10 bp (0.0028%)
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing 3.5.3
35
Microbial Pathogen Resequencing
RAs can be a rapid, cost-effective, and efficient platform for rapidly resequencing microbial and viral genomes or genomic regions. Three recent studies have made use of RAs to resequence genomic regions from multiple strain isolates (Bacillus anthracis), viral genomes (SARS virus), and portions of microbial and viral genomes from human clinical samples, as discussed later. 3.5.3.1 Anthrax Resequencing (Bacterial Pathogens)
After the pathogen Bacillus anthracis was employed in the 2001 bioterror attacks in the United States, RAs were used to characterize genetic variations from multiple B. anthracis strains [6]. B. anthracis has two characteristics that make it an ideal system for RA-based resequencing. First, the B. anthracis genome consists of a main circular chromosome and two plasmids (pXO1, pXO2) that are approximately 5.2 MB in size. The relatively small size of microbial genomes allows for rapid target DNA isolation. While target DNA was generated using LPCR [6], subsequent work demonstrated that WGA on higher-density RAs works equally well [M. Zwick, personal communication, 2007]. Second, the ABACUS base-calling model for anthrax is haploid (the same as for the X chromosome in human males), and haploid base calls on RAs have higher-quality scores. A geographically diverse panel of 56 B. anthracis strains was resequenced using Affymetrix RAs, and base calls were determined with the RA Tools software package [6]. Each RA was capable of resequencing 29,212 bp, or about 0.5%, of the B. anthracis genome. Long PCR sample preparation and chip processing was conducted for 118 RAs. Analysis of these 118 RAs with the ABACUS software package showed that 115 were successful (97.5%). Experimental failure was declared when less than 60% of the total possible bases failed to achieve quality scores exceeding the ABACUS user-defined threshold. For that study, the total threshold was set at 31 with a strand minimum of −2 [5], as determined by analysis of a replication experiment. The successful RAs (115) called 92.6% of the possible bases (3,109,539 bp out of a total possible 3,359,380 bp). Bases with quality scores that failed to meet the minimum threshold stemmed from two primary causes. Amplicon failure, which typically arises from LPCR failure, accounted for 1.1% of the uncalled bases. The remaining uncalled bases were distributed nonrandomly across the RAs and were composed of oligonucleotide probes with a significantly higher purine composition (P<10−22). A similar pattern emerged in an analysis focused on guanine-rich probes (P<10−9). These analyses demonstrated that both purine-rich and guanine-rich oligonucleotide probes were significantly more likely to fail at generating quality scores exceeding the experimental threshold.
36
Genome Sequencing Technology and Algorithms
RA data quality was assessed by two methods [6]. The first consisted of a replicate experiment where 51 samples were independently hybridized on 102 RAs. Table 3.2 shows the results of this experiment. If repeatability could be related to accuracy, then this level of repeatability would correspond to a phred score of at least 61. Because repeated systematic errors would not be detected by a replicate experiment, the RA sequence data was compared to shotgun sequence data from the identical strains (Table 3.2, part B). A total of 15 discrepancies were observed. Making the conservative assumption that all observed errors arose from the RA data, then this level of accuracy would correspond to a phred score of at least 44. However, two lines of evidence suggested that such a conservative assumption was incorrect. First, at all discrepant sites, the RA called the base corresponding to the reference sequence, while the shotgun sequence called a SNP. Second, a closer examination of the sequence from a later assembly agreed with the RA base call at 14 of the 15 discrepant sites. The sole remaining discrepant site came from a single shotgun-sequencing read with a phred score of 7. Clearly, the shotgun coverage lacked sufficient depth at this site, and the RA base call seemed far more likely to be correct. Assuming that this is indeed the case, the observed level of sequencing accuracy corresponds to a phred score of 56. These data demonstrate that RA data quality from a single experiment matches, and in some cases may even exceed, the level obtained by multiple DNA sequencing reads generated by conventional DNA sequencing technologies. The study found no evidence of plasmid exchange or recombination altering the patterns of DNA sequence variation among B. anthracis strains in the regions that were resequenced. An excess of rare SNPs was observed. This pattern of B. anthracis genetic variation is consistent with expectations for a
Table 3.2 Assessing B. anthracis RA Data Quality A. Replication Experiment Total number of bases called in Replicate 1
1,383,229
Total number of bases called in Replicate 2
1,373,905
Total number of bases called in both replicates
1,349,177
Total number of bases called differently
1
Replication Experiment Discrepancy Rate
7.4E–07
B. Accuracy Estimation Experiment Total number of bases called identically
398,452
Total number of bases called differently
15
Accuracy Experiment Discrepancy Rate
3.8E–05
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing
37
bacterial species that has undergone a rapid, historically recent expansion from a single clone. This study demonstrated that high-throughput resequencing with RAs of multiple closely related strains could assist with studies aimed at the following goals: identifying a specific strain in environmental and clinical samples; determining forensic attribution and phylogenetic relationships of strains; and uncovering the genetic basis of phenotypic variation in traits such as mammalian virulence and antibiotic resistance. 3.5.3.2 SARS Resequencing (Viral Pathogens)
In April 2003 the Severe Acute Respiratory Syndrome (SARS) outbreak was attributed to the SARS coronavirus (SARS-CoV), a single-stranded RNA virus. Many point mutations among SARS-CoV genome sequences correlated closely with the SARS epidemic. These mutations can alter virulence and the therapeutic response of viral pathogens. To rapidly detect genetic variants in newly confirmed SARS cases and to further provide important clues to the geographic origins of infection, Wong et al. [27] used high-throughput RAs (NimbleGen Systems, Inc., Madison, Wisconsin) to resequence and track the evolution of the SARS coronavirus. With the aid of the ABACUS algorithm, the SARS-CoV resequencing chip repeatedly called greater than 99% of the bases and yielded highly accurate sequence (greater than 99.99%). Traditional ABI capillary sequencing (ACS) was used for independent confirmation to determine discordant calls (Table 3.3). In the table, ambiguous calls refer to those bases lacking sufficient information for high-confidence base assignment. The call rate is the percentage of genome sequence with high-confidence base calls. Accuracy is represented by the percentage of correctly called bases (as determined by ACS) over the total number of bases called (excluding any ambiguous calls). The rapid sequence turnaround time and high accuracy of the RA, coupled with its reasonable cost, make it an ideal platform for the global monitoring of any small-genome pathogen and its entire infected population. 3.5.3.3 Infectious Agent Detection
With mounting concern over the threats posed by bioterrorism and the spread of novel infectious diseases, the rapid diagnosis of infections in human clinical samples has become an increasingly high priority. RAs are one possible technology that could efficiently and rapidly detect these infectious agents. Furthermore, compared to other current state-of-the-art technologies, which require multiple diagnostic tests to identify the infectious agent, RAs could (at least in principle) disclose a wide variety of infectious agents in a single assay. This capability was demonstrated by Lin et al. in 2006. They used a respiratory pathogen RA to survey pathogen nucleic acid sequences from clinical samples [28], and ABACUS allowed them to obtain unambiguous, reproducible, and accurate results. This application of RAs and ABACUS not only resulted in the
38
Genome Sequencing Technology and Algorithms
Table 3.3 Call Rate and Accuracy of SARS Resequencing Array
Array Sequence
Discordant Calls
Ambiguous Calls (ns) Call Rate Accuracy
SIN2500
3
495
98.33%
99.989%
SIN2677
4
179
99.40%
99.986%
SIN2679
0
138
99.53%
SIN2748
2
223
99.22%
99.993%
Vero isolate 1
1
230
99.02%
99.997%
Vero isolate 2
1
328
98.89%
99.997%
Vero isolate 3
4
183
99.38%
Vero isolate 4
0
198
99.33%
100%
Vero isolate 5
0
218
99.36%
100%
Vero isolate 6
0
210
99.29%
100%
Vero isolate 7
0
307
98.96%
100%
Vero isolate 8
0
220
99.26%
100%
Tissue 1-1
1
227
99.24%
99.993%
Tissue 1-2
1
982
96.69%
99.997%
Tissue 1-3
2
120
99.60%
99.997%
Tissue 2
0
278
99.07%
100%
99.986%
100%
simultaneous detection and differentiation of common circulating respiratory pathogens at clinically relevant sensitivity levels, but also identified coinfections and unusual pathogens that are rarely encountered or typically unexpected. In addition, these researchers demonstrated that RAs are able to discriminate and make strain-level identifications of several coinfectants in a complex mixture of samples. With the future expected to bring increases in density and decreases in cost, RA technology holds out great promise for the surveillance of broadspectrum respiratory pathogens.
3.6 Further Challenges With the current explosion of interest in next generation DNA sequencing technologies, the idea of a genome-sequencing center in every lab seems increasingly feasible. High-density oligonucleotide resequencing arrays are one possible technology well suited to fulfilling this vision. RAs can generate enormous quantities of very high-quality DNA sequence with minimal personnel and infrastructure
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing
39
requirements. And yet, while RAs already are a powerful tool applicable to a variety of whole-genome analyses, significant challenges remain to be addressed. The most important technical challenge for RAs lies in the isolation of target DNA from large, complex eukaryotic genomes. For organisms with relatively small genomes, whole-genome amplification followed by labeling and hybridization is a viable strategy. While LPCR can be used to resequence large genomic regions, scaling this approach to obtain high call rates on regions as big as an entire eukaryotic chromosome arm is probably not within reach of a single laboratory. Clone-based methods have shown some promise, but they are still somewhat labor-intensive and relatively expensive. As RA feature density increases, this problem will only become more pronounced; therefore, this will remain an important area of research. Because RAs can only compare target DNA to complementary probes based upon a reference sequence, they are not best used for identifying novel sequences or sequence rearrangements that may occur in the experimental sample. Furthermore, existing algorithms do not allow RAs to detect copy number variation (CNV) in diploid targets. The CNV class of variation, though more rare than the SNP, has nonetheless proved to be surprisingly frequent [29, 30]. While the number of features possible on a RA has grown rapidly, there are undoubtedly practical limits to the absolute number of oligos that can be synthesized on a single chip. Despite this limitation, for many genetic studies, particularly in human or mouse genetics, resequencing large genomic regions, rather than entire genomes, may be sufficient to identify specific mutations. Coupled with an appropriate target DNA isolation procedure, RAs could be very efficient at performing these types of studies. RAs also present a number of computational and bioinformatic challenges that will likely be addressed as this technology develops. Although ABACUS does perform extraordinarily well and has become the industry standard for analyzing RAs, algorithmic improvements are certainly within the realm of possibility. For instance, ABACUS is a purely statistical model that does not account for probe sequence composition. Other algorithms, like model-P [31], are based on probe sequences and have demonstrated improved base calling in diploid samples, making this an active area of research. The need to annotate and analyze the vast quantities of sequence data produced by such next generation sequencing technologies as RAs poses another challenge. Integrating these data with other existing genome annotations in current databases, like Ensembl [32] (http://www.ensembl.org/) or the UCSC Genome Bioinformatics site (http://www.genome.ucsc.edu), will be vital to maximizing the utility of these data. In the final analysis, all next generation sequencing technologies will face a range of unique and common challenges as the technologies develop. RAs may ultimately be combined with other sequencing technologies to speed specific
40
Genome Sequencing Technology and Algorithms
research applications, while at the same time helping to fulfill the promised future of personalized medicine. Yet all the next generation sequencing technologies, which will generate ever-greater quantities of DNA sequence data while decreasing personnel and infrastructure requirements, will undoubtedly pose significant threats to the traditional industrial model of DNA sequence production. Envisioning a scientific landscape radically altered by a future where every laboratory is a genome-sequencing center promises to foment still other revolutions, the shape of which we can only begin to imagine.
References [1] The International Human Genome Sequencing Consortium, “Initial Sequencing and Analysis of the Human Genome,” Nature, Vol. 409, 2001, pp. 860–921. [2] Collins, F. S., M. Morgan, and A. Patrinos, “The Human Genome Project: Lessons from Large-Scale Biology,” Science, Vol. 300, 2003, pp. 286–290. [3] Venter, J. C., et al., “The Sequence of the Human Genome,” Science, Vol. 291, 2001, pp. 1304–1351. [4] Shendure, J., et al., “Advanced Sequencing Technologies: Methods and Goals,” Nat. Rev. Genet., Vol. 5, 2004, pp. 335–344. [5] Cutler, D. J., et al., “High-Throughput Variation Detection and Genotyping Using Microarrays,” Genome Res., Vol. 11, 2001, pp. 1913–1925. [6] Zwick, M. E., et al., “Microarray-Based Resequencing of Multiple Bacillus Anthracis Isolates,” Genome Biol., Vol. 6, 2005, p. R10. [7] Lipshutz, R. J., et al., “High Density Synthetic Oligonucleotide Arrays,” Nat. Genet., Vol. 21, 1999, pp. 20–24. [8] Singh-Gasson, S., et al., “Maskless Fabrication of Light-Directed Oligonucleotide Microarrays Using a Digital Micromirror Array,” Nat. Biotechnol., Vol. 17, 1999, pp. 974–978. [9] Karolchik, D., et al., “The UCSC Table Browser Data Retrieval Tool,” Nucleic Acids Res., Vol. 32, 2004, pp. D493–D496. [10] Smit, A. F. A., and P. Green, “RepeatMasker,” http://ftp.genome.washington.edu/RM/RepeatMasker.html. [11] Raymond, C. K., E. H. Sims, and M. V. Olson, “Linker-Mediated Recombinational Subcloning of Large DNA Fragments Using Yeast,” Genome Res., Vol. 12, 2002, pp. 190–197. [12] Raymond, C. K., et al., “Targeted, Haplotype-Resolved Resequencing of Long Segments of the Human Genome,” Genomics, Vol. 86, 2005, pp. 759–766.
The Role of Resequencing Arrays in Revolutionizing DNA Sequencing
41
[13] Hacia, J., and F. S. G. Collins, “Mutational Analysis Using Oligonucleotide Microarrays,” J. Med. Genet., Vol. 36, 1999, pp. 730–736. [14] Hacia, J. G., et al., “Oligonucleotide Microarray Based Detection of Repetitive Sequence Changes,” Hum. Mutat., Vol. 16, 2000, pp. 354–363. [15] Hacia, J. G., et al., “Determination of Ancestral Alleles for Human Single-Nucleotide Polymorphisms Using High-Density Oligonucleotide Arrays,” Nat. Genet., Vol. 22, 1999, pp. 164–167. [16] Hacia, J. G., et al., “Evolutionary Sequence Comparisons Using High-Density Oligonucleotide Arrays,” Nat Genet., Vol. 18, 1998, pp. 155–158. [17] Hacia, J. G., et al., “Strategies for Mutational Analysis of the Large Multiexon ATM Gene Using High-Density Oligonucleotide Arrays,” Genome Res., Vol. 8, 1998, pp. 1245–1258. [18] Chee, M., et al., “Accessing Genetic Information with High-Density DNA Arrays,” Science, Vol. 274, 1996, pp. 610–614. [19] Halushka, M. K., et al., “Patterns of Single-Nucleotide Polymorphisms in Candidate Genes for Blood-Pressure Homeostasis,” Nat. Genet., Vol. 22, 1999, pp. 239–247. [20] Wang, D. G., et al., “Large-Scale Identification, Mapping, and Genotyping of SingleNucleotide Polymorphisms in the Human Genome,” Science, Vol. 280, 1998, pp. 1077–1082. [21] Cargill, M., et al., “Characterization of Single-Nucleotide Polymorphisms in Coding Regions of Human Genes,” Nat. Genet., Vol. 22, 1999, pp. 231–238. [22] Sachidanandam, R., et al., “A Map of Human Genome Sequence Variation Containing 1.42 Million Single Nucleotide Polymorphisms,” Nature, Vol. 409, 2001, pp. 928–933. [23] Ewing, B., and P. Green, “Base-Calling If Automated Sequencer Traces Using Phred. II. Error Probabilities,” Genome Res., Vol. 8, 1998, pp. 186–194. [24] Ewing, B., et al., “Base-Calling of Automated Sequencer Traces Using Phred. I. Accuracy Assessment,” Genome Res., Vol. 8, 1998, pp. 175–185. [25] Maitra, A., et al., “The Human MitoChip: A High-Throughput Sequencing Microarray for Mitochondrial Mutation Detection,” Genome Res., Vol. 14, 2004, pp. 812–819. [26] Zhou, S., et al., “An Oligonucleotide Microarray for High-Throughput Sequencing of the Mitochondrial Genome,” J. Mol. Diagn., Vol. 8, 2006, pp. 476–482. [27] Wong, C. W., et al., “Tracking the Evolution of the SARS Coronavirus Using High-Throughput, High-Density Resequencing Arrays,” Genome Res., Vol. 14, 2004, pp. 398–405. [28] Lin, B., et al., “Broad-Spectrum Respiratory Tract Pathogen Identification Using Resequencing DNA Microarrays,” Genome Res., Vol. 16, 2006, pp. 527–535. [29] Sebat, J., et al., “Large-Scale Copy Number Polymorphism in the Human Genome,” Science, Vol. 305, 2004, pp. 525–528.
42
Genome Sequencing Technology and Algorithms
[30] Sharp, A. J., et al., “Segmental Duplications and Copy-Number Variation in the Human Genome,” Am. J. Hum. Genet., Vol. 77, 2005, pp. 78–88. [31] Zhan, Y., and D. Kulp, “Model-P: A Basecalling Method for Resequencing Microarrays of Diploid Samples,” Bioinformatics, Vol. 21, Suppl. 2, 2005, pp. ii182–ii189. [32] Birney, E., et al., “Ensembl 2006,” Nucleic Acids Res., Vol. 34, 2006, pp. D556–D561.
4 Polony Sequencing Jay Shendure, Gregory J. Porreca, and George M. Church
4.1 Introduction Conventional technology and industrial capacity for sequencing DNA polymers is many orders of magnitude ahead of the equivalents for direct RNA and protein sequencing. This is ironic, given that initial development of a DNA-sequencing method was the most difficult of the three, and took the longest [1]. The first attempts at DNA sequencing followed the precedent set by protein and RNA, sequencing by detailed analysis of degradation products. However, the length and consequent complexity of DNA polymers proved to be significantly problematic, and a real breakthrough was not achieved until the development of the Maxam-Gilbert and Sanger methods in the late 1970s [2, 3]. The former proceeds by base-specific chemical degradation, and the latter by base-specific termination of polymerase-driven synthesis. For both approaches, however, it was the use of electrophoretic gels capable of resolving single basepair length differences that proved critical to enabling long, accurate reads. Through the 1980s and 1990s, the Human Genome Project motivated a wide range of innovations in biochemistry and automation that brought the sequencing field to its present state. Highly optimized machines performing the Sanger method generate up to one megabase of sequence per day, at a cost of approximately $1 per raw kilobase. Although this low cost and high data-rate are the result of incremental improvements approximating a Moore’s Law of DNA sequencing, it is generally recognized that most avenues for optimization have been exhausted. As we have discussed previously in a review of emerging sequencing technologies [4], there remains a long list of applications for DNA 43
44
Genome Sequencing Technology and Algorithms
sequencing that will be increasingly realistic and worthwhile, provided the cost of sequencing continues to drop. These applications provide a strong incentive for investing significantly in the development of alternative sequencing technologies. Methodologies under development can be broadly grouped into a small number of categories [4], namely: (1) microelectrophoresis, (2) nanopore sequencing, (3) resequencing by hybridization to microarrays, and (4) cyclic-array methods. We recently described a cyclic-array method for DNA sequencing [5], involving sequencing of PCR colonies tethered to beads (bead polonies) via a novel ligation-based chemistry. In this chapter, we will briefly review how our method works and discuss some of the existing and potential applications.
4.2 Overview The term “polony,” in the context of molecular biology, is an abbreviation of “POLymerase colONY” [6]. To quote from [7]: “Polonies are discrete clonal amplifications of a single DNA molecule, grown on a solid-phase surface. This approach greatly improves the signal-to-noise ratio. Polonies can be generated using several techniques that include solid-phase PCR in polyacrylamide gels, bridge PCR, rolling-circle amplification, BEAMing (beads, emulsions, amplification and magnetics) based cloning on beads and massively parallel signature sequencing (MPSS) to generate clonal bead arrays.” The workflow for our implementation of polony sequencing can be divided into three steps: (1) library construction, (2) template amplification, (3) sequencing. To briefly summarize our use of the technology as it was implemented in [5]: Genomic DNA (gDNA), isolated from an E. coli strain that was the product of an experimental evolution experiment was converted by a purely in vitro protocol into a sequencing library. In the library, each ∼135 bp template contained two 17- to 18-bp tags of unique sequence (derived from the E. coli genome being sequenced), flanked and separated by universal adaptor sequences. Each set of tags on the same template molecule was “paired,” in that the two tags were known to have derived from locations on the genome separated by a defined distance distribution. This mixture of templates was then amplified in parallel on 1-micron beads by emulsion PCR [8]. This resulted in a population of “clonal” beads, where each bead bears thousands of copies of the same library template, while a different bead will have copies of a different template, and so forth. Millions of beads were immobilized to a two-dimensional array and subjected to automated cycles of multiplex sequencing via a novel ligation-based chemistry. Sequencing data were acquired by rapid four-color imaging via epifluoresence microscopy. Although the reads obtained were short (a discontinuous 13 bp from each tag),
Polony Sequencing
45
this information was sufficient to sensitively and specifically identify adaptive mutations and genomic rearrangements in the evolved E. coli strain. On our prototype instrument, we estimated our costs at roughly an order of magnitude below those of conventional sequencing as implemented by the major sequencing centers.
4.3 Construction of Sequencing Libraries Conventional DNA sequencing libraries are generated by cloning fragmented gDNA into a vector which can be transformed into E. coli for propagation and amplification. Paired reads can be obtained by sequencing from either direction into inserts with a known size distribution. As we set out to develop a library construction protocol, we had several constraints in mind. First, the transformation step imposes a numerical bottleneck on the complexity of the library, and propagation in E. coli can bias the library against certain sequences. We therefore sought to develop a purely in vitro method of library construction. Second, we wanted the library method to be compatible with obtaining paired reads, which are proven to be useful for detecting rearrangements as well as for genome assembly. Third, we had observed that our intended amplification protocol, emulsion PCR, poorly amplified sequences that were greater than 200 bp. We therefore sought a method that would yield relatively short library molecules. With these constraints in mind, the method that we developed involves the following steps: (1) mechanical shearing of genomic DNA; (2) gel-based size selection of fragments approximately 1 kb in length; (3) end-repair and A-tailing of these fragments; (4) circularization with a short, ∼30-bp, T-tailed fragment (T30) that contained outward facing sites for a Type IIs restriction enzyme, MmeI; (5) exonuclease treatment and hyperbranched rolling-circle amplification of circles (hRCA), to increase the available number of molecules; (7) digestion with MmeI, to release T30 fragments along with paired, 17- to 18-bp tags (each set of which is derived from the ends of an about 1-kb genomic DNA fragment); (8) ligation of adaptor sequences; and (9) PCR amplification of the library to increase the available number of molecules. We are presently working to improve and simplify this protocol in a number of ways. (1) Analysis of our sequencing data clearly indicates that the bottleneck in the complexity of our sequencing libraries is due to inefficient circularization of genomic DNA fragments to the T30 adaptor. This is likely due to the poor efficiency of TA ligation. We are replacing the A-tailing step with the ligation of adaptors bearing longer ssDNA overhangs, enabling efficient self-circularization of library molecules. (2) MmeI yields tags of 17 or 18 bp, at approximately a 1:1 ratio. We are exploring a number of different Type IIs enzymes, including EcoP15I and AcuI, that yield tags of ∼27 bp and ∼16 bp,
46
Genome Sequencing Technology and Algorithms
respectively. We have generally found that TypeIIs enzymes that yield shorter tags have less uncertainty in the precise position at which they cut. (3) Several polyacrylamide gel electrophoresis (PAGE) size purifications are required in our published protocol. We have switched to a column-based gel system in which size ranges are isolated by time-sensitive elution, significantly reducing the labor due to these steps.
4.4 Template Amplification with Emulsion PCR Although direct interrogation of single nucleic acid molecules is gaining in practicality, DNA and RNA generally require amplification to enable analysis. The application of restriction enzymes to develop generalized cloning methods [9] opened the gates to modern molecular biology. Cloning allows isolation and perpetual high-fidelity amplification of a specific DNA fragment. The operation is “clonal,” in that all resulting amplicons originated from the same single molecule. In a shotgun-sequencing pipeline, the multiplex construction of a complex library is essentially disentangled by transformation into E. coli. Individual colonies propagate and amplify a single sequencing template, but a bottleneck exists in that colonies must be serially picked and then fed to a highly parallel sequencing platform. Since 1988, methods have been developed that enable in vitro polymerasedriven amplification of single molecules, such that all amplicons, analogous to a bacterial clone, reside at a shared location [10]. In vitro amplification can be potentially based on the polymerase chain reaction (PCR) or rolling circle amplification. Avoidance of mixing between amplification products can be achieved most simply through template dilution and physically distinct wells [11, 12]. Alternatively, immobilization of at least one end of each amplicon to a two-dimensional [8, 13, 14] or three-dimensional [6, 15] solid support matrix can result in physically separated PCR colonies. A third method of compartmentalizing reactions involves water-in-oil emulsions [16]. These were originally used for in vitro directed evolution, but more recently have been modified to allow capture of clonal PCR reaction products on recoverable beads [8], as described in further detail later. We and others [7] use the term “polony” broadly, to describe systems where multiplex PCR amplification is performed, but amplicon mixing is prevented by local immobilization of amplicons to yield colonies of PCR products. “Rolony” refers to amplified colonies generated by rolling circle amplification, rather than PCR amplification. Our initial focus centered on in situ polonies, in which amplification was performed within a polyacrylamide gel to restrict diffusion, and PCR products were locally immobilized by covalent linkage of one of the PCR primers to the gel matrix itself [6, 15]. In this system, multiplex
Polony Sequencing
47
hybridizations and enzymatic reactions to interrogate amplified in situ polonies were performed with oligonucleotides and dNTPs bearing fluorescent labels. Data were acquired via a laser-based scanning microarray reader. With colleagues, we developed applications for querying nucleic acids in ways that are extremely difficult with conventional technology, such as long-range direct molecular haplotyping across kilobases [17] or whole chromosomes [18], quantitation of mRNAs bearing complex, combinatorial patterns of alternative splicing [19], and sequencing-by-synthesis of short tags using cleavable fluorescent nucleotides [20]. We have subsequently transitioned to generating bead-based polonies via emulsion PCR (ePCR) as described by [8]. The ePCR protocol involves generating a water-in-oil emulsion that contains all PCR reactants in the aqueous phase. Template is included at a low concentration, such that the vast majority of compartments contain zero or one template molecule, though a small percentage has multiple templates. Also included in the reaction are 1-micron paramagnetic beads that bear one of the PCR primers (“reverse primer”) by a streptavidin-biotin linkage, such that one strand of each PCR product will be tethered to the beads. The forward primer and a low concentration of reverse primer are present in the aqueous phase. The PCR reaction is carried out via standard thermocycling, albeit with a greater number of cycles. In compartments containing a single template, amplicons are captured to the beads, resulting in a clonal bead. In compartments containing zero or multiple templates, beads end up with no amplicons, or mixed amplicons, respectively. The primary advantages of bead polonies/ePCR, relative to in situ PCR, include the small, uniform size and high signal density of the resulting sequencing features. These in turn enable data acquisition by epifluorescence microcopy, rather than a microarray scanner. In ePCR, the consequence of lowering the concentration of template to avoid obtaining mixed beads (resulting from multiple templates in one compartment) is that one increases the fraction of beads that are “empty” because their compartment contained no template. The ratios are governed by a Poisson distribution, and a typical experiment might yield 90.5% empty beads, 9% clonal beads, and 0.5% mixed beads. As empty beads occupy substantial territory on the sequencing arrays, we developed a method (as described in [5]) to enrich the fraction of template-bearing beads. The method is based on hybridization of ePCR-generated beads to large (3 µm), low-density beads that bear a primer complementary to the forward PCR primer. As this sequence is only present on amplicons tethered to PCR-product bearing beads, these beads selectively hybridize to the 3-µm capture beads. This fraction is separated from empty 1-µm beads by centrifugation through a glycerol gradient. The protocol can be repeated for increased levels of enrichment.
48
Genome Sequencing Technology and Algorithms
Other emerging sequencing technologies, such as that of 454 Corp., also rely on emulsion PCR. Contrasts between their ePCR protocols and those of [8] include (1) different bead sizes (25 µm versus 1 µm, which translates to a 625-fold difference in cross-sectional area and an approximate 15,000-fold difference in volume), and (2) markedly different emulsion compositions. It is also notable that the protocols [8] have recently been updated by several papers that include protocols for greater ePCR consistency and a method for using rolling circle amplification (RCA) to enable more than a hundredfold increases in signal [21, 22]. We are currently working to integrate these improvements into our sequencing platform protocols.
4.5 Sequencing Arrays of sequencing features, produced by layering beads, can potentially be ordered or random. Ordered arrays have the advantage of defined feature separation and can enable very high packing densities, while disordered arrays are much easier to generate but retain the potential for high feature density (by self-assembly of monolayers, for example). In our transition from in situ polonies to bead-based sequencing features, we adapted the gel-based system to enable monolayering of beads at the surface of a thin acrylamide gel. We have subsequently adapted these protocols to enable gel-free bead arrays [23]. In initial experiments, we have found that in the absence of the acrylamide gel, enzymatic reactions are more efficient and the resulting imaging data is significantly less noisy. In cyclic-array methods, each cycle generally involves an enzymatic step in which a fluorescent label is incorporated to a primer that is hybridized to a constant sequence present on each template molecule. The enzymatic reaction provides specificity, and the identity of the fluorophore provides information as to whether a particular base is present at a given position. Enzymes that have been used in this way include polymerases and ligases. We described a sequencing method that relies on ligation of degenerate nonamers to an “anchor” primer that hybridizes immediately adjacent to the unknown sequence of interest [5]. In each cycle: 1. An anchor primer is hybridized either immediately 5’ or 3’ to one of the unknown tag sequences. 2. A population of random 9-mers is flowed in; each bears a fluorescent label. Depending on which base is being queried at a given cycle, the population of nonamers is structured such that the identity of a specific base position correlates with the identity of the attached fluorophore.
Polony Sequencing
49
3. Data acquisition via four-color imaging of beads (e.g., A = Cy3, G = Cy5, T = FITC, C = Texas Red). 4. Stripping of the anchor primer/nonamer complexes to reset the array prior to starting the subsequent cycle, which will interrogate a different base position. In [5], stripping was performed by enzymatic digestion at deoxyuridines included in the anchor primer, but we have since begun chemically stripping with alkali to reduce cost and time. We have found that T4 ligase will perform ligation efficiently, but the fidelity of ligation extends only to 6 to 7 bases away (in both directions) from the actual site of ligation. Taq ligase (commercially known as Ampligase) has strong potential to extend the specificity to 9 bases [24]. The drawback of nonamer ligation for sequencing, as we have currently implemented it, is that reads are limited to relatively short lengths. However, by positioning the anchor primer at either end of each unknown tag, one can sequence from either direction into the unknown tag. In the described work, we were able to sequence 6 to 7 bp from each direction into each of two 17- to 18-bp tags. Although this provided 13 bp of sequence for each of the two tags, the sequence itself was not continuous, and was compounded by the uncertainty in the distance between the 6-mer and 7-mer because of the ”wobble” in MmeI cut distance. However, we were nevertheless able to use the information to place reads to a reference E. coli sequence and identify mutations. We feel our success in making use of these data supports the case that for a variety of goals, as discussed below, relatively modest read-lengths will be sufficient. Specifically, applications that put a larger priority on the total amount of sequence, or the number of independent sequence tags obtained, may be more accepting of shorter reads. However, discontinuous 6- to 7-bp reads are not sufficient for many of these purposes, and we are therefore working to enable continuous 20–25 bp reads, via modifications to ligation-based protocols.
4.6 Future Directions In both academia [5] and industry [25], we have seen several alternative DNA sequencing technologies achieve important proof-of-principle milestones. These successes have led to broadened interest and funding for enabling new technologies. In the 1990s, a single-sequencing platform (namely, the ABI series of instruments) was generally considered the instrument of choice for high-throughput sequencing. It remains unclear whether a single approach will become dominant in this next generation of technologies. The range of applications of sequencing has expanded considerably (e.g., genome resequencing, de
50
Genome Sequencing Technology and Algorithms
novo sequencing, barcode sequencing, transcript tag sequencing, digital karyotyping, and so forth) and the critical parameters for these applications differ. For example, de novo sequencing is simplest with long, paired-sequencing reads. For genome resequencing, the key is to achieve high final consensus accuracies, and reads need only be long enough to match to a reference sequence. For transcript tag sequencing, digital karyotyping, and barcode sequencing, the priority is on depth—obtaining the greatest possible number of independent reads. It is possible that one technology will excel in all of these, but it is also possible that different platforms may be the best choice for specific applications. In any case, as this field gathers momentum it is clear that cost of the DNA sequencing will continue to fall. The completion of a human genome may have marked the end-of-the-beginning of the era of sequencing and, more generally, the era of nucleic-acid technologies. It is hard to avoid the feeling that we have only scratched the surface of what it will be possible to do with DNA.
References [1] Sanger, F., “Sequences, Sequences, and Sequences,” Ann. Rev. Biochem., Vol. 57, 1988, pp. 1–28. [2] Maxam, A. M., and W. Gilbert, “A New Method for Sequencing DNA,” Proc. Natl. Acad. Sci. USA, Vol. 74, No. 2, February 1977, pp. 560–564. [3] Sanger, F., S. Nicklen, and A. R. Coulson, “DNA Sequencing with Chain-Terminating Inhibitors,” Proc. Natl. Acad. Sci. USA, Vol. 74, No. 12, December 1977, pp. 5463–5467. [4] Shendure, J., et al., “Advanced Sequencing Technologies: Methods and Goals,” Nat. Rev. Genet., Vol. 5, No. 5, May 2004, pp. 335–344. [5] Shendure, J., et al., “Accurate Multiplex Polony Sequencing of an Evolved Bacterial Genome,” Science, Vol. 309, No. 5741, September 9, 2005, pp. 1728–1732. [6] Mitra, R. D., and G. M. Church, “In Situ Localized Amplification and Contact Replication of Many Individual DNA Molecules,” Nucleic Acids Res., Vol. 27, No. 24, December 15, 1999, p. e34. [7] Fan, J. B., M. S. Chee, and K. L. Gunderson, “Highly Parallel Genomic Assays,” Nat. Rev. Genet., Vol. 7, No. 8, August 2006, pp. 632–644. [8] Dressman, D., et al., “Transforming Single DNA Molecules into Fluorescent Magnetic Particles for Detection and Enumeration of Genetic Variations,” Proc. Natl. Acad. Sci. USA, Vol. 100, No. 15, July 22, 2003, pp. 8817–8822. [9] Cohen, S. N., et al., “Construction of Biologically Functional Bacterial Plasmids In Vitro,” Proc. Natl. Acad. Sci. USA, Vol. 70, No. 11, November 1973, pp. 3240–3244. [10] Li, H. H., et al., “Amplification and Analysis of DNA Sequences in Single Human Sperm and Diploid Cells,” Nature, Vol. 335, No. 6189, September 29, 1988, pp. 414–417.
Polony Sequencing
51
[11] Leamon, J. H., et al., “A Massively Parallel PicoTiterPlate Based Platform for Discrete Picoliter-Scale Polymerase Chain Reactions,” Electrophoresis, Vol. 24, No. 21, November 2003, pp. 3769–3777. [12] Vogelstein, B., and K. W. Kinzler, “Digital PCR,” Proc. Natl. Acad. Sci. USA, Vol. 96, No. 16, August 3, 1999, pp. 9236–9241. [13] Adams, C., and S. Kron, “Method for Performing Amplification of Nucleic Acid with Two Primers Bound to a Single Solid Support,” U.S. Patent No. 5641658, 1997. [14] Lizardi, P. M., et al., “Mutation Detection and Single-Molecule Counting Using Isothermal Rolling-Circle Amplification,” Nat. Genet., Vol. 19, No. 3, July 1998, pp. 225–232. [15] Chetverin, A. B., H. V. Chetverina, and A. V. Munishkin, “On the Nature of Spontaneous RNA Synthesis by Q Beta Replicase,” J. Mol. Biol., Vol. 222, No. 1, November 5, 1991, pp. 3–9. [16] Tawfik, D. S., and A. D. Griffiths, “Man-Made Cell-Like Compartments for Molecular Evolution,” Nat. Biotechnol., Vol. 16, No. 7, July 1998, pp. 652–656. [17] Mitra, R. D., et al., “Digital Genotyping and Haplotyping with Polymerase Colonies,” Proc. Natl. Acad. Sci. USA, Vol. 100, No. 10, May 13, 2003, pp. 5926–5931. [18] Zhang, K., et al., “Long-Range Polony Haplotyping of Individual Human Chromosome Molecules,” Nat. Genet., Vol. 38, No. 3, March 2006, pp. 382–387. [19] Zhu, J., et al., “Single Molecule Profiling of Alternative Pre-mRNA Splicing,” Science, Vol. 301, No. 5634, August 8, 2003, pp. 836–838. [20] Mitra, R. D., et al., “Fluorescent In Situ Sequencing on Polymerase Colonies,” Anal. Biochem., Vol. 320, No. 1, September 1, 2003, pp. 55–65; erratum in Anal. Biochem., Vol. 328, No. 2, May 15, 2004, p. 245. [21] Diehl, F., et al., “BEAMing: Single-Molecule PCR on Microparticles in Water-in-Oil Emulsions,” Nat. Methods, Vol. 3, No. 7, July 2006, pp. 551–559. [22] Li, M., et al., “BEAMing Up for Detection and Quantification of Rare Sequence Variants,” Nat. Methods, Vol. 3, No. 2, February 2006, pp. 95–97. [23] Kim, J. B., et al., “Polony Multiplex Analysis of Gene Expression (PMAGE) in a Mouse Model of Hypertrophic Cardiomypathy,” Science, Vol. 316, No. 5830, 2007, pp. 1481–1484. [24] Housby, J. N., and E. M. Southern, “Fidelity of DNA Ligation: A Novel Experimental Approach Based on the Polymerisation of Libraries of Oligonucleotides,” Nucleic Acids Res., Vol. 26, No. 18, September 15, 1998, pp. 4259–4266. [25] Margulies, M., et al., “Genome Sequencing in Microfabricated High-Density Picolitre Reactors,” Nature, Vol. 437, No. 7057, September 15, 2005, pp. 376–380.
5 Genome Sequencing: A Complex Path to Personalized Medicine Lewis J. Frey, Victor Maojo, and Joyce A. Mitchell
5.1 Introduction With the completion of the Human Genome Project in 2003, the worldwide focus has shifted to converting this vast storehouse of information into innovative health-care solutions. The ultimate promise is to ensure that every person has optimum health throughout their life. This promise is fulfilled by many parts, including adequate nutrition, clean water supplies, up-to-date immunizations, and regular health screening. The part of the promise to be fulfilled by knowledge and information stemming from genomics and other “omics” is yet unfolding. The clear informational basis for bioinformatics, the famous rule of the Crick’s dogma of biology, DNA to RNA to proteins, gave researchers concrete ground that facilitated the rapid completion of the Human Genome Project. It is quite a different situation for biomedical informatics, where the path from genomic sequences to personalized medicine is complex given the many difficulties of modeling systems in clinical medicine. The purpose of this chapter is to review some of the progress made towards personalized medicine from the perspective of biomedical informatics. With respect to their usefulness on human health care, the vast and heterogenous storehouses of information are just beginning to be tapped. A major push from the informatics community as it focuses on how to organize, synthesize, and deliver information to providers and
53
54
Genome Sequencing Technology and Algorithms
the public worldwide in an effective manner to demonstrate improved health is critical to realize the potential of personalized medicine. Personalized medicine does not have a crisp definition, but rather reflects a broad coalition of ideas brought to bear on an age-old notion of personalized care. In the Genomics and Personalized Medicine Act of 2006 [1] personalized medicine is defined as “…the application of genomic and molecular data to better target the delivery of health care, facilitate the discovery and clinical testing of new products, and help determine a patient’s predisposition to a particular disease or condition.” The tradition of health care is to focus on the patient, whose care is being provided in the best possible manner, thus providing personalized care. The “personalized medicine” movement incorporates the use of molecular analysis and specifically methods evolving from knowledge of genomics to better manage a patient’s disease or predisposition toward a disease [2]. The belief of the worldwide scientific community is that knowledge of genomics will contribute to better health outcomes. The actual approaches are not well defined but would include genetic screening programs, genetic risk analyses, and the use of diagnostic and therapeutic modalities that are still evolving. The realization of this dream of personalized medicine is tied to the discoveries of bioinformatics and the implementations of health information technology that have been developed by the pioneers of medical informatics. Thus the two subfields of biomedical informatics are dependent on each other for realizing their full level of success. While the development of new genetic tests and diagnostic modalities is steadily advancing, the progress of incorporating results of such tests into the electronic medical records and using these results in clinical decision support is inching forward and would benefit from a coordinated worldwide approach from the biomedical informatics research community. The realization of the dream of personalized medicine is also tied to the Internet and the public’s use of the World Wide Web. There is growing interest from the public to find information related to health problems they see in their families, and also where they might be tested for specific genetic mutations [3]. Web sites that focus on providing genetic information linked to specific human health concerns have shown growing interest. For example, the Genetics Home Reference is a Web site created by the National Library of Medicine as part of its consumer health information resources (see Figure 5.1) [4, 5]. Links to this resource from such health-news outlets as CNN and CNBC demonstrate that the public is interested in genetic and health topics and is willing to follow up the news stories with investigation of related Web links. This interest from the public is creating pressure on care providers worldwide to order more genetic tests and to be more educated about the range of possible genomic-based medicine as it evolves [6].
Genome Sequencing: A Complex Path to Personalized Medicine
55
Figure 5.1 Home page of the Genetics Home Reference. This National Library of Medicine–supported site is focused on presenting the health-related results of the Human Genome Project to the public. The research findings are linked to specific health conditions.
5.2 Personalized Medicine After the completion of the Human Genome and other “omics” projects, biomedical scientists and professionals aimed to introduce biological information, such as SNPs, microarray data, biomarkers, and ever increasing data sets into clinical practice. Researchers hoped that new findings could have immediate clinical applications, leading to new visions of medicine, such as genomic medicine or “personalized medicine” [7–12]. Personalized medicine aims to adapt these mechanisms to individual patients [13]. Nevertheless, each patient will not be treated differently from every other patient [14]. Rather, patients are divided into groups by genetic and other markers that predict disease progression and treatment outcome. Personalized medicine, based on genetic factors or markers and more specific drugs [15], cannot be a magical solution for every individual. Instead, drugs will be tailored for groups of people with similar or related genetics characteristics. In this scenario of personalized medicine, pharmacogenetics is at the center of research and practice [14, 16–18]. Pharmacogenetics explains the different
56
Genome Sequencing Technology and Algorithms
responses of individuals to the same drugs. To validate preliminary findings and models, experiments (e.g., clinical trials) must be carried out with a large number of patients [13]. Therefore, classical clinical studies must be redesigned to adapt to these new situations. Weatherall [19] has emphasized the different cautious steps to be taken before personalized medicine can be applied in clinical medicine. Personalized medicine can prove that diseases such as cancer or diabetes type II, formerly classed as a unique and isolated category, can be reconsidered and reclassified, proving that they are due to different causes. This reclassification leads to new diagnostic and therapeutic procedures. Once this process is established, researchers must show that it is cost-effective to test specific markers and use specific drugs. Otherwise, health systems may refuse to afford the enormous demands of this new shift in medicine, particularly if there is not enough evidence of their significant impact in changing medical outcomes in the population.
5.3 Heterogeneous Data Sources Over the last decade a whole area of “data integration” has been created and expanded. It includes approaches such as data warehousing, information linkage, data translation, and query translation [20] as well as techniques such as ontologies [21]. We have earlier proposed that genomic data could be integrated into health information systems [22–24] but recent research [25–29] suggests that this bridging process will not be easy. At the time of writing, around 900 biological public databases (e.g., genomic, proteomic, metabolomic, and others) were available to researchers and other professionals. These databases have been designed and maintained as a result of many biological research projects that produced a huge amount of heterogeneous information about genes, proteins, and genetic diseases. Public databases usually include different data, ranging from biochemical to public health data. A larger number of organizations maintain their own databases, restricted to public access for different reasons (e.g., socioeconomic, confidentiality, strategic), often focused in one specific area or topic. Within biomedical databases information is often inconsistent or missing. In systems biology, for instance we can find problems related to functional annotations of genes and proteins, genotype-phenotype relationships, kinetic values for enzymes or components of pathways [16]. In clinical systems, spanning over decades, the inconsistencies can be even higher. Analyzing old medical records stored on paper, in settings where computerized medical records were not available until recently, the rate of missing or inconsistent data can be quite variable and often very high [30].
Genome Sequencing: A Complex Path to Personalized Medicine
57
From a scientific perspective, these increase the problems of data integration and analysis, due to the frequent variability across different settings regarding experiments, techniques, procedures, theoretical approaches, cognitive biases, among others [25, 31, 32]. Given this lack of consistency, using data obtained from heterogeneous sources to advance scientific research presents different problems, especially in biomedicine. In the “omics” areas, there has been a predominant data-driven research approach. Multiple sources of genomic-scale data must be integrated to develop more precise descriptions of clinical phenotypes. For instance, gene expression data reflect the effect of oncogenes on metabolic pathways leading to oncological disease. We know now that cancer is not a precise and unique disease, but a number of pathologies, with different causes and therapies. In fact, the differences in all these databases, considering hardware, software applications (e.g., operating systems, database management systems), semantics as well as the differences mentioned above in scientific approaches, cultural environments, cognitive biases, and others (subtly hidden in the stored data) must be solved if the researchers want to really integrate information and extract useful patterns. Frequently, data must be normalized [25] and some common data models and coding systems must be used or developed to standardize the representation of genotype-phenotype information.
5.4 Information Modeling In this effort to enhance information storage and data exchange, bioinformaticians can draw on work that the Object Management Group (OMG; http://www.omg.org) has done in the development of the model driven architecture (MDA) approach. This is an approach that represents systems with graphical object models. They propose the development of platform independent models using the Unified Modeling Language (UML). For modeling complex systems that combine clinical and genomic data, a special kind of UML model, called a domain model, can be used [33]. Such a domain model incorporates the scientific domain knowledge that is necessary in using clinical and genomic data for personalized medicine. The models can be used to communicate information about the system to both developers and users of the system. For example when creating a system about transcription and translation, the objects of DNA, RNA, and proteins should be modeled along with their associations. Models that use domain information to represent knowledge about the data are needed in order for the field to create systems that have better information representations and data exchange. Bioinformaticians are in a position to communicate the underlying body of knowledge to developers in order to create
58
Genome Sequencing Technology and Algorithms
such domain models. In bridging the technology and scientific communities they can help in the creation of domain models that communicate semantically meaningful information about the data. Semantically meaningful information models allow developers to construct objects that have meaningful counter parts in use in their area of application. Since many systems are being developed independently, if developers are enabled to represent objects in a meaningful way, then the chances of having reusable objects or at least objects that are easier to map between systems is increased. Reuse of objects between systems will help improve information storage, data exchange, and the development of interoperable systems.
5.5 Ontologies and Terminologies An interesting effort to normalize and reuse vocabularies and knowledge over different projects and groups is related to ontological development. Ontologies provide the semantics needed to bridge the existing gaps between heterogeneous data sources and a formal language for information retrieval. The underlying vocabularies that are currently being used to support MDA development at the National Cancer Institute (NCI) are those provided by the Enterprise Vocabulary Services (EVS). They support a number of terminologies for the needs of NCI. The two products being used in MDA at NCI are the NCI Thesaurus [34–37] and the NCI Metathesaurus [38]. The former is a reference terminology that has vocabulary in clinical care, translational research, and basic research. It contains information on 10,000 cancers and related diseases and 8,000 therapies. The NCI Metathesaurus is a mapping between multiple terminologies. It includes a specialized version of the UMLS [39, 40]. This version is specialized in order to focus on terminologies that can be related to cancer terminologies [33]. Some of the terminologies that the Metathesaurus includes are LOINC [41], SNOMED/CT [42], Veterans Health Administration National Drug File (VA NDF), Gene Ontology (GO) [43], and MGED Ontology [44]. The NCI Metathesaurus contains 1.2 million concepts mapped to 2.9 million terms with 5 million relationships. Mapping these terminologies supports the goal of representing and combining clinical and genomic information. These terminologies help the developers of domain UML models by giving them a broad range of terminologies. In this way the projects are combining bioinformatics and clinical informatics concepts in data models that support interoperable systems for the field. This is a key component of creating systems that support the development of personalized medicine. In the medical domain, vocabulary and coding systems such as the ICD 9 and 10, SNOMED, LOINC, MeSH, UMLS, ICNP, GALEN, the NCI thesaurus, MedDRA, and others are now used for ontology-related tasks. Although it
Genome Sequencing: A Complex Path to Personalized Medicine
59
can be assumed that they are not “true” ontologies from a formal computing perspective, they have been used in some concrete applications (e.g., the UMLS) [21]. The Foundational Model of Anatomy (FMA) is an extended work concerned with the representation of classes and relationships used for the symbolic representation of the structure of the human body in a format that is understandable to humans and also navigable by computers. Specifically, the FMA is a domain ontology that represents a coherent body of explicit declarative knowledge about human anatomy. In genetics, GO has experienced great success and leads ontological development in the genetic area. GO is a collaborative effort among different organizations and professionals to create a controlled vocabulary of gene and protein roles in cells to consistently describe gene products in different databases. GO includes three structured, controlled vocabularies (or “light” ontologies) that describe gene products in terms of their associated biological processes, cellular components, and molecular functions. There are no current worldwide standards that represent genotype-phenotype data with specific data models that can be used to enhance information storage and exchange. Different coding and vocabulary systems have been used in the medical domain in electronic health records, HIS, epidemiological surveillance systems, and so on, but only recently proposals have been made to link clinical and genetic concepts. The UMLS has recently included genetics terms [45] and the GO [46] within its medical vocabularies and nomenclatures. In general, these efforts have been supported by medical informatics professionals, whereas bioinformaticians have more recently realized that they should dedicate their efforts to this area. In a semantic mediation system, the users (humans or machines) do not care about the specific format of the information source, but only about the terms contained in the ontology for building the query in a proper way. In this regard, ontologies can be understood and used by both humans and machines.
5.6 Applications In a research environment where thousands of devices, databases, Web-based documents and other sources are used in research, clinico-genomics, semantic mediation, and novel computing techniques for such computationally demanding tasks will be needed. For instance, “data grids” can be used in the short term to enhance access to computationally demanding clinico-”omics” applications from remote sites [47, 48]. Bioinformatics’ Web and grid services can be orchestrated to organize intelligent work flows of different applications, organized using program managers and semantic mediators. Semantic mediation will be needed to intelligently organize such “choreography” [47, 49].
60
Genome Sequencing Technology and Algorithms
ACGT (Advancing Clinico-Genomics Trials on Cancer) [50] is funded by the European Commission as an integration project to design new methods and resources for cancer research. Twenty-five partners from Europe and Japan participate in ACGT. The goal of the project is to identify technological gaps and barriers in cancer research and create novel techniques for diagnosis and prevention as well as to design new models of clinico-genomic trials that will facilitate the creation of new drugs and therapies in the context of personalized medicine. From a biomedical informatics perspective, ACGT aims to develop a biomedical grid infrastructure at a European level to conduct research on two different kinds of cancer: pediatric nephroblastoma and breast cancer. In this grid-based scenario, research on systems interoperability (based on the development of the “ACGT master ontology on nephroblastoma” and a semantic mediator to organize the choreography of different Web and grid services), in-silico simulation of drug design, data mining, and clinico-genomic information modeling and management are being investigated to develop novel approaches of clinico-genomic trials. In this framework, heterogeneous data from three ongoing clinical trials are linked with “omic” information into a common virtual repository, by using an ontology-based approach. Such a repository includes different types of clinical and genomic information, such as numerical data, text and images from patients participating in the trials, external public databases, and in-silico simulation. This project, ending in 2010, aims to solve some of the problems that arise in this kind of research. For instance, to build an efficient biomedical Grid infrastructure or carry out in-silico simulations to design and test new drugs in the context of personalized medicine. Two examples of European systems that provide examples of intermediate solutions to the hard challenge of integrating heterogenous data sources are OntoFusion and DiseaseCard. OntoFusion is a tool developed to integrate remote databases. DiseaseCard is an information retrieval tool for accessing and integrating genetic and medical information for medical applications. OntoFusion [21] uses an ontology-based approach, designed to build virtual repositories of physical databases by mapping the schemas of the latter with a domain ontology. Once these schemas have been normalized according to the semantic contents of the ontology, then the virtual repositories can be automatically unified by using a unification algorithm previously described [21]. OntoFusion has been mainly designed to be used by biomedical researchers, although it is domain independent. One of its main features is the ability to integrate public and private databases using the semantic-based approach of the integration method. While its primary objective was just related to database integration, its developers are expanding its features to use ontology-based approaches to automatically preprocess data coming from remote databases.
Genome Sequencing: A Complex Path to Personalized Medicine
61
This process eliminates inconsistencies in terminologies, format, scales, and so on [51]. In such virtual worldwide environment, researchers can access, for instance, a large number of SNP databases or link specific concepts of computerized medical records with similar concepts from remote databases. Finally, users can retrieve the information they need by using Google-like searches or navigating the ontology representing the global virtual repository. Figure 5.2 represents a screenshot of the OntoFusion tool. On the left, the ontology represents the schema of the different (unified or individual) virtual repositories. On the right, the virtual repositories are physically displayed. By clicking these virtual repositories the contents of the physical databases can be displayed, navigated, or retrieved. In this case, the figure represents the integration of different biomedical ontologies for developing a vocabulary server used by the application. Different Web technologies can be used to access and share remote heterogeneous information. Web services are a good example. Web services are based on service-oriented architectures using established Web standards such as eXtensible Markup Language (XML), Web Services Description Language (WSDL), Simple Object Access Protocol (SOAP), or Universal Description, Discovery, and Integration (UDDI). Web services are platform-independent and can be invoked from any platform or architecture. For the different needs related to personalized medicine hundreds of Web services are currently available for practitioners and researchers. To integrate such heterogeneous services new standards are needed for managing semantic
Figure 5.2 OntoFusion tool screen shot. OntoFusion builds virtual repositories of physical databases by mapping the schemas with a domain ontology.
62
Genome Sequencing Technology and Algorithms
heterogeneity. Isolated services are many times unable to solve complex problems. The possibility of combining these services on customized workflows, adapted to the exact demands of researchers, from the combination of those previously available is a new challenge. To reuse and “orchestrate” Web services, some approaches have been reported, such as Taverna [52] and BioMOBY [53]. DiseaseCard is a comprehensive resource to access diseases’ data available over the Internet, in different public remote databases (e.g., OMIM, Medline, Orphaned, PharmGKb). DiseaseCard was developed by the Bioinformatics Group at the University of Aveiro, Portugal, with the collaboration of the Institute of Health Carlos III, Spain. The ultimate goal of DiseaseCard is to provide biomedical practitioners, researchers, and patients rapid access to useful information related to many rare and common genetic diseases. In the framework of personalized medicine, these kind of tools can be a useful aid for practitioners, researchers, and the public in general to rapidly access information about different diseases over the Internet and link it to specific patients’ data. Figure 5.3 shows an example related to hemochromatosis. On the left, users can expand different folders related to different subjects (e.g., references, genetics tests and labs, polymorphisms, nucleotide sequences, metabolic pathways, protein structure, and others). When these nodes are expanded, the information related (which can be locally stored or is retrieved from remote databases) is shown in the right side. In the United States, the National Cancer Institute has taken up the challenge of combining genomic and clinical data for cancer research and treatment. The perspective has been one of building a well-specified infrastructure to support the development of interoperable tooling built upon that infrastructure. The effort has been undertaken by the Cancer Biomedical Informatics Grid (caBIG) community. Their approach based on binding controlled terminology is described below along with some of the tooling developed for caBIG. The UML models in caBIG contain class diagrams that represent the scientifically relevant objects that are part of running software systems. These are objects like DNA sequence, RNA sequence, and protein. The classes are composed of the class name itself (e.g., protein) and the attributes that are in the class (e.g., uniProtKB, name, symbol, and so forth). Between the classes there are association links that convey the relationships between the classes. A description, stored in the UML model, is required for each class and attribute. Using UML domain models to instantiate the MDA framework gives a conceptual representation of the underlying scientific objects via the classes, attributes, associations, and descriptions. This model does not provide an unambiguous representation because developers at different sites, while using the same scientific domain knowledge, can create similar classes and attributes, but with different names, configurations, and descriptions. The binding of
Genome Sequencing: A Complex Path to Personalized Medicine
63
Figure 5.3 Screen shot example of using DiseaseCard to access information related to hemochromatosis. The Bioinformatics Group at the University of Aveiro, Portugal, in collaboration with the Institute of Health Carlos III, Spain, developed DiseaseCard (http://bioserver.ieeta.pt/diseasecard/).
controlled terminology to the model can mitigate the latter problem of different semantics associated with the scientific concepts in the model. The binding does this by unambiguously specifying the description in the model with controlled terminology. The binding is accomplished by mapping concepts from the EVS NCI Thesaurus and Metathesaurus to the classes and attributes in the UML model. These are bound using the concept codes or concept unique identifiers (CUIs) that are maintained by EVS. The descriptions for the classes and attributes are used to determine what CUIs from the EVS terminology should be used for the mapping. This mapping is then used in the creation of the metadata for the data elements that represent the model. This generation of metadata is supported by a suite of tools and infrastructure developed at the NCI. The NCI has implemented the ISO11179 standard for representing metadata in their Cancer Data Standards Repository (caDSR). This incorporates the data structures and format of ISO11179 to store a data element (DE) using a combination of a data element concept (DEC) and a value domain (VD). The DEC maintains the set of CUIs associated with the DE, and the VD
64
Genome Sequencing Technology and Algorithms
specifies the data type and permissible values associated with the DE. Since ISO11179 does not have associations in its representation, the caDSR extends upon the standard to store the metadata for the associations between the UML classes. This is in order to more fully support the MDA approach and incorporate the associations that are in the UML information models. The potential benefit of binding UML models to terminology is the ability to more readily support reuse of model elements. Once the attributes are mapped to the terminology, it has a defining series of concept codes. This along with the value domain specifies the data element. Hence, if another model has an attribute mapped to the same series of concept codes and value domains, then the two models share an identical attribute. This is regardless of differences in the naming conventions in the two models and any differences in the descriptions in the two models. The scientific meaning is encapsulated in the series of concept codes and the value domain that is identical for both models. The point of this system is to help developers and users reach consensus and converge to common models for their systems. In this way tooling can be built in an interoperability fashion. Three tissue banking and pathology tools have been developed using the caBIG infrastructure to coordinate the underlying information models. These are caTISSUE Core, caTISSUE Clinical Annotation Engine (CAE), and the cancer Text Information Extraction System (caTIES). The caTISSUE Core system is used to inventory and track biospecimens. This includes searching for specimens and requesting them for studies. The CAE annotation system is based on the College of American Pathologist (CAP) cancer protocols [54]. It has the functionality to import data from anatomic pathology laboratory systems, cancer tumor registries and clinical pathology laboratory systems. The information is clinically oriented and is tightly tied in with the caDSR, enabling the definitions from the EVS terminology to be displayed for field titles in the interface. The tool caTIES extracts structured text from free-text surgical pathology reports and encodes it in caBIG compliant terminology. This enables researchers to search for annotated tissue over structured terminology instead of free text in order to obtain relevant biospecimens. The Cancer Translational Research Informatics Platform (caTRIP) system utilizes the EVS terminology and metadata in caDSR to run distributed queries on federated data resources. This includes the caTISSUE tools that have their metadata registered in the caDSR. This is an example of the UML models bound to controlled terminology enabling systems to interoperate more effectively. A specific example of interoperability using the caBIG MDA infrastructure is illustrated for the CAE and caTRIP systems. The UML model for breast biomarkers was developed at the University of Pittsburgh in the Biomedical Informatics Department and implemented for their CAE system. It contains the
Genome Sequencing: A Complex Path to Personalized Medicine
65
class Breast Biomarkers with the attribute her2Status [Figure 5.4(a)]. The class and attribute are mapped onto EVS concepts. The class, Breast Biomarkers, is mapped to Breast Carcinoma Tumor Marker [Figure 5.4(b)] and the attribute, her2Status, is mapped to Her2/Neu Status. These supply a list of concept codes with definitions that uniquely identify the common data element. The permissible values are also specified and are viewable under the Permissible Values tab in the CDE Browser (http://cdebrowser.nci.nih.gov/CDEBrowser/). These values are “Positive” and “Negative” and also have EVS concept codes associated with
breast: BreastCancerBiomarkers – erStatus: string – prStatus: string – her2Status: string – her2TestType: string – efgrStatus: String (a)
(b)
Figure 5.4 The breast cancer biomarkers class (a) from the CAE UML model, developed at the University of Pittsburgh, has been mapped to the common data elements stored in the caDSR. This is viewable with the NCI’s CDE browser (b).
66
Genome Sequencing Technology and Algorithms
them. This CDE is used in the CAE to store the status of the genetic test for her2. The caTRIP system (https://cabig.nci.nih.gov/tools/caTRIP) leverages the metadata in the caDSR with respect to CAE. It uses it to construct the attribute filters for its distributed queries. In Figure 5.5 the attribute filter for Her2/Neu Status is specified. This reuses the CDE for her2Status developed for CAE. The definition of the test result is identical as are the permissible values. This is seen in the screen shot with “Positive” being in the Value field for the search on available biospecimens with a positive her2 status. Other filters can be added such as the type of test used (e.g., ImmunoHistoChemistry). This also comes from the CAE UML model with the attribute her2TestType (see Figure 5.4). The returned rows of available tissue with positive test results demonstrate an intermediate solution using MDA to achieve interoperability across institutions for genetic testing related to cancer. The caIntegrator system (https://cabig.nci.nih.gov/tools/caIntegrator) combines a variety of biomedical data related to clinical trials together with bioinformatics experimental data. These latter data types include Immunohistochemistry (IHC), microarray-based gene expression, and SNPs. The tools support the analysis of these data in an integrated system. Some proposals aim to link genotype and phenotype information. One example is the Polymorphism Markup Language (PML), to represent and store SNP (single nucleotide polymorphism) information [46]. This project, launched by a broad international consortium, aims to model the variation of genetic information, including a whole range of mutations. Following a different direction, the IBM Haifa Group has led the HL7 Clinical Genomics special interest group (SIG) to create standards for exchanging clinical and genomic data [55] by using genomic data in health care to support personalized medicine, or integrating genomic data into classical electronic health records, linked to emerging bioinformatics formats such as MAGE-ML for gene expression or BSML for sequencing data. Its genotype model includes various types of genomic data such as sequencing, expression, and proteomics data. Developers have tested this model on cystic-fibrosis data, bone-marrow transplantation, and pharmacogenetics projects [55]. From a European perspective, the European Commission has launched several initiatives since 2001 related to specific contributions that biomedical informatics can apply to personalized medicine. A preliminary conference, called “Synergy between Research in Medical Informatics, Bioinformatics and Neuroinformatics: Knowledge Empowering Individualized Healthcare and Well-Being” was held in Brussels in 2001. In June 2006, another meeting, “ICT for BIO Medical Sciences 2006,” analyzed the results obtained in the 5 years since 2006. In this time various conferences, projects, and different activities were carried out. The BIOINFOMED study [22] was delivered in 2002,
Figure 5.5 The caTRIP Federated Query Builder, developed at Duke University, uses metadata consistent with that in caDSR to populate its query tool. The Her2Neu Status is the same as the one from the CAE system as demonstrated in Figure 5.4.
Genome Sequencing: A Complex Path to Personalized Medicine 67
68
Genome Sequencing Technology and Algorithms
establishing various significant challenges in biomedical informatics at a European level. These challenges were related to linking clinical and genomic information for biomedical research and practice, in issues such as biobanking, genomic-based computerized medical records, pharmainformatics, integrated ontologies, or integrated access to clinical and genomic databases. In summary, the goal was to introduce a strong scientific biological basis to clinical medicine that could lead to better diagnostic and therapeutic procedures. The Network of Excellence (NoE) [56], an initiative started in 2004 to promote biomedical informatics in Europe in support of personalized health care, was created to launch different directions and ideas, aiming to establish a common meeting place within the European Union in the biomedical informatics area. In this NoE, several workpackages were envisioned to deal with dissemination, training and mobility, data modeling, integration and mining as well as four clinical pilots, all of them linking different types of biomedical information. These pilots were designed to create new biomedical informatics approaches in (1) pharmacoinformatics, (2) genomics and infectious diseases, (3) periodontitis, and (4) genetics and colon cancer. These four pilots are examples of the different approaches and problems that biomedical informatics can face in the new environment of genomic medicine, previously described [57]. For instance, the periodontitis pilot project, led at the VU University Medical Center in Amsterdam, aimed to develop informatics methods to store and analyze clinical and genomic information. Periodontitis is an example of chronic infectious and inflammatory disease caused by multiple factors (genetics, infectious, geographical, and environmental) that affect the teeth-supporting tissues. It affects more than 10% of the adult population and nearly 30% of elderly people, increasing the risk of cardiovascular diseases in this group of people. Periodontitis was selected since it seems to have a small number of triggering factors, facilitating clinico-genomic research. A database has been built including clinico-genomic information. PML and other models are being used for representing genotype-phenotype links. In such datasets, data-mining methods are being used to discover links between clinical information and genetic traits. In addition to the intermediate opportunities of developing applications that serve specific biological and clinical needs and the hard challenge of integrating heterogeneous data sources, there are examples of immediate low-hanging fruit. Creating an infrastructure to standardize genetic tests would actualize an immediate benefit of personalized medicine. The first step is establishing a genetic test that identifies the specific mutation, or the set of mutations or functional changes, for the disorder in question. In many cases, such tests are registered on either a research basis or a clinical basis in the GeneTests system (http://www.genetests.org/), an international registry of all available genetic tests for clinical disorders. As of March 2006, there were over 900 different
Genome Sequencing: A Complex Path to Personalized Medicine
69
genes and their variants that could be tested on a clinical basis, and another 300 genes that could be tested on a research basis at almost 600 laboratories worldwide. These tests are performed by a variety of methods, depending on whether the tests look for a specific characteristic set of mutations or determine the DNA sequence for a section of the gene (or the entire gene and its flanking regions). All of these tests use simple free text to report results to the requesting physicians, with little or no standardization, making the results unsuitable for decision support within an electronic medical record and often resulting in information loss. Thus, these are a natural target for a standards-based approach. A specific example of standardizing genetic tests is creating the infrastructure for reporting genetic tests on hemochromatosis. The first step would be for a clinician to order a genetic test to determine if a patient had a genetic mutation that was causative for hemochromatosis. The reason for the test might be suspicious clinical symptoms (e.g., elevated serum ferritin, hepatic cirrhosis or fibrosis, hepatoma) or the diagnosis of hemochromatosis in a sibling. Since there are five different genes that cause various types of hemochromatosis, we will use the HFE gene example since it is the most common gene related to this disorder in the United States. The ARUP laboratory at the University of Utah is one of the five largest molecular diagnostic testing laboratories in the United States. Their HFE test is a targeted mutation analysis looking for the C282Y, H63D, and S65C mutations. C282Y is the most common mutation in the HFE gene, a G to A transition at nucleotide 845, which substitutes a tyrosine (Y) for a cysteine (C) at amino acid position 282. The ARUP result report explains the basic test and includes a textual interpretation, plus algorithms for diagnosis and other screening tests. A positive case report includes all of this information and is sent to the ordering physician as a multipage printed document, unless the order came from another laboratory that can receive an electronic report, in which case it is sent electronically as a multipage textual report. Printed documents are usually put into a paper chart at the receiving end, perhaps then scanned into an electronic record, but the results are not available in computable format using standardized vocabulary and data fields. Therefore these test results are usually limited to the person who ordered the test and certainly not readily accessible to the next physician who sees the patient. This is low-hanging fruit in that the standardized report can be relatively easily agreed upon which then opens it up to more than just the original physician who saw the patient. Standards are being developed for the representation of concepts and test results from the various kinds of genetic tests. The Human Genome Variation Society has a nomenclature for the description of sequence variations (http://www.genomic.unimelb.edu.au/mdi/mutnomen/), the American College of Medical Genetics has policy statements and nomenclature standards (http://www.acmg.net/resources/policies/pol-027.pdf), and the LOINC
70
Genome Sequencing Technology and Algorithms
Committee (Logical Observation Identifiers Names and Codes) has developed codes for the most common genetic tests and is developing specifications for many additional genetic tests (http://www.regenstrief.org/loinc/download/loinc/guide/LOINCManual.pdf). There is also an initiative underway to create standard definitions for genetic-testing panels using the LOINC coding system. This activity is a collaborative effort of the HL7 Clinical Genetics SIG, the LOINC Committee, CDISC, and investigators in the life sciences group at IBM. This activity will make it possible to order genetic tests using standard coded terms and transmit the orders using HL7 messages and standard test codes. Clinical, phenotypic, and family-history-related data that accompanies such orders will also be encoded so that testing laboratories will be able to create algorithms based on data that guide the technologists in their selection of tests to be performed. Results of the testing will be returned in HL7 messages using standard codes as well. The LOINC code for a laboratory test result for the HFE mutation C282Y is: 21695-2 HFE GENE.P.C282Y ARB PT BLD/TISS ORD MOLGEN Translated as a narrative description, the fully specified LOINC name indicates that the C282Y mutation (as named using protein-based nomenclature, “P”) of the HFE GENE was tested for on a blood (BLD) or tissue (TISS) sample. The result value associated with this test code would indicate: no mutation present, heterozygous mutation present, or homozygous mutation present. The precise definition of these test codes is essential if the gene testing results are to be referenced in computable rules and protocols. Work is being done to store results of genetic testing in a coded format in the electronic medical record (EMR). If this test result, LOINC–encoded data, is incorporated into the EMR, then computable recommendations for treatment can be represented using a standard decision support language like Arden Syntax or GELLO (an object-oriented guideline expression language). These computable recommendations can be shared, implemented, and executed in any EMR system as long as the system is using standard coded terminologies such as LOINC, SNOMED CT, or NDF-RT. The basic recommendations are to follow the serum ferritin levels of the patient every few years, keeping in mind that the serum ferritin levels are age and sex dependent. If the serum ferritin becomes elevated, then the physician should suggest that the patient become a blood donor or have frequent phlebotomies. If the serum ferritin level approaches 1,000 ng/mh, then the patient should be evaluated for difficulties arising from iron storage including liver biopsy. If the patient has liver fibrosis and elevated serum ferritin, then the physician should keep a close watch for hepatocellular cancers. Finally, the
Genome Sequencing: A Complex Path to Personalized Medicine
71
appropriate relatives should be tested for the same mutation. All of these recommendations can be structured in a computable knowledge representation format using standards, and once the algorithms have been tested and verified, the set of recommendations can be made available to the worldwide community. The activities of the Biomedical Informatics project to translate clinical research findings into clinical practice and communities will focus on the standards and tool sets by which such translation can occur within the gene-testing domain. To accomplish this task what is needed are clinical geneticists who work on the impact of genomics on clinical information systems; experts who are familiar with LOINC and in a position to incorporate new genetic tests into the LOINC system and into laboratory information systems; and experts who will develop the clinical decision support system rules in a standard form that can be used in all EMRs. One such system is being tested in the Cerner system at the University of Utah and the GE/IDX system at the Intermountain Healthcare, a community health care delivery system that operates within Utah, Idaho, and Wyoming at multiple clinics and hospitals. Ties have already been established with both the Cerner Corporation and the GE Corporation to start work on translational research methods using sharable standards. Additionally there is very close collaborations with the Department of Veterans Affairs field office in Salt Lake City, in addition to work with them on a number of federal interoperability projects relevant to data exchange standards and formats.
5.7 Conclusion Like all interdisciplinary areas, educational needs are demanding and complex. In the case of medical informatics, basic training included topics related, of course, to medicine (including clinical medicine and decision-making, publichealth, or health-services research) and computer science (including AI, probability, or statistics). Personalized medicine will also demand new knowledge and expertise. For instance, physicians will need to learn concepts related to genetics or systems biology, whereas biologists and bioinformaticians will have to deal with clinical data and issues that have been unknown to them until now. Such complexity may even increase more dramatically if nanotechnology begins to have a significant impact on clinical practice beyond current laboratory research. Large initiatives will be necessary to create the tooling, interoperability, and scientific-domain-driven knowledge base to effectively advance personalized medicine. After some preliminary overoptimistic expectations, it seems clear now that genetics alone cannot transform medicine [58, 59]. Research on biomarker discovery that can be detected before clinical onset, has signaled molecular profiling as a great challenge for personalized medicine, but biomarkers with
72
Genome Sequencing Technology and Algorithms
adequate specificity and sensitivity values are still scarce for most diseases. Biomarkers must be evaluated in order to demonstrate their medical significance and cost-effectiveness [60]. In order to achieve this, heterogeneous clinical and genomic data sources must be integrated in scientifically meaningful and productive systems. This will include hypothesis-driven scientific research systems along with well-understood information systems to support such research. These in turn will enable the faster advancement of personalized medicine.
References [1] S. 3822 [109th]: Genomics and Personalized Medicine Act of 2006, http://www. govtrack.us/congress/billtext.xpd?bill=s109-3822. [2] Personalized Health Care RFI, January 26, 2007, Personalized Medicine Coalition Response, http://www.personalizedmedicinecoalition.org/PMC_Response_to_HHS_RFI_on_HIT_ final_1_25_071.pdf. [3] Johnson, J. D., et al., “Genomics—The Perfect Information-Seeking Research Problem,” J. Health Commun., Vol. 10, No. 4, June 2005, pp. 323–329. [4] Mitchell, J. A., F. Fun, and A. T. McCray, “Design of Genetics Home Reference: A New NLM Consumer Health Resource,” J. Am. Med. Inform. Assoc., Vol. 11, 2004, pp. 439–447. [5] Patrick, T. B., et al., “Evidence-Based Retrieval in Evidence-Based Medicine,” J. Med. Libr. Assoc., Vol. 92, No. 2, 2004, pp. 196–199. [6] Sifri, R., et al., “Use of Cancer Susceptibility Testing Among Primary Care Physicians,” Clin. Genet., Vol. 64, 2003, pp. 355–360. [7] Collins, F. S., Shattuck Lecture, “Medical and Societal Consequences of the Human Genome Project,” N. Engl. J. Med., Vol. 341, 1999, pp. 28–37. [8] Abrahams, E., G. S. Ginsburg, and M. Silver, “The Personalized Medicine Coalition: Goals and Strategies,” Am. J. Pharmacogenomics, Vol. 5, No. 6, 2005, pp. 345–355. [9] Meadows, M., “Genomics and Personalized Medicine,” FDA Consum., Vol. 39, No. 6, November-December 2005, pp. 12–17. [10] Nicholson, J. K., “Global Systems Biology, Personalized Medicine and Molecular Epidemiology,” Mol. Syst. Biol., Vol. 2, No. 52, 2006. [11] Haselden, J. N., and A. W. Nicholls, “Personalized Medicine Progresses,” Nat. Med., Vol. 12, No. 5, May 2006, pp. 510–511. [12] West, M., et al., “Embracing the Complexity of Genomic Data for Personalized Medicine,” Genome Res., Vol. 16, No. 5, May 2006, pp. 559–566. [13] Gurwitz, D., J. E. Lunshof, and R. B. Altman, “A Call for the Creation of Personalized Medicine Databases,” Nat. Rev. Drug Discov., Vol. 5, No. 1, January 2006, pp. 23–26.
Genome Sequencing: A Complex Path to Personalized Medicine
73
[14] Davies, S. M., “Pharmacogenetics, Pharmacogenomics and Personalized Medicine: Are We There Yet?” Hematology Am. Soc. Hematol. Educ. Program, 2006, pp. 111–117. [15] Dietel, M., and C. Sers, “Personalized Medicine and Development of Targeted Therapies: The Upcoming Challenge for Diagnostic Molecular Pathology. A Review,” Virchows Arch., Vol. 448, No. 6, June 2006, pp. 744–755. [16] Klein, T. E., et al., “Integrating Genotype and Phenotype Information: An Overview of the PharmGKB Project,” Pharmacogenomics J., Vol. 1, No. 3, 2001, pp. 167–170. [17] Sadee, W., and Z. Dai, “Pharmacogenetics/Genomics and Personalized Medicine,” Hum. Mol. Genet., Vol. 14, Spec. No. 2, October 15, 2005, pp. R207–R214. [18] Woodcock, J., “The Prospects for ‘Personalized Medicine’ in Drug Development and Drug Therapy,” Clin. Pharmacol. Ther., Vol. 81, No. 2, February 2007, pp. 164–169. [19] Weatherall, D., “Sir David Weatherall Reflects on Genetics and Personalized Medicine,” Drug Discov. Today, Vol. 11, Nos. 13–14, July 2006, pp. 576–579. [20] Sujansky, W., “Heterogeneous Database Integration in Biomedicine,” J. Biomed. Inform., Vol. 34, No. 4, 2001, pp. 285–298. [21] Alonso-Calvo, R., et al., “An Agent- and Ontology-Based System for Integrating Public Gene, Protein, and Disease Databases,” J. Biomed. Inform., Vol. 40, No. 1, February 2007, pp. 17–29. [22] Martin-Sanchez, F., et al. “Synergy Between Medical Informatics and Bioinformatics: Facilitating Genomic Medicine for Future Health Care,” J. Biomed. Inform., Vol. 37, No. 1, 2004, pp. 30–42. [23] Del Fiol, G., et al., “Integrating Genetic Information Resources with an HER,” AMIA Ann. Symp. Proc., 2006, p. 904. [24] Mitchell, J. A., “The Impact of Genomics on E-Health,” Stud. Health Technol. Inform., Vol. 106, 2004, pp. 63–74. [25] Searls, D. B., “Data Integration: Challenges for Drug Discovery,” Nat. Rev. Drug Discov., Vol. 4, No. 1, January 2005, pp. 45–58. [26] Sax, U., and S. Schmidt, “Integration of Genomic Data in Electronic Health Records—Opportunities and Dilemmas,” Methods Inf. Med., Vol. 44, No. 4, 2005, pp. 546–550. [27] Mitchell, D. R., and J. A. Mitchell, “Status of Clinical Gene Sequencing Data Reporting and Associated Risks for Information Loss,” J. Biomed. Inform., Vol. 40, No. 1, February 2007, pp. 47–54. [28] Mitchell, J. A., A. T. McCray, and O. Bodenreider, “From Phenotype to Genotype: Issues in Navigating the Available Information Resources,” Methods Inf. Med., Vol. 42, No. 5, 2003, pp. 557–563. [29] Adida, B., and I. S. Kohane, “GenePING: Secure, Scalable Management of Personal Genomic Data,” BMC Genomics, Vol. 7, No. 93, 2006, pp. 1–10.
74
Genome Sequencing Technology and Algorithms
[30] Sanandres-Ledesma, J. A., et al., “A Performance Comparative Analysis Between Rule-Induction Algorithms: Application to Rheumatoid Arthritis,” Lecture Notes in Computer Science, Vol. 3337, 2004, pp. 224–234. [31] Pazzani, M., “Knowledge Discovery from Data?” IEEE Intelligent Systems, Vol. 15, No. 2, 2000, pp. 10–13. [32] Maojo, V., “Domain-Specific Particularities of Data Mining: Lessons Learned,” Lecture Notes in Computer Science, Vol. 3337, 2004, pp. 235–242. [33] Komatsoulis, G. A., et al., “caCORE Version 3: Implementation of a Model Driven, Service-Oriented Architecture for Semantic Interoperability,” J. Biomed. Inform., 2007. [34] Sioutos, N., et al., “NCI Thesaurus: A Semantic Model Integrating Cancer-Related Clinical and Molecular Information,” J. Biomed. Inform., 2006. [35] Hartel, F. W., et al., “Modeling a Description Logic Vocabulary for Cancer Research,” J. Biomed. Inform., Vol. 38, No. 2, 2005, pp. 114–129. [36] Fragoso, G., et al., “Overview and Utilization of the NCI Thesaurus,” Comparative and Functional Genomics, 2004, p. 5. [37] de Coronado, S., et al., “NCI Thesaurus: Using Science-Based Terminology to Integrate Cancer Research Results,” Medinfo, Vol. 11, Pt. 1, 2004, pp. 33–37. [38] Covitz, P. A., et al., “caCORE: A Common Infrastructure for Cancer Informatics,” Bioinformatics, Vol. 19, No. 18, 2003, pp. 2404–2412. [39] Lindberg, C., “The Unified Medical Language System (UMLS) of the National Library of Medicine,” J. Am. Med. Rec. Assoc., Vol. 61, No. 5, 1990, pp. 40–42. [40] Tuttle, M. S., et al., “The Homogenization of the Metathesaurus Schema and Distribution Format,” Proc. Ann. Symp. Comput. Appl. Med. Care, 1992, pp. 299–303. [41] McDonald, C. J., et al., “LOINC, A Universal Standard for Identifying Laboratory Observations: A 5-Year Update,” Clin. Chem., Vol. 49, No. 4, 2003, pp. 624–633. [42] Kudla, K. M. and M. C. Rallins, “SNOMED: A Controlled Vocabulary for Computer-Based Patient Records,” J. Ahima, Vol. 69, No. 5, 1998, pp. 40–44; quiz pp. 45–46. [43] Ashburner, M., et al., “Gene Ontology: Tool for the Unification of Biology: The Gene Ontology Consortium,” Nat. Genet., Vol. 25, No. 1, 2000, pp. 25–29. [44] Whetzel, P. L., et al., “The MGED Ontology: A Resource for Semantics-Based Description of Microarray Experiments,” Bioinformatics, Vol. 22, No. 7, 2006, pp. 866–873. [45] Yu, H., et al., “Representing Genomic Knowledge in the UMLS Semantic Network,” Proc. AMIA Symp., 1999, pp. 181–185. [46] Bodenreider, O., J. A. Mitchell, and A. T. McCray, “Evaluation of the UMLS as a Terminology and Knowledge Resource for Biomedical Informatics,” Proc. AMIA Symp. 2002, pp. 61–65. [47] Konagaya, A., “Trends in Life Science Grid: From Computing Grid to Knowledge Grid: Pharmacogenetics Research Network and Knowledge Base,” BMC Bioinformatics, Vol. 18, No. 7, Suppl. 5, December 2006, p. S10.
Genome Sequencing: A Complex Path to Personalized Medicine
75
[48] Saltz, J., et al., “caGrid: Design and Implementation of the Core Architecture of the Cancer Biomedical Informatics Grid,” Bioinformatics, Vol. 22, No. 15, 2006, pp. 1910–1916. [49] de Knikker, R., et al., ”A Web Services Choreography Scenario for Interoperating Bioinformatics Applications,” BMC Bioinformatics, Vol. 5, No. 25, March 10, 2004. [50] ACGT, http://www.eu-acgt.org. [51] Pérez-Rey, D., A. Anguita, and J. Crespo, “OntoDataClean: Ontology-Based Integration and Preprocessing of Distributed Data,” Lecture Notes in Computer Science, Vol. 4345, 2006, pp. 262–272. [52] Hull, D., et al., “Taverna: A Tool For Building and Running Workflows of Services,” Nucleic Acids Res., Vol. 34 (Web Server issue), July 1, 2006, pp. W729–W732. [53] Wilkinson, M. D., and M. Links, “BioMOBY: An Open Source Biological Web Services Proposal,” Brief Bioinform., Vol. 3, No. 4, December 2002, pp. 331–341. [54] Tobias, J., et al., “The CAP Cancer Protocols—A Case Study of caCORE Based Data Standards Implementation to Integrate with the Cancer Biomedical Informatics Grid,” BMC Med. Inform. Decis. Mak., Vol. 6, June 20, 2006, pp. 25–40, http://stdsnp. genes.nig.ac.jp/index.html/. [55] HL7 SIG, http://www.haifa.ibm.com/projects/software/cgl7/specifications.html. [56] INFOBIOMED, http://www.infobiomed.org. [57] Kulikowski, C., “The Micro-Macro Spectrum of Medical Informatics. Challenges: From Molecular Medicine to Transforming Health Care in a Globalizing Society,” Methods Inf. Med., Vol. 41, 2002, pp. 20–24. [58] Kiberstis, P., and L. Roberts, “It’s Not Just the Genes,” Science, Vol. 296, 2002, p. 685. [59] Lunshof, J. E., M. Pirmohamed, and D. Gurwitz, “Personalized Medicine: Decades Away?” Pharmacogenomics, Vol. 7, No. 2, March 2006, pp. 237–241. [60] Collins, C. D., et al., “The Application of Genomic and Proteomic Technologies in Predictive, Preventive and Personalized Medicine,” Vascul. Pharmacol., Vol. 45, No. 5, November 2006, pp. 258–267.
Part II Genome Sequencing and Fragment Assembly
6 Overview of Genome Assembly Techniques Sun Kim and Haixu Tang
The most common laboratory mechanism for reading DNA sequences (e.g., gel electrophoresis) can determine sequence of up to approximately 1,000 nucleotides at a time.1 However, the size of an organism’s genome is much larger; for example, the human genome consists of approximately 3 billion nucleotides. The most commonly used and most cost-effective process is shotgun sequencing, which physically breaks multiple copies (or clones) of a target DNA molecule into short, readable fragments and then reassembles the short fragments to reconstruct the target DNA sequence. The assembly of short fragments in shotgun sequencing was originally done by hand, but manual assembly clearly is not desirable since it is error prone and not cost-effective. Automatic fragment assembly has been studied for a long period of time [1–11]. Various sequence assemblers contributed to the determination of many genome sequences, including the most recent announcement of the human genome [12, 13].
6.1 Genome Sequencing by Shotgun-Sequencing Strategy Almost all large-scale sequencing projects employ the shotgun strategy that assembles (deduces) the target DNA sequence from a set of short DNA 1. Recently, several promising new experimental techniques have been developed. Note that we survey new sequencing technology in Part I.
79
80
Genome Sequencing Technology and Algorithms
fragments determined from DNA pieces randomly sampled from the target sequence. The set of short DNA fragments, called shotgun reads, are assembled into a set of contigs, or sets of aligned fragments, using a computer program, fragment assembler. The fragment assembly is a conceptually simple procedure that generates longer sequences by detecting overlapping fragments. If the fragment assembly can be done perfectly, the genome sequencing would be a simple problem. However, there are extensive repetitive sequences, repeats in short, in a genomic sequence, which can easily mislead the fragment assembly process (see Figure 6.1). A useful technique to overcome the difficulty from repeats is to sequence both ends of a clone, generating two fragment reads per clone. Since the insert size of clone is known, we know the approximate distance between two fragments. This technique is developed by Hood and his colleagues [14]. The fragment matching information is often referred as mate-pair information, which becomes essential for large-scale shotgun sequencing. The main issue utilizing this information during the assembly process is that we do not know the sequence between the two reads, which can only be deduced by assembling other fragments into a single contig. As a result, we can utilize the clone-length information only after assembly, which results in either a correct or an incorrect assembly based on the clone-length information. See Figure 6.2. One strategy to use the mate-pair information effectively is to assemble contigs as accurate as possible by detecting potentially misassembled contigs and then utilize the mate-pair information using only contigs that are likely to be assembled correctly. See Sections 7.4 and 7.5 for the strategy. 6.1.1
A Procedure for Whole-Genome Shotgun (WGS) Sequencing
In general, assembly of shotgun reads generates a large number of contigs and some of them are misassembled probably due to repetitive sequences in the target DNA. As a result, genome sequencing is usually carried out in multiple steps and, unfortunately, there is no consensus on the steps of all genome-sequencing
Assembly is wrong due to repeats
Figure 6.1 Effect of repeats in fragment assembly. Since assembly is based on overlapping regions between fragments, repeats can easily mislead assembly process, putting all five fragments from two repeat copies into one contig in this figure.
Overview of Genome Assembly Techniques
81
Approximate length in bps
f2 5’ 5’
f1
Read one fragment f1 from one end.
Read another fragment f2 from the other end.
f1 f1
f2
f2 2 kb
6 kb
Figure 6.2 (Upper panel) Mate-pair information. Two fragments, f1 and f2, are read at both ends of the same clone of approximate size of 2 kb. (Bottom panel) The main issue utilizing this information during the assembly process is that we do not know the sequence between the two reads, which can only be deduced by assembling other fragments into a single contig. As a result, we can utilize the clone-length information only after assembly, which result in either a correct or an incorrect assembly based on the clone length information.
projects. We describe a general procedure for genome sequencing below, but we emphasize that procedures used at genome-sequencing centers differ in details. 1. Fragment readout: The sequences of each fragment are determined using an automatic base-calling software. Phred [15, 16] is the most widely used program. 2. Trimming vector sequences: Shotgun reads often contain part of the vector sequences that have to be removed before sequence assembly. 3. Trimming low-quality sequences: Shotgun reads contain poor-quality basecalls and removing or masking out these low-quality base calls often leads to more accurate sequence assembly. However, this step is optional and some sequencing centers do not mask out low-quality
82
Genome Sequencing Technology and Algorithms
4.
5.
6.
7.
base calls, relying on the fragment assembler to utilize quality values to decide true fragment overlaps. Fragment assembly: The shotgun data is input to a fragment assembler that automatically generates a set of aligned fragment called contigs. A survey of fragment assembly algorithms is in Chapter 7. Assembly validation: Some contigs that assembled in the previous steps may be misassembled due to repeats. Since we do not have a priori knowledge on repeats in the target DNA, it is very difficult to verify the correctness of assembly of each contig and this step is largely done manually. There are recent algorithmic developments on automatic verification of contig assemblies (see Section 6.4). Scaffolding contigs: Contigs need to be oriented and ordered. The mate-pair information is a primary information source for this step, thus this step is not achievable if the input shotgun data is not prepared by reading both ends of clones (see Section 6.5 for more details). Finishing: Assuming that all contigs are assembled correctly and contigs are oriented and ordered correctly, we can close gaps between two contigs by sequencing specific regions that correspond to the positions of gaps.
6.2 Trimming Vector and Low-Quality Sequences DNA characters in a fragment are determined from a chromatogram that can be viewed as a plot that shows possibilities of each of four DNA characters. The base call is a DNA character that is determined from a chromatogram and this process is done automatically by a computer program. Phred [15], the most widely used base-calling program, generates numeric values to denote the confidence level of each base call. The quality value of a base is q = −10 × log 10 ( p ) where p is the estimated error probability for the base [15]. Thus a sequencing machine generates two types of output files, one for DNA fragment sequence and another for based-call-quality values for a DNA fragment. Using this information, the next step is to trim sequences from vectors and identify low-quality regions. 6.2.1
The Trimming Vector and Low-Quality Sequences Problem
Input: A set of fragment reads with base-call-quality information; a set of vector sequences. Output: A set of fragment reads with vector sequences trimmed, and with information on start and end positions of good-quality regions.
Overview of Genome Assembly Techniques
83
The problem is relatively simple but it requires a carefully written computer program to handle issues related to fragment trimming, such as vector sequence removal, identification of low-quality regions, and identification of contaminant reads. Chou and Holmes [16] wrote a suite of programs called LUCY for trimming vector and low-quality sequences from each fragment read. The design goal of LUCY is to process fragments so that trimmed fragments have the best overall quality rather than individual base-quality values. LUCY operates in multiple steps. 6.2.1.1 Quality Region Determination
The following is the quality region determination: 1. To determine the good-quality region of a fragment, LUCY first removes low-quality regions from both ends since the beginning and end of each sequence are typically of low quality. This is done by scanning a fragment from its left by identifying the first window of 10 bases with an error probability rate of 0.02 or less. Similarly, it finds the first window from its right end. 2. The next step is to identify regions with high error rates. This is done by scanning the remaining fragment region with a window size of 50 bases and a maximum error probability rate with 0.08, and then with a window size of 10 bases and a maximum probability error rate with 0.3. Any clean range sequences of less than 100 bases will be discarded. 3. Each of remaining clean range sequences will be further examined by checking it with two parameters, the overall maximum error probability (0.025) and the maximum error probability rate of two consecutive bases at the ends (0.02). Note that this step looks at the entire sequence range rather than a window. 6.2.1.2 Vector Splice Site Trimming
This step requires two input files, one with a whole vector sequence and another with two splice-site temple sequences, upsteam and downstream from the insertion point on the vector. Since vector splice sites are usually at the beginning of a fragment where the quality of bases is low, a simple sequence matching does not guarantee to find vector splice sites. Note that vector splice sites may be outside the good-quality region of a fragment and these splice sites will still be sought for since splice-site information is useful (e.g., for estimating clone length). To deal with sequences with low-quality bases, LUCY uses three consecutive windows of 40, 60, and 100 bases. Vector sequences are matched with a minimum match length of 8, 12, and 16 bases within the three windows.
84
Genome Sequencing Technology and Algorithms
6.2.1.3 Contaminant Detection
Contaminates can come from many sources, including Escherichia coli or human, which can be identified easily by sequence comparison methods. The real challenge is to identify contaminates from cloning vectors themselves. Two common contaminants are vector inserts that formed by a vector’s splicing with another vector and short inserts in which case most of a fragment read is a vector sequence. 1. The first step is to prepare a sequence tag pool of, say, 10 bases from a full-length vector sequence. 2. Each fragment is converted into tags and searched against the contaminant tag pools. A contaminant sequence is detected by counting the number of matched tags. Since the tag-matching step is performed after trimming low-quality regions, tag matching is done only for good-quality regions, so matched tags are of very high confidence.
6.3 Fragment Assembly Given a set of shotgun reads with vector and low-quality sequences trimmed, a fragment assembly program is used to assemble the reads to reconstruct the target sequence. 6.3.1
The Fragment Assembly Problem
Input: A set of fragment reads with vector sequences trimmed and with information on start and end positions of good-quality regions; a set of base-call-quality information for each fragment. Output: A set of contigs, each of which is a set of aligned fragments; a set of consensus sequences, a consensus sequence for a contig. Typically, a fragment assembly program generates many sets of assembled fragments instead of a single contiguous sequence. Two major reasons are repeats in the target sequence and low-coverage regions in the shotgun data. See Chapter 7 for details. Most fragment assembly algorithms employ the overlap-layout-consensus approach. 6.3.1.1 Overlap-Layout-Consensus Approach
The most widely used “overlap-layout-consensus” approach, pioneered by Peltola et al. [11], consists of three major steps: (1) identification of candidate overlaps, (2) fragment layout, and (3) consensus sequence generation from the layout. The first step is achieved using string pattern matching techniques, generating possible overlaps between fragments. The second and third steps involve
Overview of Genome Assembly Techniques
85
building models, implicit or explicit, for computing the layout of fragments and generating consensus sequences by enumerating the search space based on the model. Many successful sequence assembly algorithms have been developed based on this paradigm [1–3, 5, 7–9, 12]. There are also other approaches explicitly based on graph theory [6, 17]. These sequence assemblers contributed to the determination of many genome sequences, including the most recent announcement of the human genome [12, 13]. However, sequence assemblers typically generate a large number of contigs rather than single contiguous sequences, due to repetitive sequences and technical difficulties encountered at different stages of a genome-sequencing project. For example, the four most widely used assemblers generated 149 to more than 300 contigs for the N. meningitidis genome of 2.18 Mb [6]. The complete determination of the target sequence from the set of contigs requires a significant amount of work, which is called finishing.
6.4 Assembly Validation Repeats in the genome can easily lead to misassembly of contigs. Thus it is very important to validate contig assembly before scaffolding contigs or finishing gaps between contigs. The most accurate method to detect such misassembled contigs is to perform wet-lab experiments. However, this is time consuming and requires carefully designed experiments. 6.4.1
The Assembly Validation Problem
Input: A set of contigs with fragment alignment information; mate-pair information (some methods, e.g., an information theoretic probabilistic approach in this section, do not require this information). Output: For each base position, prediction on whether the position is assembled correctly or not. Rouchka and States [18] proposed a computational technique to design wet-lab experiments for contig assembly validation, including high clone coverage maps, multiple complete digest mapping, optical restriction mapping, and ordered shotgun sequencing [18]. Recently, several computational techniques without using wet-lab experiments have been developed. These techniques can be implemented as separate computational tools [19–22] or embedded in assemblers. The assembly validation techniques used in the sequence assemblers are reviewed in Sections 7.3, 7.4, and 7.5. Another interesting approach is to compare sequence assemblies from two or more fragment assembly programs to detect misassembled regions and to get a higher quality assembly (e.g., [23]).
86
Genome Sequencing Technology and Algorithms
6.4.1.1 TAMPA
Dew et al. [19] developed a sequence-assembly validation method that utilizes mate-pair data to evaluate and compare assemblies. The basic assumption is that lengths of mate pairs from a clone library follow Gaussian distribution with a mean µ and a standard deviation σ, which can be observed in the plots of clone mate lengths in the final curated assembly. Thus mate pairs are unsatisfied if the distance between pairs are beyond the range µ ± 3σ. TAMPA is a computational geometry-based approach to detecting assembly breakpoints by exploiting constraints that mate pairs impose on each other. They classified mate pairs into four assembly problems, insertion of incorrect sequences between a mate pair, deletion of sequences between sequences of a mate pair, inversion between two or more mate pairs, and transposition of mate pairs. The effects of four assembly problems are stretched (insertion and transposition), compressed (deletion or transposition), and (anti)-normal (inversion). 6.4.1.2 Compression/Expansion Statistics
Zimin and Yorke [22] developed compression/expansion statistics to identify misassembled regions (i.e., assembly regions that are either compressed or expanded due to repeats). The basic idea is again to assume that insert lengths between two mate fragments are distributed according to a Gaussian distribution with a mean and a variance. Given a contig, a global mean and a global variance of insert lengths are estimated. Then a sample mean and sample variance for a given library at a given base position in the contig is computed as follows. The sample mean length is the average length of inserts that covers the given position. The sample variance is estimated as sample standard deviation = global standard deviation
N
where N is the number of inserts that cover the given base position. Using the sample and global means and variance, the CE statistic is computed as C = ( sample mean − global mean ) sample standard deviation The CE statistic is negative at a collapsed region and positive at an expanded region. The thresholds for collapsed and expanded regions are empirically determined as –4 and 4.7, respectively. Using the CE statistic, Zimin et al. developed a method to compare and correct (reconciliate) misassembled regions using two different assemblies.
Overview of Genome Assembly Techniques
87
6.4.1.3 Clone Coverage Analysis
Sequence assembly validation based on the clone coverages can be used to detect large-scale misassemblies, especially collapsed repeats [20, 24]. This approach works in three steps as listed next. 1. Contigs are oriented and ordered. 2. The estimated lengths for all library clone types are computed and clones are classified into two classes, bad clones whose length deviate much from the expected clone length and good clones whose length is within an acceptable range of the expected clone length. 3. A good-minus-bad clone coverage plot is computed for each contig by subtracting the number of bad clones from the number of good clones. The basic idea is simple. Any region where more bad clones are aligned than good clones is likely to be misassembled. 6.4.1.4 An Information Theoretic Probabilistic Approach
This approach [21] identifies misassembled regions using entropy plots that are computed using statistics on the number of patterns per fragment. To compute entropy of fragments, we need to construct a probability model that measures how much each aligned fragment contributes to misassembly. The probability function fi is built using the fragment distribution, a measure used for repeat handling in a sequence assembler called AMASS [3]. From the probability model, we compute entropy at base position p in a contig as: entropy ( p ) =
∑ − prob ( f ) × log( prob ( f ))
p − δ ≤ pos ( f i ) ≤ p + δ
i
i
where pos(fi ) denotes the left-end position of fi in the contig and δ is a user-input parameter (by default, it is the same as the window size used for the fragment distribution calculation). Figure 6.3 shows how the entropy plot can detect misassembled regions.
6.5 Scaffold Generation Some sequence assembly packages include a scaffold generation module that generates scaffolds of assembled contigs [5, 6, 9, 25–28]. There are separate packages such as GigAssembler [26] and Bambus [28], which will be surveyed in this section.
88
Genome Sequencing Technology and Algorithms 60 C8 fragment coverage 50
Coverage
40 30 20 10 0 0
50000 0
100000 150000 Base position (a)
200000
250000
25 Contig8.good–bad
20 15
Coverage
10 5 0 −5 −10 −15 −20 −25 0
50000
100000 150000 Base position (b)
200000
250000
8 C8 entropy 7
Coverage
6 5 4 3 2 1 0 0
50000
100000 150000 Base position (c)
200000
250000
Figure 6.3 (a) The fragment coverage, (b) the clone coverage plot, and (c) the entropy plot, for a contig 8 generated by Phrap (version 2001). There is a misassembled region from 89,415 to 90,332 where the fragment coverages are not distinctly high but the valleys in the clone coverage plot and peaks in the entropy plot are distinct, effectively identifying the misassembled region.
Overview of Genome Assembly Techniques 6.5.1
89
The Scaffold Generation Problem
Input: A set of contigs; mate-pair information; physical/genetic map (optional); expressed sequence tags (EST) (optional). Output: A set of linearly ordered contigs with optional gap-size information between adjacent contigs. In a sense, scaffolding is to generate a linear order of contigs after orienting and ordering contigs. Issues related to scaffolding are: 1. Mate-pair information is erroneous. Some mate pairs come from chimeric clones. More seriously, mate-pair information from fragments aligned at wrong places can easily confuse contig orientation and ordering. 2. There are typically several types of clone libraries that differ in length, say, 2 kb, 10 kb, 40 kb, 100 kb, and so on. In general, mate-pair information from shorter clones is more accurate than that from longer clones. How to utilize mate-pair information of different quality is not trivial. Bambus is one of the hierarchical scaffolding methods that utilize mate-pair information from clones of different length in a hierarchical fashion. 3. There are external information sources, that can be utilized for scaffolding contigs, such as physical/genetic map, alignment information obtained by aligning contigs to already finished genomes, and conservation of gene synteny. 6.5.2
Bambus
The main design philosophy of Bambus is to make a stand-alone scaffolding package so that is can be coupled with other fragment assembly packages and users can easily control parameters for scaffolding contigs. Note that recent assemblers, such as the Celera Whole Genome Assembler, and Arachne, embedded a scaffolding module, but the scaffolding modules are tightly coupled with specific assemblers. In this section, we explain the steps of Bambus, discussing how Bambus deals with the main issues of scaffolding contigs. 6.5.2.1 Edge Bundling to Handle Errors in Mate Pairs
Mate-pair information is very important in orienting and ordering contigs. However, some mate pairs are incorrect due to misassembly of contigs or fragments from chimeric clones. Intuitively, if more mate pairs between two contigs that are consistent in terms of orienting and ordering the two contigs, the mate pairs can be considered to be correct with a higher confidence. This problem can be formally defined and solved by finding the largest clique (i.e., a fully
90
Genome Sequencing Technology and Algorithms
connected subgraph), in the interval graph induced by the inter-conitg gap ranges for the links. The cluster with the most links is chosen and all links in other clusters are given the invalid orientation tags. Bambus allows the user to specify different redundancies to be used for contig links, depending on the confidence in the data. For example, shorter clones, say, of 2 kb, require a smaller number of edge bundling while longer clones, say, of 100 kb, require more edge bundling to be used for contig orientation. The output of this step is a set of contig edges between contig pairs. The remaining task is to orient and order contigs using these contig edges. 6.5.2.2 Contig Orientation
The contig orientation problem is to find a consistent orientation for “all” contigs. This is sometime challenging. Consider three contigs, A, B, and C. The orientation of a contig, say B, with respect to another contig, say A, can be either A → B, A → rc(B), rc(A) → B, or rc(A) → rc(B) where rc(A) and rc(B) represent the reverse complement of A and B, respectively. Suppose that contigs edge impose contig orientation, A → rc(B) and A → rc(C). In addition, suppose that contigs edge impose contig orientation, B → rc(C). Then the three-contig orientation is not consistent. Note that there are clones of different length, thus bundled edges are also of different length. In case there is error in bundled edges, the situation described above can happen. Based on the principle of parsimony, we can consider the contig orientation problem as contig orientation and ordering with computing the minimum number of contig edges to be removed to make a consistent orientation for all contigs. Unfortunately, this problem is an NP hard [4]. Thus a greedy heuristic algorithm is used in practice. In general, the greedy contig orientation algorithm works well since the edge-bundling step generates contig edges of high accuracy. 6.5.2.3 Contig Ordering
The contig-ordering problem is to embed contigs on a line while preserving the gap length suggested by bundled edges. This can be formulated as a problem of topological ordering of contigs subject to length constraints between contigs. An optimization problem formulation would be to find a topological ordering with a minimum number of edges removed. This is also known as an NP-hard problem. Bambus uses an “expand-contract” greedy heuristic for contig ordering. The first step expand is to anchor the first unplaced contig with edges at their maximum allowable length, then traverse the contig graph in a breadth-first search manner to fill in the range. As this is a greedy placement of contig, any contig with inconsistent ordering is not placed. After the expand step, contigs are brought back and placed as close as possible to the midpoint of the range defined by the length constraints of edges. This contraction step allows placement of as many contigs as possible. The resulting ordering may not be
Overview of Genome Assembly Techniques
91
consistent, meaning that two contigs may occupy the same space. This ambiguous placement can be helpful for the final genome-finishing step. 6.5.2.4 Hierarchical Scaffolding
Contig edges from smaller insert libraries have significant fewer errors than those from longer insert libraries. Thus how to utilize clone edges of different accuracies is not trivial. Bambus generates scaffolds of contigs in a hierarchical fashion, starting with contig edges from smallest libraries, say, of 2 kb, then Bambus adds edges of lower-quality from larger insert libraries. The quality of contig edges are evaluated not only by the library length but also by the number of edges connecting two contigs since confirmation from two independent edges is an indication of higher quality in connecting contigs. 6.5.2.5 Untangling
Given a scaffold of contigs, there can be contigs that are involved in multiple paths of contigs. In this case, it may be desirable to untangle those contigs to convert an ambiguous scaffold to a single linear stretch. The Bambus untangler resolves an ambiguous scaffold by iteratively finding the longest nonself-overlapping path in a greedy fashion. If a contig involves multiple potential paths, it may be desirable to break a contig into multiple pieces and then test if single linear—nonoverlapping—stretches of contigs can be generated. Bambus plans to incorporate this implementation in its future release. 6.5.3
GigAssembler
GigAssembler [26] was used for the human genome assembly in the public Human Genome Project [13]. It generated scaffolds using contigs, map, mRNA, EST, and BAC end data. The overview of the scaffold-generation process is as follows. 1. Decontaminating and repeat masking the sequence. RepeatMasker [29] is used to mask known repeats and contaminants from bacteria, vectors, and others. 2. Aligning mRNA, EST, BAC end, and paired-plasmid reads against initial sequence contigs. 3. Creating an input directory structure using map and other data. For the human genome, they used Washington University’s map data. A directory is created for a chromosome and a subdirectory for each fingerprint clone contig. 4. For each fingerprint clone contig, aligning the initial sequence contigs within that contig against each other.
92
Genome Sequencing Technology and Algorithms
5. Using the Gigassembler program within each fingerprint clone contig to merge overlapping initial sequence contigs, and to order and orient the resulting sequence contigs into scaffolds. 6. Combining the contig assemblies into full chromosome assemblies. 6.5.3.1 Preprocessing: Alignment of mRNA, ESTs, BAC Ends, and Paired Reads
Contigs are oriented and ordered by aligning mRNA, ESTs, BAC ends, and paired reads to contigs using a program called psLayout. It reports all matches above a certain minimal quality between query sequences and database sequences. To compute alignments, it collects candidate-matching regions by using 10-mer indices in a set of overlapping 500-base regions of query sequence. Then candidate-matching regions are aligned, especially tolerating intron regions in the case of aligning mRNA and ESTs. Resulting aligned regions are combined using a dynamic programming algorithm. To reduce the effects of repeats, two techniques are used. The first technique is to use repeat sequences (repeats are not masked although they are detected by RepeatMasker). The second technique is to maintain “near best" matches only, which means discard matches (even good ones) if they are below the best match. 6.5.3.2 Assembly and Ordering of Contigs
The GigAssembler operates in many steps. The task is to generate consensus sequences determined by contigs and their ordering. Contigs are ordered and merged gradually into larger ones by building rafts, barges, raft-ordering graphs, and bridge graphs. Next we describe the algorithm in more detail. 1. Build merged sequence contigs, called rafts, from overlapping initial sequence contigs. A score to each aligning pair is assigned, and then the alignments are processed from the best scoring ones to least ones. 2. Build sequenced clone contigs, called barges, from overlapping clones. Barges are constructed in a greedy fashion where the clone overlap is the sum of all initial sequence contig overlaps. Each clone will be assigned a coordinate in the result barge. 3. Once the orientation and order of clones are determined while constructing barges, rafts (merged sequence contigs) can be ordered using a raft-ordering graph. This is a directed graph with two types of nodes, rafts and sequenced clone endpoints. To understand what is happening at this stage, see Figure 6.4. 4. Rafts are bridged with mRNAs, ESTs, paired-plasmid reads, BAC end pairs, and ordering information from the sequencing centers. The resulting graph is called a bridge graph. Bridge is added one at a time, starting with the best scoring, to the ordering graph. The score
Overview of Genome Assembly Techniques
93
AAAA AAAA AAAA A A a1a1a1a1 a2a2a2a2 BBBB BB BB BB BBBB BBBB BBBB B b1b1b1b1b1b1b1
As
Bs
As
Bs
b2b2b2b2 CCCCCCCCCCCCCCCCCCC c1c1c1c1c1c1 c2c2c2
Ae
Ae
Cs
Cs
Be
Ce
Be
Ce
Figure 6.4 How to build a raft-ordering graph. Six initial contigs (a1, a2, b1, b2, c1, c2) are aligned to three clones (A, B, C) (top figure), an ordering graph of clone starts and ends is given (middle figure), and the final raft-ordering graph after adding in rafts to the ordering graph (bottom figure). Form the top figure, we can construct three rafts, a1, b1, a2, b2, c1, and c2, based on their overlaps. Then an ordering graph of clone starts and ends can be constructed based on the positions of clone start and end positions as in the middle figure. The node names As and Ae denotes the start and the end of a clone A, respectively. Finally, the three rafts are added to the ordering graph as in the bottom figure.
function for bridges is based on the type of information. mRNA information is given the highest weight, then paired-plasmid reads, information provided by the sequencing centers, ESTs, and BAC end matches, in that order. 5. Walk the bridge graph to get an ordering of rafts. Each bridge is walked in the order of the default coordinates assigned with a constraint that if a raft has predecessors, all the predecessors must be walked before the raft is walked. 6. A sequence path through each raft is built in a greedy fashion, starting with the longest, most finished initial sequence contig that passes though each section of the raft.
94
Genome Sequencing Technology and Algorithms
7. Build the final sequence for the fingerprint clone contig by inserting the appropriate number of Ns between raft sequence paths.
6.6 Finishing Finishing is labor intensive and constitutes a major bottleneck in any genome-sequencing project. Input to the finishing stage is a set of oriented and ordered contigs. However, as we discussed in previous sections, it is still challenging to verify the correctness of contigs and to generate scaffolds of contigs. Due to the difficulties, there are two different views in pursuing genomelevel sequencing, one in favor of the whole-genome shotgun strategy [30] and another in favor of a hierarchical strategy involving only smaller-scale shotgun sequencing [31] (see Section 6.7 for more discussion). In summary, there should be more efforts in developing frameworks for genome sequencing as well as component tools such as scalable, reliable sequence assemblers and contig assembly- validation methods. As one of the initial efforts, the AMOS project aims at developing open-source whole-genome assembly software for the genome- sequencing community [32].
6.7 Three Strategies for Whole-Genome Sequencing The first whole bacterial genome, H. influenzae, was sequenced at TIGR in 1995 using the whole-genome shotgun strategy [33]. Since then, the whole-genome shotgun strategy has been successfully used for many genomes, including human [12]. Basically, the longer the size of DNA region, the more repeats exist, which becomes clearly a major hurdle to the genome sequencing. There are three different strategies of employing shotgun strategy in wholegenome sequencing. 1. The whole-genome shotgun strategy applies shotgun-sequencing strategy to the whole-genome level. The advantage of this approach is that it is most cost-effective since shotgun data can be prepared in a single step at the whole-genome level. The human genome assembly by Celera was achieved using this strategy [12]. 2. The hierarchical approach uses libraries of different insert size. Libraries of larger insert size are further split into libraries of smaller insert size while keeping track of which library the current library is a descendant of. This often requires a high-resolution genetic map prior to the whole-genome assembly and low-resolution physical map. Shotgun strategy is applied when a library becomes small enough so that the
Overview of Genome Assembly Techniques
95
current assembly algorithm could determine the target sequence with confidence. Since the library hierarchy information can be easily used to produce the target sequence, this approach may produce more accurate genome sequences. The major drawback of this approach is time and cost of genome sequencing. The human genome consortium used this approach [13]. 3. The hybrid approach, called pooled genomic indexing—a technique pioneered at the Baylor College of Medicine, employs both the hierarchical and the whole-genome shotgun approaches, but without physical and genetic mapping information. This approach combines two different types of shotgun reads, one from the whole-genome shotgun and the other from the shotgun sequencing of individual BACs. BACs are generated by using large insert BAC clones and a minimum tiling path of BACs that covers the whole genome is computed. Then shotgun strategy with a low coverage is applied to a set of selected BACs from the tiling path. In parallel, the whole-genome shotgun strategy is applied to generate another set of shotgun data at the whole-genome level. These two shotgun data sets are combined to determine the whole-genome sequence. The brown Norway rat genome was assembled with this strategy [34].
6.8 Discussion In this section, we briefly summarize techniques for genome sequencing. For more information, readers may refer to several review articles on genome sequencing [35–37]. Although genome sequencing still remains an open problem, recent advances in computational techniques make it possible to sequence very large eukaryotic genomes such as Drosophila melanogaster [27] and the human genome [12, 13]. We discuss some of the recent trends in genome-sequencing strategies next. 1. To achieve very large-scale genome sequencing, it is necessary to have shotgun data of very high quality (see [27]). Otherwise, is not possible to distinguish repeats from errors in the shotgun data. What is really interesting is that recent assemblers attempt to correct errors in the input shotgun data before sequence assembly [5, 6]. There is no guarantee to correct errors without knowing the target sequence. Indeed, EULER, a genome assembly package, names this procedure as data corruption instead of error correction. Nonetheless, this is a promising technique that works for large-scale sequence assembly.
96
Genome Sequencing Technology and Algorithms
2. Repeat boundaries are identified before sequence assembly and then contigs are assembled up to the boundaries [5, 27]. Like the error correction, there is no guarantee to identify the repeat boundaries correctly without knowing the target sequence, but this is another promising technique. 3. Computational techniques to ensure the correctness of contig assembly becomes more important. Correctness can be checked using the characteristics of the shotgun data (i.e., random sampling).2 There are two ways to utilize the characteristics of data, on the fragment level [2, 5, 9, 27] and there is also an interesting approach based on pattern statistics [21]. 4. Mate-pair information and base-call-quality values become an essential data for genome sequencing. 6.8.1
A Thought on an Exploratory Genome Sequencing Framework
As hinted in Section 6.5.2, contigs that are involved in multiple paths of contigs may be broken into smaller pieces and can be tested if linear paths can be generated. To realize this idea, methods for assembly validation that detect misassembled regions in contigs are much needed (see Section 6.4). We tested this idea for several bacterial genomes including Agrobacterium [38]. The schematic overview of a genome-sequencing framework [39] developed at DuPont is depicted in Figure 6.5. This approach can be viewed as “a hypothesis generation and validation paradigm” in search of a set of correctly assembled contigs and their ordering. All decisions made at user interaction points are hypotheses that will be subsequently tested with larger clones in the next step. This approach was successful in assembling several genome sequences. For example, 502 contigs in the Phrap assembly of the Agrobacterium shotgun data were grouped and ordered into only 15 sets of contigs (the largest set longer than 2 Mb) using a Web interface in a single iteration of our genome-sequencing framework. Note that there are four replicons in the Agrobacterium genome. As more accurate assembly validation methods are developed, this technique might be useful for automating the sequencing of microbial genomes. By embedding sequence assembly modules into an assembly package, such as Minimus [40].
2. There are regions where sampling is biased due to biological reasons. However, random sampling can be assumed as a whole shotgun data.
Overview of Genome Assembly Techniques
97
A set of DNA fragments
Sequence assembler
A set of contigs Assembly validation
Split contigs Clone linkage information
Ordering contigs
A set of groups of contigs Large clone linkage information
Ordering groups
A set of groups of groups
Figure 6.5 A framework for genome sequencing. This framework is to search for a set of correctly assembled contigs and their ordering in an iterative fashion.
Acknowledgments Sun Kim was supported in part by a Career DBI-0237901 from the National Science Foundation (United States) and a grant from the Korea Insititute of Science and Technology Information. We thank the anonymous reviewer for his or her valuable comments.
References [1]
Green, P., http://www.phrap.org.
[2]
Sutton, G., et al., “TIGR Assembler: A New Tool for Assembling Large Shotgun Sequencing Projects,” Genome Science and Technology, Vol. 1, 1995, pp. 9–19.
[3]
Kim, S., and A. M. Segre, “AMASS: A Structured Pattern Matching Approach to Shotgun Sequence Assembly,” Journal of Computational Biology, Vol. 6, No. 4, 1999.
[4]
Kececioglu, J. D., and E. W. Myers, “Combinatorial Algorithms for DNA Sequence Assembly,” Algorithmica, Vol. 13, 1995.
98
Genome Sequencing Technology and Algorithms
[5] Batzoglou, S., et al., “Arachne: A Whole-Genome Shotgun Assembler,” Genome Research, Vol. 12, No. 1, 2002, pp. 177–189. [6] Pevzner, P. A., et al., “An Eulerian Path Approach to DNA Fragment Assembly,” PNAS, Vol. 98, 2001, pp. 9748–9753. [7] Huang, X., “A Contig Assembly Program Based on Sensitive Detection of Fragment Overlaps,” Genomics, Vol. 14, 1992. [8] Huang, X., “An Improved Sequence Assembly Program,” Genomics, Vol. 33, 1996. [9] Huang, X., and A. Madan, “CAP3: A DNA Sequence Assembly Program,” Genome Research, Vol. 9, No. 9, 1999, pp. 868–877. [10] Huang, X. et al., “PCAP: A Whole-Genome Assembly Program,” Genome Res., Vol. 13, 2003, pp. 2164–2170. [11] Peltola, H., et al., “SEQAID: A DNA Sequence Assembling Program Based on a Mathematical Model,” Nucleic Acids Res., Vol. 12, No. 1, Pt. 1, 1984, pp. 307–321. [12] Venter, J. C., et al., “The Sequence of the Human Genome,” Science, Vol. 291, 2001, pp. 1304–1351. [13] Lander, E. S., et al., “Initial Sequencing and Analysis of the Human Genome,” Nature, Vol. 409, 2001, pp. 860–921. [14] Roach, J. C., “Pairwise End Sequencing: A Unified Approach to Genome Mapping and Sequencing,” Genomics, Vol. 26, 1995, pp. 345–353. [15] Ewing, B., et al., “Base-Calling of Automated Sequencer Traces Using Phred. I. Accuracy Assessment,” Genome Research, Vol. 8, 1998, pp. 175–185. [16] Chou, H. H., and M. H. Holmes, “DNA Sequence Quality Trimming and Vector Removal,” Bioinformatics, Vol. 17, No. 12, 2001, pp. 1093–1104. [17] Idury, R., and M. S. Waterman, “A New Algorithm for DNA Sequence Assembly,” Journal of Computational Biology, Vol. 2, No. 2, 1995, pp. 291–306. [18] Rouchka, E. C., and D. J. States, “Sequence Assembly Validation by Multiple Restriction Digest Fragment Coverage Analysis,” Proc. of Intelligent Systems for Molecular Biology (ISMB), 1998, pp 140–147. [19] Dew, I. M., et al., “A Tool for Analyzing Mate Pairs in Assemblies (TAMPA),” J. Comput. Biol., Vol. 12, No. 5, 2005, pp. 497–513. [20] Kim, S., et al., “Enumerating Repetitive Sequences from Pairwise Sequence Matches,” manuscript, DuPont Central Research, 2000. [21] Kim, S., et al., “A Probabilistic Approach to Sequence Assembly Validation,” ACM SIGKDD Workshop on Data Mining in Bioinformatics (BioKDD2001), 2001, pp. 38–43. [22] Zimin, R., and J. A. Yorke, “Assembly Reconciliation Method,” http://www.genome. umd.edu/reconciliation.htm, 2007. [23] Shatkay, H., et al., “ThurGood: Evaluating Assembly-to-Assembly Mapping,” Journal of Computational Biology, Vol. 11, No. 5, 2004, pp. 800–811
Overview of Genome Assembly Techniques
99
[24] Kim, S., et al., “A Computational Approach to Sequence Assembly Validation,” manuscript, DuPont Central Research, 2000. [25] She, X., et al., “Shotgun Sequence Assembly and Recent Segmental Duplications Within the Human Genome,” Nature, Vol. 431, 2004, pp. 927–930. [26] Kent, W. J., and D. Haussler, “Assembly of the Working Draft of the Human Genome with GigAssembler,” Genome Res., Vol. 11, 2001, pp. 1541–1548. [27] Myers, G., et al., “A Whole-Genome Assembly of Drosophila,” Science, Vol. 287, 2000, pp. 2196–2204. [28] Pop, M., et al., “Hierarchical Scaffolding with Bambus,” Genome Res., Vol. 14, No. 1, 2004, pp. 149–159. [29] Smit, A., “Repeat Masker,” http://repeatmasker.genome.washington.edu/, 2007. [30] Weber, J. L., and E. Myers, “Human Whole-Genome Shotgun Sequencing,” Genome Research, Vol. 7, 1997, pp. 401–409. [31] Olson, M., and P. Green, “A ‘Quality-First’ Credo for the Human Genome Project,” Genome Research, Vol. 8, No. 5, 1998, pp. 414–415. [32] AMOS: A Modular Open-Source Assembler, http://amos.sourceforge.net/, 2007. [33] Fleischmann, R. D., et al., “Whole-Genome Random Sequencing and Assembly of Haemophilus Influenzae Rd.,” Science, Vol. 269, No. 5223, 1995, pp. 496–512. [34] Gibbs, R. A., et al., (Rat Genome Sequencing Project Consortium), “Genome Sequence of the Brown Norway Rat Yields Insights into Mammalian Evolution,” Nature, Vol. 428, No. 6982, 2004, pp. 493–521. [35] Pop, M., et al., “Genome Sequence Assembly: Algorithms and Issues,” IEEE Computer, Vol. 35, No. 7, 2002, pp. 47–55. [36] Pop, M., et al., “Shotgun Sequence Assembly,” Advances in Computers, Vol. 60, June 2004. [37] Batzoglou, S., “Algorithmic Challenges in Mammalian Genome Sequence Assembly: Special Review,” in D. M. Jordel, P. Little, and S. Subramaniam, (eds.), Encyclopedia of Genomics, Proteomics, and Bioinformatics, New York: John Wiley & Sons, 2005. [38] Wood, D. W., et al., “The Genome of Agrobacterium Tumefaciens C58: Insights into the Evolution and Biology of a Natural Genetic Engineer,” Science, 2001, pp. 2317–2323. [39] Kim, S., “The AMASS Genome Sequencing Package,” Advances in Genome Biology and Technology Conference, February 2002. [40] Sommer, D. D., et al., “Minimus: A Fast, Lightweight Genome Assembler,” BMC Bioinformatics, Vol. 8, February 26, 2007, p. 64.
7 Fragment Assembly Algorithms Sun Kim and Haixu Tang
Fragment assembly algorithms take, as an input, a set of fragment reads with vector sequences trimmed and information on the start and end positions of good quality regions, and together with base-call-quality information. The output from fragment assembly algorithms is a set of aligned fragments, called contigs, and a consensus sequence for each contig. Repeats that are often longer than the average fragment length make the assembly very difficult, thus assembly algorithms generates many contigs rather than single contiguous sequences. See Chapter 6 for more information. One of the most effective methods to handle repeats is to use mate-pair information from a clone, which most modern fragment assembly algorithms utilize. However, it is not trivial to utilize the mate-pair information. The main issue utilizing this information during the assembly process is that we do not know the sequence between the two reads, which can only be deduced by assembling other fragments into a single contig. As a result, we can utilize the clone-length information only after assembly, which results in either a correct or an incorrect assembly based on the clone-length information (see Figure 6.2). In this chapter, we will survey nine fragment assembly algorithms. Recent assemblers are comprehensive genome-sequencing packages, rather than just fragment assembly algorithms, thus description of these algorithms includes all issues in genome assembly: Celera Whole Genome Assembler [1] in Section 7.4 and Arachne [2] in Section 7.5. The rest of this chapter is organized as follows. In the next six sections, we describe seven fragment assembly algorithms among widely used ones as of
101
102
Genome Sequencing Technology and Algorithms
today. The following section describes two more algorithms that are interesting due to the algorithm design.
7.1 TIGR Assembler The TIGR assembler [3] is the first assembler that was used to assemble a whole bacterial genome, H. influenzae, using the shotgun sequencing strategy in 1995. The TIGR assembler operates in two phases: pairwise comparison of fragments and fragment assembly. A consensus sequence is automatically determined as fragments are assembled. It handles repetitive sequences with increased match criteria, while incorporating mate-pair information in assembly.
7.1.1
Merging Fragments with Assemblies
After computing pairwise overlaps among input fragments, a fragment is merged with the current assembly if the four conditions are satisfied: minimum length of overlap, minimum similarity in the overlap region as a percentage of the best possible score, maximum length of overhang, and maximum number of local errors. Overhang is referred to as the region in the alignment where two fragments do not match, and the length of overhang is the maximum number of overhang at both ends of the alignment. Local errors are the number of base-pair mismatches between the fragment and the assembly in any given contiguous 32 bp in the overlap region. The maximum number of local errors is used to reject overlap with clustered errors, which might survive the similarity test. For example, 16 errors spread out evenly over a 400-bp overlap (96% similarity) is more likely to be a real overlap than 8 errors clustered in a 32-bp window of 400-bp overlap (98% similarity). Note that, when a fragment is considered for assembly, match criteria are computed against the current assembly, not against a fragment, thus the assembly does not rely on pairwise alignment, although selection of a fragment for assembly does.
7.1.2
Building a Consensus Sequence
When a fragment is added to the current assembly, TIGR does not commit to a consensus sequence but keeps a history of what bases have been aligned to that position in the past. This results in a column or profile where a count of bases plus gaps is recorded. From this profile, a consensus sequence is generated after the assembly is completed, selecting the most frequent bases for consensus sequence.
Fragment Assembly Algorithms 7.1.3
103
Handling Repetitive Sequences
TIGR uses two strategies to handle repetitive sequences: increased match criteria for fragments possibly from repeats, and clone-length constraints. Fragments from repetitive sequences are identified by the number of potential overlaps each fragment has based on pairwise comparisons. Any fragment with the number of overlaps more than a threshold is labeled as being from repetitive sequences. When a repeat fragment is added to the current assembly, the stringency of the match criteria is increased so that inexact repeats (for example, 80% similarity for Alu repeats) can be distinguished. Even with strict match criteria, it is impossible to avoid false overlap identifications when repeats are longer than the average fragment size. TIGR incorporates mate-pair information that maintains distance between two reads from the same clone to further eliminate false overlaps.
7.2 Phrap Phrap is one of the most widely used fragment assemblers. However, there is no published paper that describes the algorithm for Phrap. The description of the Phrap algorithm is based on the online documentation at http://www.phrap.org. 1. All matching words of length minmatch or greater are identified and a sorted list of the words are created. 2. For each pair, a band around a diagonal that is defined by matching words is defined, and overlapping words are merged. SWAT, an implementation of the Smith-Waterman algorithm, is used to find matching segments above a preset minscore between matches. By masking out the current matched regions, SWAT is recursively applied between matches. 3. A log-likelihood ratio (LLR) score for comparing two hypotheses, a hypothesis that the reads truly overlap and another hypothesis that they are from repeats of 95% similarity, is computed. LLR utilizes the probability of the observed data under each hypothesis that is quantified using the interpretation of the Phrap qualities in terms of error probabilities. Since LLR is a ratio score of the two hypotheses, a positive LLR score implies a true overlap while a negative LLR score implies an overlap from repeats. 4. Fragment layout is progressively generated using a sorted list of matches in terms of their LLR scores.
104
Genome Sequencing Technology and Algorithms
5. The consensus sequence of each contig is generated as a mosaic of individual read by building a weighted graph using selected positions of matches as vertices (ends of alignments, and midpoints of perfectly matching segments of sufficient length). Unidirectional edges from 5’ to 3’ positions within a single read, with weight equal to the total quality of the sequence between the two nodes. To cross-link matches, bidirectional edges with weight 0 between aligned bases in overlapping reads are added. Then, a standard maximum weight single-source maximum weight path is computed (the complexity is linear in relation to the number of vertices).
7.3 CAP3 CAP3 is an improved version of its previous releases, CAP2 [4] and CAP [5]. Three major improvements in CAP2 were: (1) performance improvement by filtering out potentially nonoverlapping fragments, (2) identification of chimeric fragments by computing and utilizing an error rate vector for each input fragment, and (3) handling repetitive sequences by constructing repetitive contigs while merging two different contigs. CAP2 was further improved to CAP3 as described in this section. There is also a parallel version of CAP, called PCAP [6]. 7.3.1
Automatics Clipping of 5’ and 3’ Poor Quality Regions
Clipping is done using both base-quality values and sequence similarities, and by defining and using the notion of good regions of a read as follows: 1. Any sufficiently long region of high-quality values; 2. Any sufficiently long region that is highly similar to a good highquality region of another read defined to be good. The 3’ and 5’ clipping positions of a read are determined by the boundaries of good regions. 7.3.2
Computation and Evaluation of Overlaps
A global alignment of two fragments is computed over the band determined by the optimal local alignment while clipping poor quality regions. Each overlap is evaluated by five measures: minimum length, minimum percent identity, minimum similarity score, differences between overlapped reads at bases of
Fragment Assembly Algorithms
105
high-quality values, and difference between the rate of error at the overlap being considered with respect to the sequencing error rate estimate. 7.3.3
Use of Mate-Pair Constraints in Construction of Contigs
The mate-pair information is used while assembling contigs: 1. An initial layout of reads is performed by use of a greedy method in decreasing order of overlap scores. 2. The quality of the current layout is assessed by mate-pair constraints, (i.e., existence of paired reads and their distance). 3. A region of the current layout with the largest number of unsatisfied constraints is located and then the unsatisfied constraints are checked for being satisfiable by aligning unaligned pairs according to their distance. If such a region exists, corrections to the region are made by adding satisfiable mate pairs and breaking unsatisfiable pairs, and then steps 2 and 3 are repeated. Otherwise, the correction procedure is terminated. 4. Contigs are ordered and linked with unsatisfied constraints (i.e., using mate pairs in two different contigs).
7.4 Celera Assembler The Celera Whole Genome Assembler (WGA) is the first fragment assembler that successfully assembled WGS reads from large eukaryotic genomes (>100 Mbp). The description of the Celera assembler is based on the article describing the Drosophila genome assembly [1]. Before we explain the Celera WGA, we will survey an approach by Kececioglu and Myers [7] which was a basis for the Celera WGA. 7.4.1
Kececioglu and Myers Approach
The Kececioglu and Myers approach [7] formulated the fragment assembly problem in a formal way. The algorithm operates in four steps: 1. Construct a graph of approximate overlaps between every pair of fragments. 2. Assign an orientation to each fragment (i.e., choose the forward or reverse complement sequence for each fragment). 3. Select a set of overlaps that induces a consistent layout of the oriented fragments.
106
Genome Sequencing Technology and Algorithms
4. Merge the selected overlaps into a multiple sequence alignment, and vote on a consensus. Each of the four phases can be viewed as a separate problem. Unfortunately, the last three problems are NP-complete and are handled by a heuristic algorithm in the Kececioglu and Myers approach. 7.4.1.1 Overlap Graph Construction
There are four possible types of overlaps between two fragments f 1 and f 2: a fragment f 1 dovetails to another fragment f 2 when a suffix of f 1 aligns to a prefix f 2;f 1 contains f 2 when f 2 is a substring of f 1. An overlap graph G = (V, E, w) represents fragments with vertex set V, and overlaps with edge set E. An edge weight function w gives the plausibility metric for an overlap. To choose which of the possible overlaps actually appears between each vertex pairs in the overlap graph, Kececioglu and Myers choose the maximum likelihood overlap among all possible overlaps based on the edit distance and the probabilistic metric from Chvatal and Sankoff. The probabilistic metric is computed as follows: given an overlap between two fragments, the overlap of length l + d is a string containing l exact matches (substrings that both fragments agree) and d mismatches. The Chvatal and Sankoff algorithm computes the probability that a string of length l + d which contains the fixed substring of length l occurs. Finally, overlap edges are culled according to the two following criteria: (1) match significance, and (2) error distribution. An overlap with match probability less than match significance threshold is rejected. Assuming a binomial distribution in the error, they also reject some edges by error distribution threshold. Roughly speaking, an overlap with highly clustered errors is rejected by a probabilistic argument. 7.4.1.2 Fragment Orientation
Once an overlap graph has been constructed, the next step is to determine the orientation of each fragment. This is formulated as an optimization problem with an objective function: maximize w (O ) =
∑ opp( f 1, f 2 ) + (
( f 1 , f 2 ) ∈(O ,O )
∑ opp( f 1, f 2 ) same ( f 1, f 2 )
f 1 , f 2 ) ∉(O ,O )
where same ( f 1, f 2) = max (w ( f 1, f 2)), w ( f 1, f 2) and opp ( f 1, f 2) = max (w ( f 1, f 2), w ( f 2, f 1)). This problem is NP-complete, shown by the reduction from the maximum weight problem [7]. Thus, Kececioglu and Myers proposed a greedy approximation algorithm.
Fragment Assembly Algorithms
107
7.4.1.3 Fragment Layout
A layout of fragment overlaps is generated by traversing the oriented graph according to the following four constraints: 1. 2. 3. 4.
Every vertex in G has at most one incoming edge. The edges do not form cycles. No two dovetail edges leave the same vertex. No containment edge f 1⇒ f 2 is followed by a dovetail edge f 2 → f 3.
A set of edges that satisfies constraints 1 and 2 is called a branching. A branching can be seen as a collection of trees. A set of edges that also satisfies constraints 3 and 4 is called a dovetail-chain branching. Then the layout problem is formulated as the maximum dovetail-branching problem, which can be solved by repeating the generation of the maximum weight branching and then generating subproblems by removing a pair of edges violating constraints 3 and 4. Obviously, it grows exponentially. Kececioglu and Myers presented two techniques to reduce search space. 7.4.1.4 Multiple Sequence Alignment
Once pairwise sequence alignments of two fragments are computed, a trace graph of aligned characters in each column is constructed. A trace gives us a sequence of characters. Thus the multiple alignment phase determines a trace first and then generates a sequence by topologically sorting connected components in the trace. The problem is how to find the best trace from a graph of characters. The basic idea to solve the problem is that any pairwise alignment that is already determined forms a trace. Given the pairwise alignments, compute a supergraph whose supernodes are the sequences to be aligned and whose superedges are defined by pairwise alignments. A superedge is weighted by a similarity metric which is the sum of similarities between characters in two sequences. Now the goal is to find a tree of pairwise traces with the maximum weight for a supergraph. The heuristic proposed by Kececioglu and Myers is to compute a closure between pairwise traces and add them to the superedges and then to compute the maximum weight-spanning tree. 7.4.2
The Design Principle of the Celera Whole-Genome Assembler
The following is the design principle of the Celera Whole-Genome Assembler. 1. The clone-mate information is used to generate scaffold of the genome as well as contigs. One important feature is that assembly of contigs
108
Genome Sequencing Technology and Algorithms
were tried to be as accurate as possible by detecting repeat boundaries while assembling contigs. Contigs without repeats are named U-unitigs. Note that use of clone-length information is reliable as long as assembly of contigs (unitigs) are correct; see Figure 6.2 for issues using mate-pair information. 2. The assembler can utilize external information such as physical/genetic maps. 3. The assembler places fragment reads in a series of stages, starting with the safest moves to more aggressive ones. The stage and evidence for a read’s placement are open to inspection, providing an audit trail of the assembler’s decision.
7.4.3
Overlapper
Fragment overlaps are detected with a criteria requiring fewer than 6% difference and at least 40 bp of unmasked sequence, which is similar to the well-known seed-and-extend method developed for BLAST [8]. A simple statistic can show the existence of extensive repeats, for example: the average number of overlaps per fragment read was 33.7, which is a lot higher than the coverage of the shotgun data (14.6). Like many other assemblers, unusually high number of overlaps for a fragment can be used for detecting repeats.
7.4.4
Unitigger
A collection of fragments whose arrangement is not contested by overlaps from other fragments were assembled into unitigs, contigs with more stringent criteria. Each unitig is examined to see whether it contains repeats or not as follows. Unitigs, that represent nonrepetitive unique DNA, are called U-unitigs. Potential repeat boundaries in U-unitigs are computed and then U-unitigs are extended up to these repeat boundaries. To detect misassembled unitigs, WGA used A-statistic, a log-odds ratio of the probability from the distribution of fragment start points. U-unitigs are unitigs with A-statistic of 10 or higher. A-statistic is calculated as follows. Let F be the number of fragments in the database and G be the (estimated) size of a genome. Assume that fragments are not oversampled. For a unitig with k fragments and distance ρ between the start of its first fragment and the start of the last fragment, the probability of seeing k − 1 start points in the interval of length ρ is [( pF /G )k /k !]exp( − pF /G ). If the unitig was the result of collapsing two repeats, the probability is [( 2 pF /G )k /k !]exp( −2 pF /G ). A-statistic is the log of the ratio of the two probabilities.
Fragment Assembly Algorithms
109
By detecting repeat boundaries, unitigs are extended on the order of a fragment length (i.e., extension of an unitig up to a fragment length). Repeat boundaries are detected as follows. Whenever a unitig A overlaps with two different unitigs B and C, but B and C overlapping regions fail to overlap, a repeat boundary can be detected by aligning B and C using a dynamic programming technique.
7.4.5
Scaffolder
The Celera Scaffolder [9] uses a greedy algorithm that uses a graph structure constructed using mate-pair information or BAC ends, to orient and order unitigs. We briefly sketch the algorithm in two steps. 7.4.5.1 Bactig Graph Construction
Bactigs are contiguous sequences from a common source region obtained by shotgun strategy and assembly process. In the Drosophila shotgun data, there were four different types of library clones of lengths, 2k, 10k, 50k, and 100k. The graph is constructed in three steps. 1. The initial graph: A bactig graph G is a weighted, undirected multigraph, without self loops. Each bactig Bi gives rises to precisely two nodes v, w in the graph and an edge e connecting v and w. Then, an edge e is associated with a standard deviation σ(e) of length variation. 2. Edge bundling: Let M denote the set of mate edges between nodes, v and w. Edges are bundled by first greedily choosing a median-length mate edge e ′ ∈ M , whose length l (e ′) is within 3σ(e) of l(e) and then bundling all of these with e. The weight of an edge e, w(e), is 1 if e is a simple mate edge and ∑ ki =1 w (e i ) if e is obtained by bundling k mate edges {e1, ..., ek}. 3. Transitive reduction: This step is to transitively reduce long mate edges. Recall that there are four types of library clones of lengths, 2k, 10k, 50k, and 100k. By transitively reducing long edges from a larger clone library, jumping edges that can cause ambiguity in ordering are removed in the ordering. A mate edge e from v to w can be transitively reduced on to the path p if e and P have approximately the same length (three times of variation). If this is the case, the edge e is removed from the graph and the weight for every mate edge mi in P is increased by w(e). In this way, the final bactig graph is constructed.
110
Genome Sequencing Technology and Algorithms
7.4.5.2 Path-Merging Algorithm
The bactig-ordering problem is defined and solved by a heuristic algorithm called a greedy path-merging algorithm. Edges are classified into happy edges and unhappy edges. A happy edge is an edge whose length is within three times of length variations. Otherwise, an edge is unhappy. Given a bactig graph G, find an ordering φ of G that maximizes the sum of weights of happy edges.
7.5 Arachne Arachne [2] has also been used for assembling large genomes and has a number of well-designed features for large-scale genome projects: an efficient and sensitive procedure for finding real overlaps, a procedure for scoring overlaps that achieves high accuracy by correcting errors before assembly, read merger based on forward-reverse links, and detection of repeat contigs by mate-pair consistency. The Arachne assembly algorithm operates as follows: 1. Overlap detection and alignment: Pairwise overlaps are computed by a three-step process: (a) identify all k-mers (k = 24) and merge overlapping shared k-mers, (b) extend the shared k-mers to alignments, and (c) refine the alignment by dynamic programming. 2. Error correction: Sequencing errors are detected and corrected by generating multiple alignments among overlapping reads using a majority rule based on quality base score (by Phred). 3. Evaluation of alignments: Each alignment is evaluated by an overall penalty score for an alignment which combines individual discrepancy in base calls (considering the quality score). Overlaps incurring a high-penalty score are discarded. This step detects repeats and chimerical reads. 4. Identification of mate pairs: Complexes of mate pairs are built by starting with combining two overlapping paired pairs at both ends and iteratively adding paired reads matching both ends. 5. Contig assembly: Potential repeat boundaries are identified by aligning fragments that extend the same fragment. All fragment reads are merged and extended until a repeat boundary is reached. 6. Detection of repeat contigs: Once contigs are assembled, contigs that are potentially misassembled due to repeats are identified by two criteria, the depth of coverage and the consistency of linking to other contigs. 7. Creation of supercontigs or scaffold generation: Once contigs are assembled and repeat contigs are marked, supercontigs are built incrementally
Fragment Assembly Algorithms
111
using unmarked contigs. To make this procedure recursive, every contig becomes a supercontig and then merged incrementally using a priority queue. 8. Filling gaps in supercontigs: Once the scaffolds of contigs are generated, gaps between contigs are attempted to be filled using repeat contigs by computing shortest paths between contigs and then performing breadth first search for contigs that can be placed within a supercontig. 7.5.1
Contig Assembly
Reads are merged into contigs up to potential repeat boundaries. Repeat boundaries are detected based on inconsistency in extending overlaps. For example, suppose that a read r can be extended by both x and y, but x and y do not overlap each other. Then a repeat boundary can be detected by aligning x and y. However, this could result in detecting too many potential repeat boundaries. Arachne uses two techniques, dominated reads and subreads, to eliminate spurious repeat boundaries. 7.5.2
Detecting Repeat Contigs and Repeat Supercontigs
Two heuristics are used to detect contigs and supercontigs that are misassembled due to repeats. 1. Density of reads: Arachne computes the log-odds ratio, a given density of reads representing a unique region of genome log a density representing at least two copies of a repeated region Any contigs with a log-odds ratio less than one are marked as repeated. This technique is also used in the Celera assembler (see Section 7.4). 2. Consistency of forward-reverse links: For two contigs A and B, the distance between two is estimated whenever there are at least two links. The mean and standard deviation, denoted by d(A, B) and ERR(A, B), respectively, are computed and used for detecting repeat (super)contigs with two rules explained here. (a) Rule 1: If d(A, B) < −2,000 − 4 × ERR(A, B) then the (super)contigs are marked as repeated; (b) Rule 2: if contig A is linked to both B and C, then from d(A, B) and d(A, C) and the lengths of B and C, we can compute d(B, C), the estimated gap or overlap length between B and C. If d(B, C) < −2,000 − 4 × ERR(B, C) then A is marked as repeated.
112
Genome Sequencing Technology and Algorithms
7.6 EULER We review a graph-based fragment assembly approach, called EULER [11]. There are previous approaches related to EULER, sequencing by hybridization [12, 13] and the Idury-Waterman algorithm [14]. 7.6.1
Idury-Waterman Algorithm
Idury and Waterman [14] proposed a new way to assemble shotgun reads by computational methods in sequencing by hybridization (SBH) [12, 13]. To reconstruct a sequence ATGCAGGTCC, we can adopt a Hamiltonian-path approach as follows: ATG, TGC, GCA, CAG, AGG, GGT, GTC, TCC. There is a directed edge from ATG to TGC since the suffix TG of ATG is equal to the prefix TG of TGC. After constructing a graph, the sequence is determined by finding a Hamiltonian path through the graph. Since constructing a Hamiltonian path is NP-complete, Pevzner came up with an alternative formulation of the graph. In the new graph G, each k − 1 tuple becomes a node, and an edge is set from node N1 to N2 when there is an instance of a probe whose prefix of size k − 1 is N1 and whose suffix of size k − 1 is N2. With the new graph, the sequence can be determined by a finding Eulerian tour, for which a simple linear time algorithm is known (Figure 7.1 shows a Hamiltonian graph H and an Eulerian graph G for the sequence ATGTGCCGCA). Another advantage of the Eulerian graph approach is that there might be cases where the Eulerian tour determines one sequence, but the Hamiltonian tour cannot determine a sequence due to the existence of the multiple Hamiltonian tours for the same sequence. The basic idea of Idury and Waterman algorithm is that the error rate in the shotgun reads is not that high so there is a sufficient number of occurrences of the true k-tuples (as the probes in SBH). For example, if there are 2% errors, ATG
AT
TGC
TG GC
GCA CAG
CA G
H
AG AGG GG GGT GT TCC
GTC
Figure 7.1 Graphs H and G for ATGCAGGTCC.
CC
TC
Fragment Assembly Algorithms
113
there will be 50 − k correct tuples in every 50 nucleotide sequence on average. Idury and Waterman rely on the fact that there is multiple coverage to sidestep these errors. From a shotgun data, an Euler graph on (k − 1)-tuples for the k-tuples is constructed and the consensus sequence is generated by searching for the Eulerian tours. 7.6.2
An Overview of EULER
The proposed approach uses the Eulerian-superpath approach and does not employ the traditional “overlap-layout-consensus” approach. As in the Idury and Waterman approach, a de Bruijin graph, denoted by G, is constructed using tuples of length l and the Eulerian path of the graph is computed for fragment assembly (see Section 7.6.1). However, there are two major differences in two approaches, of EULER and of Idury and Waterman. 1. Errors in fragments makes a tangle of erroneous edges, which becomes a major hurdle in computing the Eulerian path. EULER tries to correct as many errors in fragments as possible before computing the Eulerian path by solving the error-correction problem. 2. EULER solves the Eulerian-superpath problem where a series of transformations of an Eulerian graph and collection of paths to a new graph and collection of paths are made to compute a solution to the fragment assembly problem. 7.6.3
Error Correction and Data Corruption
To correct errors in the input shotgun data, we need to know the target sequence. However, the target sequence is supposed to be assembled using the (erroneous) input shotgun reads. This seemingly impossible task is formulated as computing Gl, the set of all tuples in G. Of course, Gl is unknown but their strategy is to approximate Gl without knowing the sequence of G. The error correction problem was proposed to eliminate errors in the shotgun data. The basic idea comes from an observation that a single error in a read s affects at most l l-tuples in s and l l-tuples in the reverse complement of s that point to the same sequencing error. EULER employs the greedy approach that looks for error corrections in the reads that reduce the size of Sl by 2l. This greedy procedure sometimes introduces errors rather than correcting errors. For example, this procedure corrected 234,410 errors and introduced 1,452 errors in the N. meningitidis genome project. Pevzner et al. argue that introducing errors is not bad as long as consistent overlaps can be detected so that false edges in the de Bruijin graph can be reduced (the introduced errors can be corrected later).
114
7.6.4
Genome Sequencing Technology and Algorithms
Eulerian Superpath
Once |Sl |, the set of all l-tuples from S = {s1, ..., sn} is computed by solving the error correction problem, the de Bruijin graph G(Sl ) with vertex set Sl−1 (the set of all l − 1-tuples from S = {s1, ..., sn}) is computed as follows. A directed edge from an l − 1-tuple v ∈Sl−1 to another w ∈Sl−1 is added if Sl contains an l-tuple whose the first l − 1 prefix coincides with v and whose the last l − 1 suffix coincides with w. 7.6.4.1 Eulerian Superpath Problem
Given an Eulerian graph and a collection of paths in this graph, the Eulerian-superpath problem is formulated as one to find an Eulerian graph path in this graph that contains all these paths as subpaths. The Eulerian-superpath problem is solved by transforming both the graph P and the system of paths G1 into a new graph G1 and a new system of paths P1. Such transformation is called equivalent if there exists a one-to-one correspondence between Eulerian superpaths in (G, P) and (G1, P1). The goal is to make a series of transformations
(G , P ) → (G 1 , P1 ) → K → (G k , Pk )
Vin
x
Vmid
y
Vout
Vout
Vin z Vmid
Figure 7.2 The x,y-detachment: edges x and y are substituted with a new edge z. As a result, all three paths have direct paths from x to y.
Fragment Assembly Algorithms
115
where the final system of paths Pk are single edge. Due to the equivalent transformations, every solution of the Eulerian-superpath problem in (Gk, Pk) provides a solution of the Eulerian-superpath problem in (G, P) (i.e., contigs). The transformations are implemented using two techniques, detachment and cut (Figure 7.1). The x, y-detachment is a transformation that adds a new edge z = (vin, vout) and deletes the edges x and y from G (see Figure 7.2 for more details). The x-cut is a transformation that removes the edge x from all paths that contain the edge (see Figure 7.3 for more details). The authors claim that detachments and cuts are powerful techniques to untangle the graph and to reduce the fragment assembly to the Eulerian path problem for bacterial genomes that the authors used. 7.6.5
Use of Mate-Pair Information
There are two EULER programs that utilize mate-pair information, EULER-DB and EULER-SF. EULER-DB tries to untangle repeats using mate-pair information by treating each clone-mate pair as artificial paths in the graph with their expected lengths. EULER-SF generates scaffolds using matepair information.
y1
y3 y4
x
y2
y3 y4
y1 x
y2
Figure 7.3 The x-cut is used for a tangle (i.e., a repeat that does not have a read-path). The edge x is deleted from all paths that contains x.
116
Genome Sequencing Technology and Algorithms
7.7 Other Approaches to Fragment Assembly In this section, we survey a couple of interesting approaches although they are not widely used in the genome-sequencing community as of now. The first approach by Parsons et al. [15] employed a genetic algorithm approach. Kim and Segre [16], the second approach, proposed a structured pattern-matching approach using exact patterns sampled from the shotgun reads. 7.7.1
A Genetic Algorithm Approach
Parsons et al. [15] proposed an approach based on genetic algorithms. Since the fragment assembly problem is NP-complete, the application of genetic algorithms makes sense. Furthermore, as Parsons, Forrest, and Burks argue, the basic idea underlying all genetic algorithms (to generate a better composite solution from good partial solutions) is well suited to the fragment assembly. 7.7.1.1 Representing the Sequence Assembly Problem
A permutation of integers represents a sequence of fragment numbers where successive fragments overlap if there is evidence for overlapping. They used the sorted-order representation for the permutation ordering [17]. There are two requisite properties for a legal ordering: (1) all fragments should be present in the ordering, and (2) there should be no duplication in the ordering. Consider the example in Figure 7.4. In the example, each 3-successive bits represent a fragment number in the bit string. The bit string represents a sequence, 2 7 1 5 3. Each number is associated with another number (associate) representing its position in the ordering. The position of the number 2 is first, so 2 is associated with 1. Then the sequence is sorted in ascending order, becoming a new
0 1
0 1 1
1 0 0
2
7
1
5
3
1
2
3
4
5
1
5
4
2
3
1 1
0
1 0
1
0 1
Bit string
0
2 (Start position)
Start position
Figure 7.4 How to get a permutation ordering, 1 5 4 2 3.
Key values
Intermediate layout
Fragment Assembly Algorithms
117
sequence 1 2 3 5 7. The permutation is a sequence of associates, that is, 3 1 5 4 2. The final step is to read the sequence starting at the position 2 designated as a starting position by the last number in the original bit string. This reading gives us the permutation, 1 5 4 2 3. 7.7.1.2 Fitness Function
The choice of a fitness function is crucial to the success of a genetic algorithm. Parsons, Forrest, and Burks used two fitness functions: F1 and F2. Let I = f [0], f [1], ..., f [n − 1] be an ordering of fragments, where f [i] = j denotes that fragment j appears in position i of the ordering. The first fitness function F1 is defined by F1(I ) =
n −2
∑w i=0
f [i ] , f [i +1]
where wi, j is the pairwise overlap strength of fragment i and j. Note that this function examines only the overlap strength of directly adjacent fragments in the ordering. The optimization process finds a layout that maximizes this function. The second fitness function F2 considers the overlap strength among all possible pairs, in which fragments with strong overlap are far apart. n −1 n −1
F2(I ) = ∑ ∑ i − j × w f [i ] , f [i +1] i=0 j =0
Then four genetic operators, such as order crossover, edge recombination, inversion, and transposition, have been applied while the resulting ordering is evaluated using the fitness function. An important property in the operators is that they try to preserve or extend existing contigs. Especially, the two mutationlike operators do not contract existing contigs but only try to extend them. The basic idea is to allow for the evolution of larger contigs by treating smaller contigs as basic building blocks. 7.7.2
A Structured Pattern-Matching Approach
Kim and Segre [16] proposed a fragment assembly algorithm that uses exact matches of short patterns randomly selected from fragment data to identify fragment overlaps, construct an overlap map, and finally deliver a consensus sequence. 7.7.2.1 Overview of AMASS
AMASS starts with sampling patterns of fixed length from shotgun data, and then finds all occurrences of sampled patterns in shotgun data. The occurrences
118
Genome Sequencing Technology and Algorithms
of patterns are used to detect overlapping fragments and to handle repeats which is a major hurdle to fragment assembly. Two distributions, the pattern distribution and the fragment distribution, are used to identify fragments that come from repeats. Then, assembly of fragments from nonrepeat regions are assembled first, and later contigs are extended to include repeat regions. Figure 7.5 illustrates how AMASS works. 7.7.2.2 Building Contigs
AMASS represents a fragment as an ordered set of pattern occurrences (probes) and their interprobe spacings and fragment overlaps are determined by this representation. Contig is built in a greedy fashion, adding the fragment with the best score at a time as summarized next. 1. Build a pairwise overlap table. 2. Take best pair of unassigned fragments and build an initial contig. 3. Compute overlap score between the current contig and remaining fragments. Pattern dist.
Shotgun data
Sample patterns from each fragment and collect statistics
Remove those patterns
Fragment dist.
Sample more patterns and find matches
Pattern represented shotgun data
Contigs
Assemble fragments
Figure 7.5 An overview of the AMASS fragment assembler.
Fragment Assembly Algorithms
119
4. Selecting a fragment with the highest score, grow the current contig by adding the fragment. 5. Repeat steps 3 and 4 while overlap scores are still significant. 6. Go to step 2 while unassigned fragments remain. 7.7.2.3 Handling Repeats
Repeats are handled in three different ways: (1) use of satellite matching, (2) the pattern distribution, and (3) the fragment distribution. To handle very short repeats, AMASS employs a technique called satellite matching which tests for coexistence of very short patterns around a pair of common pattern (probe) occurrences. If probes are from two different repeat copies, their surrounding regions will be different for short repeats and the satellite-matching test can identify probes from different repeat copies quickly and effectively. Any probe occurrences that fail for the satellite-matching test will be discarded so that they are not used for contig construction. Probe occurrences are further screened using the pattern distribution that shows the distribution of the number of probe occurrences versus the number of probes. Any probes that occur an unusual number of times are obviously from repeats and discarded. This technique is used by nearly all fragment assemblers to quickly filter out probes from repeats. AMASS also attempts to identify fragments that come from repeats using the fragment distribution that the distribution of the number of fragments versus the number of probe occurrences in a fragment. The basic idea is that fragments from long repeats will exhibit a significant increase in the number of probe occurrences since probes from a repeat copy will occur in other repeat copies of the same repeat. AMASS marks fragments in the tail region as repeat fragments. Contigs are constructed for nonrepeat regions using the set of fragments that are not marked as repeat fragments and repeat regions are expanded later whenever ambiguity in overlapping regions are acceptable.
7.8 Incompleteness of the Survey Genome sequencing is a very important problem in biology but it is a very difficult computational problem. As a result, there has been a lot of research on computational techniques. There are many fragment assembly algorithms and this survey is not complete by any means. Among the assemblers we could not include in this chapter due the page limitation are Atlas [18], Phusion [19], STROLL [20], the Staden package [21], JAZZ [22], AMOS [23], and Minimus [24]. The genome sequencing is still unresolved and more sophisticated
120
Genome Sequencing Technology and Algorithms
techniques will be continuously developed, especially for short fragment assembly, some of which are described in this volume.
Acknowledgments Sun Kim was supported in part by a Career DBI-0237901 from the National Science Foundation (United States) and a grant from the Korea Institute of Science and Technology Information. We thank the anonymous reviewer for valuable comments.
References [1] Myers, E. W., et al., “A Whole-Genome Assembly of Drosophila,” Science, Vol. 24, 2000, pp. 2196–2204. [2] Batzoglou, S., et al., “Arachne: A Whole-Genome Shotgun Assembler,” Genome Res., Vol. 12, No. 1, 2002, pp. 177–189. [3] Sutton, G., et al., “TIGR Assembler: A New Tool for Assembling Large Shotgun Sequencing Projects,” Genome Science and Technology, Vol. 1, 1995, pp. 9–19. [4] Huang, X., “An Improved Sequence Assembly Program,” Genomics, Vol. 33, 1996. [5] Huang, X., “A Contig Assembly Program Based on Sensitive Detection of Fragment Overlaps,” Genomics, Vol. 14, 1992. [6] Huang, X., et al., “PCAP: A Whole-Genome Assembly Program,” Genome Res., Vol. 13, 2003, pp. 2164–2170. [7] Kececioglu, J. D., and E. W. Myers, “Combinatorial Algorithms for DNA Sequence Assembly,” Algorithmica, Vol. 13, 1995. [8] Altschul, S. F., et al., “Basic Local Alignment Search Tool,” Journal of Molecular Biology, Vol. 215, 1990, pp. 403–410. [9] Huson, D. H., “The Greedy Path-Merging Algorithm for Sequence Assembly,” RECOMB 2001, 2001, pp. 157–163. [10] Kim, S., et al., “Enumerating Repetitive Sequences from Pairwise Sequence Matches,” manuscript, DuPont Central Research, 2000. [11] Pevzner, P. A., et al., “An Eulerian Path