==== Front Bioinformatics Bioinformatics bioinformatics Bioinformatics 1367-4803 1367-4811 Oxford University Press 37387139 10.1093/bioinformatics/btad272 btad272 Genome Sequence Analysis AcademicSubjects/SCI01060 RawHash: enabling fast and accurate real-time analysis of raw nanopore signals for large genomes https://orcid.org/0000-0002-6548-7863 Firtina Can Department of Information Technology and Electrical Engineering, ETH Zurich, 8092 Zurich, Switzerland https://orcid.org/0000-0002-0833-0042 Mansouri Ghiasi Nika Department of Information Technology and Electrical Engineering, ETH Zurich, 8092 Zurich, Switzerland https://orcid.org/0000-0003-2581-8637 Lindegger Joel Department of Information Technology and Electrical Engineering, ETH Zurich, 8092 Zurich, Switzerland https://orcid.org/0000-0002-3502-7401 Singh Gagandeep Department of Information Technology and Electrical Engineering, ETH Zurich, 8092 Zurich, Switzerland https://orcid.org/0000-0003-4475-6945 Cavlak Meryem Banu Department of Information Technology and Electrical Engineering, ETH Zurich, 8092 Zurich, Switzerland https://orcid.org/0000-0002-7393-4504 Mao Haiyu Department of Information Technology and Electrical Engineering, ETH Zurich, 8092 Zurich, Switzerland https://orcid.org/0000-0002-0075-2312 Mutlu Onur Department of Information Technology and Electrical Engineering, ETH Zurich, 8092 Zurich, Switzerland Corresponding author. Department of Information Technology and Electrical Engineering, ETH Zurich, Gloriastrasse 35, 8092 Zurich, Switzerland. E-mail: firtinac@ethz.ch (C.F.), omutlu@ethz.ch (O.M.) 6 2023 30 6 2023 30 6 2023 39 Suppl 1 ISMB/ECCB 2023 Proceedings i297i307 © The Author(s) 2023. Published by Oxford University Press. 2023 https://creativecommons.org/licenses/by/4.0/ This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted reuse, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract Summary: Nanopore sequencers generate electrical raw signals in real-time while sequencing long genomic strands. These raw signals can be analyzed as they are generated, providing an opportunity for real-time genome analysis. An important feature of nanopore sequencing, Read Until, can eject strands from sequencers without fully sequencing them, which provides opportunities to computationally reduce the sequencing time and cost. However, existing works utilizing Read Until either (i) require powerful computational resources that may not be available for portable sequencers or (ii) lack scalability for large genomes, rendering them inaccurate or ineffective. We propose RawHash, the first mechanism that can accurately and efficiently perform real-time analysis of nanopore raw signals for large genomes using a hash-based similarity search. To enable this, RawHash ensures the signals corresponding to the same DNA content lead to the same hash value, regardless of the slight variations in these signals. RawHash achieves an accurate hash-based similarity search via an effective quantization of the raw signals such that signals corresponding to the same DNA content have the same quantized value and, subsequently, the same hash value. We evaluate RawHash on three applications: (i) read mapping, (ii) relative abundance estimation, and (iii) contamination analysis. Our evaluations show that RawHash is the only tool that can provide high accuracy and high throughput for analyzing large genomes in real-time. When compared to the state-of-the-art techniques, UNCALLED and Sigmap, RawHash provides (i) 25.8× and 3.4× better average throughput and (ii) significantly better accuracy for large genomes, respectively. Source code is available at https://github.com/CMU-SAFARI/RawHash. European Union’s Horizon 101047160 Swiss National Science Foundation 10.13039/501100001711 200021_213084 ==== Body pmc1 Introduction High-throughput sequencing (HTS) devices can generate a large amount of genomic data at a relatively low cost. HTS can be used to analyze a wide range of samples, from small amounts of DNA or RNA to entire genomes. Oxford Nanopore Technologies (ONT) is one of the most widely used HTS technologies that can sequence long genomic regions, called reads, with up to a few million bases. ONT devices use the nanopore sequencing technique, which involves passing a single DNA or RNA strand through a tiny pore, nanopore or channel, at an average speed of 450 bases per second (Kovaka et al. 2021) and measuring the electrical current as the strand passes through. Nanopore sequencing enables two key features. First, nanopores provide the electrical raw signals in real-time as the DNA strand passes through a nanopore. Second, nanopore sequencing provides a functionality, known as Read Until (Loose et al. 2016), that can partially sequence DNA strands without fully sequencing them. These two features of nanopores provide opportunities for (i) real-time genome analysis and (ii) significantly reducing sequencing time and cost. Real-time analysis of nanopore raw signals using Read Until can reduce the sequencing time and cost per read by terminating the sequencing of a read whenever sequencing the full read is not necessary. The freed-up nanopore can then be used to sequence a different read. A purely computational mechanism can send a signal to eject a read from a nanopore by reversing the voltage if the partial sequencing of a read meets certain conditions for particular genome analysis, such as (i) reaching a desired coverage for a species in a sample (Payne et al. 2021) or (ii) identifying that a read does not originate from a certain genome of interest (i.e. a target region; Kovaka et al. 2021; Zhang et al. 2021) and hence, does not need to be fully sequenced. By terminating the sequencing of reads that do not correspond to the target region, the sequencer can spend time and resources on higher coverage sequencing of the reads that correspond to the target. This process is referred to as nanopore adaptive sampling. By providing high coverage at target regions and avoiding unessential sequencing of reads outside those regions, this approach can improve the quality of sequencing and the downstream analysis utilizing the obtained data. To effectively utilize adaptive sampling in nanopore sequencing, it is crucial to have computational methods that can accurately analyze the raw output signals from nanopores in real-time. These methods must provide (i) low latency and (ii) throughput matching or exceeding that of the sequencer (Dunn et al. 2021; Kovaka et al. 2021; Zhang et al. 2021). Several works propose adaptive sampling methods for real-time analysis of raw nanopore signals (Edwards et al. 2019; Bao et al. 2021; Dunn et al. 2021; Kovaka et al. 2021; Payne et al. 2021; Zhang et al. 2021; Shih et al. 2022; Ulrich et al. 2022; Sadasivan et al. 2023; Senanayake et al. 2023). However, these works have three key limitations. First, most techniques mainly use powerful computational resources, such as GPUs (Bao et al. 2021; Payne et al. 2021), or specialized hardware (Dunn et al. 2021; Shih et al. 2022) due to the use of computationally intensive algorithms such as basecalling as we explain in detail in Supplementary Section S1. This can make real-time genome analysis challenging for portable and low-cost nanopore-based sequencers, such as the ONT Flongle or MinION, which are not typically equipped with such resources. Therefore these techniques introduce challenges for using them in resource-constrained environments. Second, the sheer size of genomic data at the scale of large genomes (e.g. human genome) makes it challenging to process the data in real-time. This is because such large genomes require efficient and accurate similarity identification across a large number of regions. This renders many current methods (Kovaka et al. 2021; Zhang et al. 2021) inaccurate or useless for large genomes as they cannot either provide accurate results or match the throughput of nanopores for these genomes. Third, machine learning models used in past works (Edwards et al. 2019; Payne et al. 2021; Bao et al. 2021; Ulrich et al. 2022; Senanayake et al. 2023) to analyze raw nanopore signals often require retraining or reconfiguring the model to improve accuracy for a certain experiment, which can be a barrier to flexibly and easily performing real-time analysis without retraining or reconfiguring these models. To our knowledge, there is no work that can efficiently and accurately perform real-time analysis of raw nanopore signals on a large scale (e.g. whole-genome analysis for human) without requiring powerful computational resources, which can easily and flexibly be applied to a wide range of applications that could benefit from real-time nanopore raw signal analysis. Our goal is to enable efficient and accurate real-time genome analysis for large genomes. To this end, we propose RawHash, the first mechanism that can efficiently and accurately perform real-time analysis of raw nanopore signals for large genomes in resource-contained environments. Unlike all the past works, RawHash is the only mechanism that can efficiently scale to large genomes and perform accurate real-time genomic analysis without requiring computationally intensive algorithms such as basecalling. Our key idea is to encode regions of the raw nanopore signal into hash values such that similar signal regions can efficiently be identified by matching their hash values, facilitating efficient similarity identification between signals. However, enabling accurate hashing-based similarity identification in the raw signal domain is challenging because raw signals corresponding to the same DNA content are unlikely to have exactly the same signal amplitudes. This is because the raw signals generated by nanopores can vary each time the same DNA fragment is sequenced due to several factors impacting nanopores during sequencing, such as variations in the properties of the nanopores or the conditions in which the sequencing is performed (David et al. 2017). Although the similarity identification of raw signals is possible via calculating the Euclidean distance between a sequence of signals in a multi-dimensional space (Zhang et al. 2021), such an approach can become impractical when dealing with larger sequences as the number of dimensions increases with the length of the sequences. This increase in dimensionality can lead to computational complexity and the curse of dimensionality, making it expensive and impractical. To address these challenges, RawHash provides three key mechanisms for efficient signal encoding and similarity identification. First, RawHash encodes signal values that have a wider range of values into a smaller set of values using a quantization technique, such that signal values within a certain range are assigned to the same encoded value. This helps to alleviate the probability of having varying signal values for the same DNA content and enables RawHash to directly match these values using a hashing technique. Second, RawHash concatenates the quantized values of multiple consecutive signals and generates a single hash value for them. The hashing mechanism enables RawHash to efficiently identify similar signal regions of these consecutive signal values by directly matching their corresponding hash values. Representing many consecutive signals with a single hash value increases the size of the regions examined during similarity identification without suffering from the curse of dimensionality. Using larger regions can substantially reduce the number of possible matching regions that need to be examined. RawHash is the first work that can accurately use hash values in the raw signal domain, which enables using efficient data structures commonly used in the sequence domain (e.g. hash tables in minimap2; Li 2018). Third, RawHash uses an existing algorithm, known as chaining (Li 2018), to find the colinear matches of hash values between signals to identify similar signal regions. These efficient and accurate mechanisms enable RawHash to perform real-time genome analysis for large genomes. While our proposed three key mechanisms have the potential to be used for various purposes in raw signal similarity identification, we design RawHash as a tool for mapping nanopore raw signals to their corresponding reference genomes in real-time. RawHash operates the mapping in two steps (i) indexing and (ii) mapping. First, in the indexing step, RawHash (i) converts the reference genome sequence into expected signal values by simulating the expected behavior of nanopores based on a previously known model, (ii) generates the hash values from these signals, and (iii) stores the hash values in a hash table for efficient matching. Second, in the mapping step, RawHash (i) generates the hash values from the raw signals in a streaming fashion, (ii) queries the hash table from the indexing step with these hash values to find the matching regions in the reference genome with the same hash value, and (iii performs chaining to find the similar region between the reference genome and the raw signal of a read. RawHash can utilize the unique functionalities of nanopore sequencing to reduce the sequencing time and cost in two ways. First, to avoid redundant sequencing and processing of each read, RawHash can use Read Until to eject a read before it is fully sequenced if RawHash identifies that the sequenced portion of the read can already be mapped to a reference genome. Second, to perform a cost- and time-efficient relative abundance estimation, RawHash can utilize Run Until to fully stop the entire sequencing of all subsequent reads after sequencing a certain amount of reads i.e. sufficient to make an accurate relative abundance estimation. We refer to such usage during abundance estimation as Sequence Until. Avoiding the redundant sequencing of further reads that are unlikely to substantially change the relative abundance estimation has the potential to significantly reduce the sequencing time and cost. To utilize Sequence Until, RawHash integrates a confidence calculation mechanism that evaluates the relative abundance estimations in real-time and fully stops the entire sequencing run if using more reads does not change its estimation. To stop the entire sequencing run for further reads, Run Until can be used to stop the entire sequencing run, which can enable the better utilization of nanopores. We find that Sequence Until can be applied to other mechanisms (e.g. UNCALLED) that can perform real-time relative abundance estimations. Prior work (Weilguny et al. 2023) proposes a technique to terminate the sequencing process when species in the sample reach a certain coverage depth. The key difference of Sequence Until is that it reduces the cost of sequencing for relative abundance estimation and is based on our adaptive, accurate, and low-cost confidence calculation during real-time abundance estimation. We evaluate RawHash on three important applications that can benefit from real-time genome analysis: (i) read mapping, (ii) relative abundance estimation, and (iii) contamination analysis. We compare RawHash with the state-of-the-art approaches, UNCALLED and Sigmap, which can be used with nanopore sequencers that may not be equipped with GPUs, such as the MinION devices. We evaluate RawHash, UNCALLED, and Sigmap in terms of their performance, accuracy, and their estimated benefits in reducing the sequencing time and cost. This article provides the following key contributions and major results: We propose RawHash, the first mechanism that can efficiently and accurately find the similarities between raw nanopore signals and a reference genome for large genomes without requiring powerful computational resources such as GPUs. We propose the first sampling mechanism that can stop the entire sequencing run for certain applications when an accurate decision can be made without sequencing the entire sample, which we call Sequence Until. We extensively evaluate RawHash by comparing it with state-of-the-art approaches, UNCALLED and Sigmap, on various datasets ranging from small genomes (i.e. genomes with up to 100 million bases) to large genomes (e.g. human genome). Our results show that RawHash provides (i) comparable accuracy to UNCALLED and Sigmap for small genomes and (ii) significantly better accuracy for large genomes than UNCALLED and Sigmap. We show that Sigmap cannot perform real-time genome analysis for large genomes as it cannot match the throughput of nanopores. We provide the open source implementation of RawHash and the complete set of scripts to reproduce the results shown in this paper at https://github.com/CMU-SAFARI/RawHash. 2 Methods We propose RawHash, a mechanism that can efficiently and accurately identify similarities between raw nanopore signals of a read and a large reference genome in real-time (i.e. while the read is sequenced). The raw nanopore signal of each read is a series of electrical current measurements as a strand of DNA passes through a nanopore. The reference genome is a set of strings over the alphabet A, C, G, T. RawHash provides the mechanisms for generating hash values from both a raw nanopore signal and a reference genome such that similar regions between the two can be efficiently and accurately found by matching their hash values. 2.1 Overview Figure 1 shows the overview of how RawHash identifies similarities between raw nanopore signals of a read and a reference genome in four steps. First, RawHash pre-processes both (i) the raw nanopore signal and (ii) the reference genome into values that are comparable to each other. For raw signals, RawHash segments the raw signal into non-overlapping regions such that each region is expected to contain a certain amount of signal values that are generated from reading a fixed number k of DNA bases. Each such region is called an event (David et al. 2017). Each event is usually represented with a value derived from the signal values in the segment. For the reference genome, RawHash translates each substring of length k (called a k-mer) into their expected event values based on the nanopore model. Figure 1. Overview of RawHash. The event values from the reference genome are not directly comparable to the event values from raw nanopore signals due to variability in the current measurements in nanopores generating slightly different event values for the same k-mer (David et al. 2017). To generate the same values from slightly different events that may contain the same k-mer information, the second step of RawHash quantizes the event values from a larger set of values into a smaller set. The quantization technique ensures that the event values within a certain range are likely to be assigned to the same quantized value such that the effect of signal variation is alleviated, i.e. the same k-mer is likely assigned the same quantized value. Due to the nature of nanopores, each event usually represents a very small k-mer of length around k = 6 bases, depending on the nanopore model (Zhang et al. 2021). Such a short k-mer is likely to exist in a large number of locations in the reference genome, making it challenging to efficiently identify the correct one. To make the events more unique (i.e. such that they exist only in a small number of locations in the reference genome), the third step of RawHash combines multiple consecutive quantized events into a single hash value. These hash values can then be used to efficiently identify similar regions between raw signals and the reference genome by matching the hash values generated from their events using efficient data structures such as hash tables. Fourth, to map a raw nanopore signal of a read to a reference genome, RawHash uses a chaining algorithm (Li 2018; Zhang et al. 2021) that find colinear matching hash values generated from regions that are close to each other both in the reference genome and the raw nanopore signal. 2.2 Event generation Our goal is to translate a reference genome sequence and a raw nanopore signal into comparable values. To this end, RawHash converts (i) each k-mer of the reference genome and (ii) each segmented region of the raw signal into its corresponding event. Sequence-to-event conversion: To convert a reference genome sequence into a form that can be compared with raw nanopore signals, RawHash converts the reference genome sequence into event values in three steps, as shown in Fig. 2. Figure 2. Converting sequences to event values based on the k-mer model of a nanopore. First, RawHash extracts all k-mers from the reference genome sequence, where k depends on the nanopore. The k-mer model of a nanopore includes the information about the expected k-mer length of an event and the expected average event value for each k-mer based on certain variables affecting the signal outcome of the nanopore’s current measurements. For many nanopore models, ONT provides the k-mer model including recent R10 and R10.4. These models can also be generated by users (Simpson et al. 2017). Second, RawHash queries the k-mer model for each k-mer of the reference genome to convert k-mers into their expected event values. Although the k-mer model of a nanopore provides an extensive set of information for each possible k-mer, RawHash uses only the mean values of events that provide an average value for the signals in the same event since these mean values provide a sufficient level of meaningful information for comparison with the raw nanopore signals. Third, RawHash normalizes the event values from the same reference genome sequence (e.g. entire chromosome sequence or a contig) by calculating the standard scores (i.e. z-scores) of these events. RawHash uses these normalized values as event values since the same normalization step is taken for raw signals to avoid certain variables that may affect the range of raw signal amplitudes during sequencing (Kovaka et al. 2021; Zhang et al. 2021). Signal-to-event conversion: Our goal is to accurately convert the series of raw nanopore signals into a set of values where each value corresponds to certain DNA sequences of fixed length k, k-mers, and consecutive values differ by one base. To achieve this, RawHash converts the raw signals into their corresponding values in three steps, as shown in Fig. 3. First, to accurately identify the distinct regions in the raw signal that correspond to a certain k-mer from DNA, RawHash performs a segmentation step as described in a basecalling tool, Scrappie, and used by earlier works UNCALLED and Sigmap. The segmentation step aims to eliminate the factors that affect the speed of the DNA molecules passing through a nanopore, as the speed affects the number of signal measurements taken for a certain amount of bases in DNA. To perform the segmentation step, RawHash identifies the boundaries in the signal where the signal value changes significantly compared to the certain amount of previously measured signal values, which indicates a base change in the nanopore. Such boundaries are computed using a statistical test, known as Welch’s t-test (Ruxton 2006), over a rolling window of consecutive signals. RawHash performs this t-test for multiple windows of different lengths to avoid the variables that cause a change in the number of current measurements due to the varying speed of DNA through a nanopore, known as skip and stay errors (David et al. 2017). Signals that fall within the same segment (i.e. between the same measured boundaries) are usually called events since each event contains the signals from a reading of a fixed amount of DNA bases, k-mers. Figure 3. Detecting events from raw signals. Second, since the number of signals that each event includes is not constant across different events due to the stay and skip errors, RawHash generates a single value for each event to quickly avoid these potential errors and other factors that cause variations from reading the same amount of DNA bases. To this end, RawHash measures the mean value of the signals that fall within the same segment and uses this mean value for an event. Third, since the amplitudes of the signal measurements may significantly vary when reading k-mers at different times, RawHash normalizes the mean event values using the event values generated from the nanopore within the same certain time interval in a streaming fashion. Although this time interval parameter can be modified in our tool, the default configuration of RawHash processes the events of signals generated by the nanopore within one second. For normalization, RawHash uses the same z-score calculation that it uses for normalizing the event values generated from reference sequences as described earlier. RawHash uses these normalized values as event values when comparing with the event values from reference sequences. 2.3 Quantization of events Our goal is to avoid the effects of generating different event values when reading the same k-mer content from nanopores so that we can identify k-mer matches by directly matching events. Although the segmentation and normalization steps explained in Section 2.2 can avoid the potential sequencing errors, such as stay and skip errors and significant changes in the current readings at different times, these approaches still do not guarantee to generate exactly the same event values when reading the same k-mer content. This is because slight changes in the normalized event values may occur when reading the same DNA content due to the high sensitivity and stochasticity of nanopores (David et al. 2017). Thus, it is challenging to generate the same event value for the same k-mer content after the segmentation and normalization steps. Since these event values generated from reading the same k-mer content are expected to be close to each other (Zhang et al. 2021), we propose a quantization mechanism that encodes event values so that events with close mean values can have the same quantized value in two steps as shown in Fig. 4. Figure 4. Quantization of two event values. First, to increase the probability of assigning the same value for similar event values, RawHash trims the least significant fractional part of mean values by using only the most significant Q bits of these mean event values from their binary format, which we represent as E[1, Q] for simplicity where E is the event value and E[1, Q] gives the most significant Q bits of E. We assume that the mean event values are represented by the standard single-precision floating-point format with the sign, exponent, and fraction bits. This enables RawHash to reduce the wide range of floating-point numbers into a smaller range without significantly losing from the accuracy such that event values closer to each other can be represented by the same value in the smaller range of values. We can perform this trimming technique without significant sensitivity loss because we observe that these normalized event values mostly use at most six digits from the fractional part of their values, leaving a large number of fractional bits useless. Second, to avoid using redundant bits that may carry little or no information in the most significant Q bits of an event value, RawHash prunes p bits after the most significant two bits of E[1, Q] such that 2+p