Exon-spanning reads sometimes have very small anchors (defined here as 1–7 bp) in one of the exons. Correctly aligning these reads is extremely difficult because a 1- to 7-bp anchor will align to numerous locations, even in a local FM index. Arguably the most effective approach to align such short-anchored reads is to use splice site information to remove the introns computationally before alignment. We can identify and collect splice site locations when aligning reads with long anchors and then rerun HISAT for the short-anchored reads (Supplementary Fig. 9 ). This two-step approach is very similar to the two-step algorithm in TopHat2.
More specifically, in the two-step HISATx2 method, we use the first run of HISAT (HISATx1) to generate a list of splice sites supported by reads with long anchors. In the second run we then use the splice sites to align reads with small anchors. For example, consider the unmapped read spanning exons e2 and e3 (the upper portion ofSupplementary Fig. 9 ). The right part of the read will be mapped to exon e3 using the global search and extension operations, leaving a short, 3-bp segment unmapped. We then check the splice sites found in the first run of HISAT to find any splice sites near this partial alignment. In this example, we find a splice site supported by a read spanning exons e2 and e3 with long anchors in each exon. On the basis of this information, we directly compare the 3 bp of the read and the corresponding genomic sequence in exon e2. If it matches, we combine the 3-bp alignment with the alignment of the rest of the read. This ‘junction extension’ procedure that makes use of previously identified splice sites is represented by brown arrows in the figure.
As we show in our experiments on simulated reads, this two-step strategy produces accurate alignment of reads with anchors as small as 1 bp (see Results). Although HISATx2 has considerably better sensitivity, it takes twice as long to run as HISATx1. As an alternative, we developed a hybrid method, HISAT, which has sensitivity almost equal to that of HISATx2 but with the speed of HISATx1. HISAT collects splice sites as it processes the reads, similarly to the first run of HISATx2. However, as it is processing, it uses the splice sites collected thus far to align short-anchored reads. In the vast majority of cases, it can align even the shortest anchors because it has seen the associated splice sites earlier. This result follows from the observation that most splice sites can be discovered within the first few million reads, and most RNA-seq data sets contain tens of millions of reads. As our results show, HISAT provides alignment sensitivity that very nearly matches the two-step HISATx2 algorithm, with a run time nearly as fast as the one-step HISAT method.
The hybrid approach is also effective in aligning reads spanning more than two exons, which are more likely to have small anchors. The alignment sensitivity for such reads increases from 53% using HISATx1 to 95% using HISAT (Supplementary Fig. 2 ).
More specifically, in the two-step HISATx2 method, we use the first run of HISAT (HISATx1) to generate a list of splice sites supported by reads with long anchors. In the second run we then use the splice sites to align reads with small anchors. For example, consider the unmapped read spanning exons e2 and e3 (the upper portion of
As we show in our experiments on simulated reads, this two-step strategy produces accurate alignment of reads with anchors as small as 1 bp (see Results). Although HISATx2 has considerably better sensitivity, it takes twice as long to run as HISATx1. As an alternative, we developed a hybrid method, HISAT, which has sensitivity almost equal to that of HISATx2 but with the speed of HISATx1. HISAT collects splice sites as it processes the reads, similarly to the first run of HISATx2. However, as it is processing, it uses the splice sites collected thus far to align short-anchored reads. In the vast majority of cases, it can align even the shortest anchors because it has seen the associated splice sites earlier. This result follows from the observation that most splice sites can be discovered within the first few million reads, and most RNA-seq data sets contain tens of millions of reads. As our results show, HISAT provides alignment sensitivity that very nearly matches the two-step HISATx2 algorithm, with a run time nearly as fast as the one-step HISAT method.
The hybrid approach is also effective in aligning reads spanning more than two exons, which are more likely to have small anchors. The alignment sensitivity for such reads increases from 53% using HISATx1 to 95% using HISAT (
