Within less than four decades, the nanopore sequencing technology accelerated from an implausible idea scribbled on a notebook page to one of the decisive contributors to the complete sequence of the human genome. Its rapid evolution, particularly in recent years, is driven not only by its inherent innovation of the nanopores but also by synergistic advancements in complementary fields, such as GPU acceleration and deep neural networks, as well as cross-disciplinary influences from domains like speech recognition. However, during this rapid advancement, certain methods within nanopore sequencing remain relatively unexplored. This oversight has the potential to create bottlenecks in the technology's further development.

In this thesis work, we delve into these uncharted areas, seeking to fill critical gaps and branch the technology into new frontiers. Our objective is to unleash its potential, enabling further breakthroughs in genomic research and beyond.

Through our research, we have developed two novel algorithms and two innovative models tailored to address these under-explored aspects of nanopore sequencing. The two algorithms, the GMBS and the LFBS, both belonging to the MBS group, offer innovative solutions to the challenging decoding problems inherent in HHMMs. They are two distinct variations tailored to different scenarios. While the GMBS is specifically suited for decoding lengthy sequences, such as those encountered in long-read basecalling, the LFBS is optimized for parallel programming and excels in processing short-length sequences. 

The two innovative models developed in this research, each leveraging variations of HHMMs and employing an end-to-end approach, exhibit distinguished structures. The first model, a hybrid of EDHMM and DNN, showcases the effectiveness of integrating both knowledge-driven and data-driven techniques. In contrast, the second model, a custom-designed Helicase HMM, draws inspiration from pioneering studies on motor proteins found in sequencing devices. With its elaborate hierarchical state architecture boasting over five million emission states, this model offers a comprehensive feature space comparable to its predecessor. 

Inom mindre än fyra decennier har nanopore-sekvenseringsteknologin accelererat från en otrolig idé som skissades i en antckningsbok till en avgörande teknologi som bidragit till den kompletta sekvensensieringen av det mänskliga genomet. Denna snabba utveckling, särskilt under de senaste åren, drivs inte bara av innovation kring nanoporer utan också av synergistiska framsteg inom kompletterande områden, såsom GPU-acceleration och djupa neurala nätverk, samt tvärvetenskapligt inflytande från domäner som taligenkänning. Under denna snabba utveckling har do vissa metoder inom nanopore sekvensering förblivit relativt outforskade. Detta förbiseende riskerar att skapa flaskhalsar i teknologins vidareutveckling.

I denna avhandling utforskar vi dessa outforskade områden, i syfte att fylla kritiska luckor och utveckla tekniken mot nya fronter. Vårt mål är att frigöra dess fulla potential och möjliggöra ytterligare genombrott inom genomisk forskning och därutöver.

Som del av vår forskning har vi utvecklat två nya algoritmer och två innovativa modeller anpassade för att adressera dessa underutredda aspekter av nanopore sekvensering. De två algoritmerna, GMBS och LFBS, som är instanser av det mer generella ramverket av MBS-algorithmer (\emph{eng.} marginalised beam search), erbjuder innovativa lösningar på de utmanande avkodningsproblemen som är inneboende i HHMM:er. De är två distinkta variationer anpassade för olika scenarier. Medan GMBS är speciellt lämpad för avkodning av långa sekvenser, såsom de som stöts på vid läsning av långa sekvenser, är LFBS optimerad för parallell programmering och utmärker sig i bearbetning av korta sekvenser.

De två innovativa modellerna som utvecklats i denna forskning, vilka båda utnyttjar variationer av HHMM:er och använder en ``end-to-end''-ansats, uppvisar distinkta strukturer. Den första modellen, en hybrid av EDHMM och DNN, visar effektiviteten av att integrera både kunskapsdrivna och datadrivna tekniker. I kontrast till detta, drar den andra modellen, en anpassad Helicase HMM, inspiration från pionjärstudier om motorproteiner som finns i sekvenseringsenheter. Med sin detaljerade hierarkiska tillståndsarkitektur med över fem miljoner emissivtillstånd, erbjuder denna modell en omfattande egenskapsrymd jämfört med sina föregångare.

Inferring a state sequence from a sequence of measurements is a fundamental problem in bioinformatics and natural language processing. The Viterbi and the Beam Search (BS) algorithms are popular inference methods, but they have limitations when applied to Hierarchical Hidden Markov Models (HHMMs), when the primary interest lies in the outer state sequence. The Viterbi algorithm can not infer outer states without inner states, while the BS algorithm requires marginalization over prohibitively large state spaces. We propose two new algorithms to overcome these limitations: the greedy marginalized BS algorithm and the local focus BS algorithm. We show that they approximate the most likely outer state sequence with higher performance than the Viterbi algorithm, and we evaluate the performance of these algorithms on an explicit duration HMM with simulated and real nanopore base calling data.

Hidden Markov models (HMMs) are frequently used in areas such as speech recognition and bioinformatics. However, implementing HMM algorithms correctly and efficiently is time-consuming and error-prone. Specifically, using model-specific knowledge to improve performance, such as sparsity in the transition probability matrix, ties the implementation to a particular model, making it harder to modify. Previous work has introduced high-level frameworks for defining HMMs, thus lifting the burden of efficiently implementing HMM algorithms from the user. However, existing tools are ill-suited for sparse HMMs with many states. This paper introduces Trellis, a domain-specific language for succinctly defining sparse HMMs that use GPU acceleration to achieve high performance. We show that Trellis outperforms previous work and is on par with a hand-written CUDA kernel implementation for a particular sparse HMM.

BackgroundBasecalling long DNA sequences is a crucial step in nanopore-based DNA sequencing protocols. In recent years, the CTC-RNN model has become the leading basecalling model, supplanting preceding hidden Markov models (HMMs) that relied on pre-segmenting ion current measurements. However, the CTC-RNN model operates independently of prior biological and physical insights.ResultsWe present a novel basecaller named Lokatt: explicit duration Markov model and residual-LSTM network. It leverages an explicit duration HMM (EDHMM) designed to model the nanopore sequencing processes. Trained on a newly generated library with methylation-free Ecoli samples and MinION R9.4.1 chemistry, the Lokatt basecaller achieves basecalling performances with a median single read identity score of 0.930, a genome coverage ratio of 99.750%, on par with existing state-of-the-art structure when trained on the same datasets.ConclusionOur research underlines the potential of incorporating prior knowledge into the basecalling processes, particularly through integrating HMMs and recurrent neural networks. The Lokatt basecaller showcases the efficacy of a hybrid approach, emphasizing its capacity to achieve high-quality basecalling performance while accommodating the nuances of nanopore sequencing. These outcomes pave the way for advanced basecalling methodologies, with potential implications for enhancing the accuracy and efficiency of nanopore-based DNA sequencing protocols.