Title: Enabling Fast, Accurate, and Efficient Real-Time Genome Analysis via New Algorithms and Techniques Show Chinese title

Title: 通过新算法和技术实现快速、准确且高效的实时基因组分析

Abstract: The advent of high-throughput sequencing technologies has revolutionized genome analysis by enabling the rapid and cost-effective sequencing of large genomes. Despite these advancements, the increasing complexity and volume of genomic data present significant challenges related to accuracy, scalability, and computational efficiency. These challenges are mainly due to various forms of unwanted and unhandled variations in sequencing data, collectively referred to as noise. In this dissertation, we address these challenges by providing a deep understanding of different types of noise in genomic data and developing techniques to mitigate the impact of noise on genome analysis. First, we introduce BLEND, a noise-tolerant hashing mechanism that quickly identifies both exactly matching and highly similar sequences with arbitrary differences using a single lookup of their hash values. Second, to enable scalable and accurate analysis of noisy raw nanopore signals, we propose RawHash, a novel mechanism that effectively reduces noise in raw nanopore signals and enables accurate, real-time analysis by proposing the first hash-based similarity search technique for raw nanopore signals. Third, we extend the capabilities of RawHash with RawHash2, an improved mechanism that 1) provides a better understanding of noise in raw nanopore signals to reduce it more effectively and 2) improves the robustness of mapping decisions. Fourth, we explore the broader implications and new applications of raw nanopore signal analysis by introducing Rawsamble, the first mechanism for all-vs-all overlapping of raw signals using hash-based search. Rawsamble enables the construction of de novo assemblies directly from raw signals without basecalling, which opens up new directions and uses for raw nanopore signal analysis. Show Chinese abstract

Abstract: 高通量测序技术的出现通过实现大型基因组的快速和低成本测序，彻底改变了基因组分析。 尽管有这些进展，基因组数据的复杂性和数量不断增加，带来了与准确性、可扩展性和计算效率相关的重大挑战。 这些挑战主要是由于测序数据中各种形式的不需要且未处理的变异，统称为噪声。 在本论文中，我们通过深入理解基因组数据中不同类型的噪声，并开发减轻噪声对基因组分析影响的技术来解决这些挑战。 首先，我们介绍了BLEND，这是一种具有噪声容忍度的哈希机制，能够通过一次哈希值查找快速识别完全匹配和高度相似但存在任意差异的序列。 其次，为了实现对嘈杂原始纳米孔信号的可扩展和准确分析，我们提出了RawHash，一种新颖的机制，通过提出第一个基于哈希的原始纳米孔信号相似性搜索技术，有效减少原始纳米孔信号中的噪声并实现准确的实时分析。 第三，我们通过RawHash2扩展了RawHash的功能，这是一种改进的机制，1）提供对原始纳米孔信号中噪声更好的理解以更有效地减少噪声，2）提高映射决策的鲁棒性。 第四，我们通过引入Rawsamble，首次提出了一种基于哈希搜索的所有对所有原始信号重叠机制，探索了原始纳米孔信号分析的更广泛影响和新应用。 Rawsamble使可以直接从原始信号构建从头组装，而无需进行碱基呼叫，这为原始纳米孔信号分析开辟了新的方向和用途。