SHRiMP: Accurate Mapping of Short Color-space Reads
[['Next generation sequencing ( NGS ) technologies are revolutionizing the study of variation among individuals in a population .', 'The ability of sequencing platforms such as AB SOLiD and Illumina ( Solexa ) to sequence one billion basepairs ( gigabase ) or more in a few days has enabled the cheap re-sequencing of human genomes , with the genomes of a Chinese individual [1] , a Yoruban individual [2] , and matching tumor and healthy samples from a female individual [3] sequenced in the last few months .', 'These resequencing efforts have been enabled by the development of extremely efficient mapping tools , capable of aligning millions of short ( 25–70 bp ) reads to the human genome [4]–[10] .', 'In order to accelerate the computation , most of these methods allow for only a fixed number of mismatches ( usually two or three ) between the reference genome and the read , and usually do not allow for the matching of reads with insertion/deletion ( indel ) polymorphisms .', 'These methods are extremely effective for mapping reads to the human genome , most of which has a low polymorphism rate , and so the likelihood that a single read spans multiple SNPs is small .', 'While matching with up to a few differences ( allowing for a SNP and 1–2 errors ) is sufficient in these regions , these methods fail when the polymorphism level is high .', 'NGS technologies are also opening the door to the study of population genomics of non-model individuals in other species .', 'Various organisms have a wide range of polymorphism rates - from 0 . 1% in humans to 4 . 5% in the marine ascidian Ciona savignyi .', 'The polymorphisms present in a particular species can be used to discern its evolutionary history and understand the selective pressures in various genomic loci .', "For example , the large amount of variation in C . savignyi ( two individuals' genomes are as different as Human and Macaque ) was found to be due to a large effective population size [11] .", 'The re-sequencing of species like C . savignyi ( and regions of the human genome with high variability ) requires methods for short read mapping that allow for a combination of several SNPs , indels , and sequencing errors within a single ( short ) read .', 'Furthermore , due to larger-scale “structural” variation , only a fraction of the read may match to the genome , necessitating the use of local , rather than global , alignment methods .', 'Previous short read mapping tools typically allow for a fixed number of mismatches by separating a read into several sections and requiring some number of these to match perfectly , while others are allowed to vary [4] , [6] , [8] .', 'An alternative approach generates a set of subsequences from the read ( often represented as spaced seeds [7] , [10] , [12] ) , again in such a manner that if a read were to match at a particular location with some number of mismatches , at least one of the subsequences would match the genome [5] , [9] .', 'While these methods are extremely fast , they were developed for genomes with relatively low levels of polymorphism , and typically cannot handle a highly polymorphic , non-model genome .', "This becomes especially apparent when working with data from Applied Biosystem's SOLiD sequencing platform ( AB SOLiD ) .", 'AB SOLiD uses a di-base sequencing chemistry that generates one of four possible calls ( colors ) for each pair of nucleotides .', 'While a sequencing error is a change of one color-call to another , a single SNP will change two adjacent color positions .', 'Hence a read with two ( non-adjacent ) SNPs and a sequencing error will differ from the reference genome in five different positions .', 'Simultaneously , the nature of the di-base sequencing code allows for the identification ( and correction ) of sequencing errors , so by carefully analyzing the exact sequence of matches and mismatches within a read , it is possible to determine that the read and the genome differ by two SNPs .', 'While efficient mappers for color-space sequences have been developed [5] , [13] , they translate the genome to color-space , and directly compare to the color-space read .', 'The complexity of the color-space representation makes the identification of complex variation such as adjacent SNPs and short indels challenging or impossible with these tools .', 'In this paper we develop algorithms for the mapping of short reads to highly polymorphic genomes and methods for the analysis of the mappings .', 'We demonstrate an algorithm for mapping short reads in the presence of a large amount of polymorphism .', 'By employing a fast k-mer hashing step and a simple , very efficient implementation of the Smith-Waterman algorithm , our method conducts a full alignment of each read to all areas of the genome that are potentially homologous .', 'Secondly , we introduce a novel , specialized algorithm for mapping di-base ( color-space ) reads , which allows for an accurate , non-heuristic alignment of AB SOLiD reads to a reference genome .', 'Finally , we introduce methodology for evaluating the accuracy of discovered alignments .', 'Because a read may match the genome in several locations with variable amounts of polymorphism , we develop a statistical method for scoring the hits , allowing for the selection of the most probable variants , and filtering of false positives .', 'Our methods are implemented as part of SHRiMP: the SHort Read Mapping Package .', 'To demonstrate the usefulness of SHRiMP we re-sequenced a Japanese Ciona savignyi genome on the SOLiD platform .', 'Preliminary estimates obtained in the course of sequencing the reference genome indicate that the SNP heterozygosity is 4 . 5% , whereas indel heterozygosity is 16 . 6% .', 'This species represents the most challenging known test case for the detection of polymorphisms with short read technologies .', "We aligned the SOLiD reads of the Japanese individual to the C . savignyi reference genome using both SHRiMP and AB's read mapper .", "SHRiMP is able to identify 5-fold more SNPs than AB's mapper , while also capturing 70 , 000 indel variants ."], ['The SHRiMP algorithm draws upon three recent developments in the field of sequence alignment: q-gram filter approaches , introduced by Rasmussen et al [14]; spaced seeds , introduced by Califano and Rigoutsos [15] and popularized by the PatterHunter family of tools [7] , [10]; and specialized vector computing hardware to speed up the Smith-Waterman Algorithm [16]–[18] to rapidly find the likely locations for the reads on the genome .', 'Once these locations are identified , we conduct a thorough , Smith-Waterman-based algorithm to rigorously evaluate the alignments .', 'In this section we will provide a brief exposition of the methods used to align short reads in SHRiMP ( a more thorough description of each of these steps is in Methods ) .', 'The AB SOLiD sequencing technology introduced a novel dibase sequencing technique , which reads overlapping pairs of letters and generates one of four colors ( typically labelled 0–3 ) at every stage .', 'Each base is interrogated twice: first as the right nucleotide of a pair , and then as the left one .', 'The exact combinations of letters and the colors they generate are shown in Figure 2A .', 'The sequencing code can be thought of as a finite state automaton ( FSA ) , in which each previous letter is a state and each color code is a transition to the next letter state .', 'This automaton is demonstrated in Figure 2B .', 'It is notable that the sequence of colors is insufficient to reconstruct the DNA sequence , as reconstruction requires knowledge of the first letter of the sequence ( or the last letter of the primer , which is fixed for a single run of the technology ) .', 'The AB SOLiD sequencing technology has the remarkable property of differentiating between sequencing errors and biological SNPs ( under the assumption that the reference genome has no sequencing errors ) : a SNP changes two adjacent readouts of the color-space code , while a sequencing error is unlikely to happen at two adjacent positions by chance ( the technology does not sequence adjacent letters at adjacent time points ) .', 'At the same time , however , the color-space code introduces certain complexities .', 'Let us consider a comparison done by first translating the color-space read code into the letter-space sequence .', 'Notice that a single sequencing error would cause every position after the place of error to be mistranslated ( Figure 3B ) .', 'Consequently , most approaches have translated the letter-space genome into the corresponding color code .', 'However , this is problematic: since the color-coding of every dibase pairing is not unique , a string of colors can represent one of several DNA strings , depending on the preceding base pair .', 'For example , a string of zeroes could be translated as a poly-A , poly-C , poly-G or poly-T string .', 'There is an additional drawback to translating the genome into color-space code: a sequence of matches and mismatches in color-space does not map uniquely into letter-space similarity .', 'For example , a single SNP results in two sequential color-space mismatches .', 'However , given two consecutive colors , there are 9 possible ways to generate two mismatches .', 'Of these , only 3 correspond to a SNP , while the rest lead to DNA strings that completely differ from the reference .', 'This is illustrated in Figure 3D .', 'We propose an alternate approach .', 'Our key observation is that while a color-space error causes the rest of the sequence to be mistranslated , the genome will match one of the other three possible translations .', 'This is illustrated in Figure 4C .', 'Consequently , we adapt the classical dynamic programming algorithm to simultaneously align the genome to all four possible translations of the read , allowing the algorithm to move from one translation to another by paying a “crossover” , or sequencing error penalty .', 'If one wishes for a probabilistic interpretation of the algorithm , one can consider the FSA in Figure 2B to be a Hidden Markov Model , where the letter is the hidden state , and the color-space sequence is the output of the model .', 'By taking the cross product of this HMM with the standard pair-HMM associated with the Smith-Waterman algorithm , we can allow all of the typical alignment parameters , including the error penalty , to be probabilistically motivated as the log of the probability of the event , and trained using the Expectation-Maximization algorithm .', 'It is notable that our approach handles not only matches , mismatches , and sequencing errors , but also indels .', 'Because the sequences are aligned in letter-space ( to be precise , they are aligned and translated simultaneously ) , indels can be penalized using the standard affine gap penalty with no further modification of the algorithm .', 'In the SHRiMP algorithm , we only apply the special color-space Smith-Waterman algorithm in the final stage .', 'For the initial stages , we convert the genome from letter-space to color-space , and search for k-mer matches as well as perform vectorized Smith-Waterman strictly in color-space .', 'In order to better incorporate SNPs in color-space data , we use a spaced seed that allows for two adjacent mismatching colors between the read and the reference genome .', 'Once all of the reads are mapped , for every read and mate-pair we compute mapping confidence statistics .', 'Initially these are computed for each read; however , they are then combined to compute likelihoods of accidental matches for mate-pairs .', 'In our experiments , we used SHRiMP to compare 135 million 35 bp reads from a tunicate Ciona savignyi to the reference genome [22] .', 'The fragments were sequenced from sheared genomic DNA with an AB SOLiD 1 . 0 instrument .', "In the following sections we first describe the running time of SHRiMP at different parameter settings , and then evaluate the quality of our alignments compared to the Applied Biosystem's read mapping program ."], ['The algorithm starts with a rapid k-mer hashing step to localize potential areas of similarity between the reads and the genome .', 'All of the spaced k-mers present in the reads are indexed .', 'Then for each k-mer in the genome , all of the matches of that particular k-mer among the reads are found .', 'If a particular read has as many or more than a specified number of k-mer matches within a given window of the genome , we execute a vectorized Smith-Waterman step , described in the next section , to score and validate the similarity .', 'The top highest-scoring regions are retained , filtered through a full backtracking Smith-Waterman algorithm , and output at the end of the program if their final scores meet a specified threshold .', 'The SHRiMP algorithm is summarized in Figure 6 .', 'In Computing Statistics for Single Reads , we briefly introduced the concepts of the pchance , pgenome and normalized odds of a hit .', 'In this section we expand on the details regarding the construction of pchance and pgenome .', 'In these formulas we make use the following definitions: Below , we refer to this denominator term as .', 'We similarly define .', 'For the C . savignyi polymorphism analysis we ran SHRiMP with the following parameters .', 'We used the spaced seed “11110111” and required two hits per 40-base window to invoke the Smith-Waterman algorithm .', 'The Smith-Waterman scoring parameters were set to +100 for a matching base , −90 for a mismatch , −250 and −100 to open and extend a gap respectively , and −300 for a crossover ( sequencing error ) .', 'The minimum Smith-Waterman score thresholds were 1000 for the vectorized first pass and 1275 for the final alignment pass .', 'We discarded alignments with pchance less than 0 . 05 , and to remove reads from known repetitive sequence we required normodds to be at least 0 . 8 .']]
['Introduction', 'Results/Discussion', 'Methods']
['The development of Next Generation Sequencing technologies , capable of sequencing hundreds of millions of short reads ( 25–70 bp each ) in a single run , is opening the door to population genomic studies of non-model species .', 'In this paper we present SHRiMP - the SHort Read Mapping Package: a set of algorithms and methods to map short reads to a genome , even in the presence of a large amount of polymorphism .', 'Our method is based upon a fast read mapping technique , separate thorough alignment methods for regular letter-space as well as AB SOLiD ( color-space ) reads , and a statistical model for false positive hits .', 'We use SHRiMP to map reads from a newly sequenced Ciona savignyi individual to the reference genome .', 'We demonstrate that SHRiMP can accurately map reads to this highly polymorphic genome , while confirming high heterozygosity of C . savignyi in this second individual .', 'SHRiMP is freely available at http://compbio . cs . toronto . edu/shrimp .']
['Next Generation Sequencing ( NGS ) technologies are revolutionizing the way biologists acquire and analyze genomic data .', 'NGS machines , such as Illumina/Solexa and AB SOLiD , are able to sequence genomes more cheaply by 200-fold than previous methods .', 'One of the main application areas of NGS technologies is the discovery of genomic variation within a given species .', 'The first step in discovering this variation is the mapping of reads sequenced from a donor individual to a known ( “reference” ) genome .', 'Differences between the reference and the reads are indicative either of polymorphisms , or of sequencing errors .', 'Since the introduction of NGS technologies , many methods have been devised for mapping reads to reference genomes .', 'However , these algorithms often sacrifice sensitivity for fast running time .', 'While they are successful at mapping reads from organisms that exhibit low polymorphism rates , they do not perform well at mapping reads from highly polymorphic organisms .', 'We present a novel read mapping method , SHRiMP , that can handle much greater amounts of polymorphism .', 'Using Ciona savignyi as our target organism , we demonstrate that our method discovers significantly more variation than other methods .', 'Additionally , we develop color-space extensions to classical alignment algorithms , allowing us to map color-space , or “dibase” , reads generated by AB SOLiD sequencers .']
['computational biology/genomics']