博士论文 | ETH Zurich 2024 | 通过新算法与技术实现快速、准确、高效的实时基因组分析 264页

高通量测序（HTS）技术的出现彻底改变了基因组分析，使得大规模基因组的快速且经济高效的测序成为可能。尽管取得了这些进展，基因组数据的复杂性和数据量的不断增加仍然带来了与准确性、可扩展性和计算效率相关的重大挑战。这些挑战主要源于测序数据中各种形式的不必要和未处理的变异，统称为噪声。解决这些挑战需要深入理解基因组数据中不同类型的噪声，并开发技术以减轻噪声对基因组分析的影响。

在本论文中，我们旨在理解影响基因组分析流程的噪声类型，并通过开发新的计算技术来容忍或减少噪声，从而实现对不同类型测序数据（例如纳米孔测序的原始电信号）更快、更准确和可扩展的分析。

首先，我们介绍了BLEND，一种噪声容忍的哈希机制，能够通过单次哈希值查找快速识别完全匹配和高度相似但存在任意差异的序列。其次，为了实现可扩展且准确的噪声原始纳米孔信号分析，我们提出了RawHash，这是一种新颖的机制，通过提出首个基于哈希的原始纳米孔信号相似性搜索技术，有效减少原始纳米孔信号中的噪声，并实现准确的实时分析。第三，我们通过RawHash2扩展了RawHash的功能，这一改进机制：1）更好地理解原始纳米孔信号中的噪声以更有效地减少噪声；2）提高映射决策的鲁棒性。第四，我们通过引入Rawsamble探索了原始纳米孔信号分析的更广泛影响和新应用。Rawsamble是首个使用基于哈希搜索的原始信号全对全重叠机制，能够直接从原始信号构建从头组装，而无需进行碱基识别，这为原始纳米孔信号分析开辟了新的方向和应用。

本论文全面理解了不同类型基因组数据中的噪声如何影响基因组分析流程，并提供了减轻噪声影响的新颖解决方案。我们的研究结果表明，通过使用新的计算技术有效容忍和减少噪声，我们可以：1）显著提高基因组分析的性能、准确性和可扩展性；2）通过实现新的应用和方向扩展原始信号分析的范围。我们希望并相信，本论文中提出的方法和见解将有助于发明和开发更强大、更高效、功能更全面的基因组分析工具，特别是在原始信号分析领域。

论文题目：Enabling Fast, Accurate, and Efficient Real-Time Genome Analysis via New Algorithms and Techniques

作者：Can Firtina

类型：2024年博士论文

学校：ETH Zurich（瑞士苏黎世联邦理工学院）

下载链接：

链接: https://pan.baidu.com/s/1wVi5V7VQXb45Dadp572lNw?pwd=n1qi

硕博论文汇总：

链接: https://pan.baidu.com/s/1Gv3R58pgUfHPu4PYFhCSJw?pwd=svp5

基因组分析在个性化医疗 [2–22]、基因组编辑 [23–50]、进化生物学 [51–65]、癌症研究 [66–112]、产前和新生儿筛查 [113–137]、疫情追踪 [138–157]、微生物组研究 [158–182]、农业 [183–195] 和法医学 [196–214] 等各个领域发挥着至关重要的作用。高通量测序 (HTS) 技术的出现，例如边合成边测序 (SBS) [215–223]、单分子实时 (SMRT) [224] 和纳米孔测序 [225–247]，彻底改变了基因组分析，与桑格测序 [249] 相比，它能够以相对较低的成本生成大量基因组数据，从而实现更快、更具成本效益的基因组测序 [248]。然而，由于多种原因，基因组数据分析具有挑战性：1）HTS 技术只能对相对较短的基因组片段（称为读段）进行测序，而这些片段在相应基因组中的位置未知 [250–254]；2）这些读段可能包含测序错误 [248, 252, 255–257]，导致与原始序列不同；3）由于物种内和物种间个体之间的差异，测序的基因组可能（通常不会）与参考数据库中记录的基因组（称为参考基因组）不完全匹配 [255,258]。尽管自 20 世纪 80 年代以来，计算工具取得了显着改进 [258]，以克服这些挑战，但基因组数据的快速增长 [259] 导致基因组分析流程中的计算开销越来越大，对高效、准确和及时的基因组分析提出了巨大挑战 [260–262]。

图 1.1 显示了基因组分析流程的多个关键步骤，每个步骤都会影响基因组分析的准确性、速度和能耗。

基因组分析流程中的关键步骤。

首先，使用 HTS 技术对生物分子（例如 DNA 分子 [263]）进行测序，以生成原始测序数据（例如，在纳米孔测序中测量的原始电信号）1。在 HTS 技术中，纳米孔测序独特地允许基于实时数据分析提前终止测序（无论是单个读取还是整个运行），从而显着减少基因组分析时间和成本。这种能力被称为自适应采样 [264]。这种分析需要快速，理想情况下，应在测序仪生成原始信号数据后立即进行。在测序过程中以与测序仪的数据生成速度（即吞吐量）匹配或超过其计算速度分析原始纳米孔信号被称为实时分析，对于自适应采样等应用至关重要。实时分析主要用于 1) 通过将测序与分析重叠来减少基因组分析延迟，这对于需要快速分析的紧急情况（例如新生儿筛查 [137]）尤其有用，以及 2) 通过减少不必要的测序来减少测序时间和成本 [265]。然而，实时分析带来了独特的挑战，特别是在满足纳米孔测序所要求的严格吞吐量和延迟要求方面。分析速度必须与数据生成保持同步以避免瓶颈，这通常很难实现，因为数据量巨大并且需要在测序过程中进行实时决策 [266]。第 2.1 节提供了有关测序技术的详细背景。

其次，原始测序数据通常通过碱基调用 2a 转换为核苷酸字符或碱基序列（例如 DNA 中的 A、C、G 和 T）。碱基调用工具 [267–288] 主要依赖于计算密集型方法，这些方法处理大量嘈杂且容易出错的原始数据，以准确推断实际的核苷酸序列 [261, 287, 289]。或者 2b，可以直接分析原始测序数据而无需碱基调用 [138, 264–266, 290–302]。虽然直接分析原始数据可以避免碱基调用的计算开销，但由于噪声增加，它带来了挑战，需要专门的技术来准确去噪。这些去噪技术通常包括时间序列分析 [286, 291, 303] 和量化 [265, 266, 299]。

第三，读取映射 3 旨在查找基因组序列对之间的相似性和差异（例如，一个或多个物种的测序查询读取和目标参考基因组之间的相似性和差异）。为了便于实际的相似性识别，读取映射包括几个步骤。这些步骤包括构建（即索引 3.1 ）和使用（即播种 3.2 ）数据库 [2, 265, 266, 292,299, 304–411]，通过利用各种草图（即采样）[306,310, 333, 360, 412–432] 和散列 [304, 307–309, 315, 334, 358, 414, 416, 424, 433–459] 方法进行有效的相似性搜索。读取映射中的过滤 [357, 460–468] 和共线链接（即稀疏动态规划）[306, 469–482] 步骤 3.3 旨在通过快速识别查询和目标序列之间高度不同或相似的区域来减少读取映射中接下来计算成本高昂的步骤的工作量。比对 [483–501] 步骤 3.4 识别查询和目标序列之间的确切差异和相似性，由于基因组序列的规模很大，因此总体上需要相当大的处理能力和内存 [258, 502, 503]。第 2.2 节提供了读取映射中关键步骤的详细背景。

第四，读取映射步骤中生成的输出可用于基因组分析的后续步骤（即下游分析 4 ），例如从头基因组组装（即从头构建基因组）[250、251、305、504–532]、变异调用（即与参考基因组相比识别个体基因组中的遗传变异）[533–570]和宏基因组学（即识别和分析环境中存在的生物）[571–591]。下游分析通常需要额外的计算密集型步骤[261]，包括集合交集[592]、图形处理[305,593]和深度神经网络（DNN）的使用[540]。这些额外的步骤进一步增加了基因组分析流程的总体计算开销和能耗[261]。第 2.3 节提供了读取映射后下游基因组分析流程中关键步骤的详细背景。

许多算法、软件和硬件技术旨在解决基因组分析流程中的计算挑战。这些工作通过以下方式提高了计算工具的性能和准确性：1）降低总体计算和空间复杂度 [266,483,485, 535,540]，2）消除无用的工作 [266,267,275,275,299,306,357,460–468,593]，3）优化数据结构和内存访问模式 [324, 594–598]，4）利用多核、众核和 SIMD 架构中的并行性和分布式计算 [300,301,334,462,484,594, 596,599,599–648,648–660]，5）为基因组分析的许多步骤设计专用的硬件加速器[138,195,262,267–284,297,300–302,461,463，467,484,490,593,594,596,598–779]。我们在第 2.4 节和第 3 节中详细描述了这些方法。

测序数据生成的主要步骤。

纳米孔测序仪的结构及其测序步骤。

处理原始测序数据的主要步骤。

原始信号分析的主要步骤。

纳米孔测序实时分析的两个主要优点。

读取映射的主要步骤。

索引（左侧）和种子（右侧）的步骤，使用哈希值在目标序列和查询序列之间找到匹配的序列段。

一种采样（即草图）机制，称为最小化草图。

间隔播种技术。预定义的固定模式应用于所有三个输入序列。屏蔽字符以红色 X 突出显示。前两个输入序列生成相同的输出哈希值，因为它们彼此不同的字符被屏蔽，从而生成相同的间隔种子和这些种子的相同对应哈希值。

使用 SimHash 技术为项目向量生成哈希值。示例输入是一个句子（即向量），其中这些单词（即项目）的哈希值（以二进制形式显示）用于生成整个句子的哈希值。

在目标序列和查询序列之间链接锚点（种子匹配）。链接方法计算一对锚点之间的距离，以确定它们是否应包含在同一个链中。

动态规划 (DP) 矩阵用于识别编辑操作：匹配、替换、插入和删除。每个单元格的值都是根据相邻单元格的值计算的，如箭头所示。最佳对齐路径以深蓝色突出显示，而浅蓝色单元格表示在链接步骤中识别的两个后续锚点。最佳对齐的相应编辑操作显示在 DP 矩阵的右侧。

具有三个不同输入序列的频闪器技术的简单示例。所选 k-mer 之间的序列被忽略，以容忍插入和删除。前两个输入序列在生成频闪器种子后，会生成与输出相同的哈希值，即使这些输入序列并不完全匹配。

用 BLEND 替换种子技术中的哈希函数。

BLEND 概述。1 BLEND 使用 BLEND-I 或 BLEND-S 将序列转换为其项目向量。2 BLEND 使用其项目向量和 SimHash 技术生成输入序列的哈希值。3 BLEND 使用哈希表查找模糊种子匹配，只需查找 BLEND 生成的哈希值即可。

BLEND-I 概述。BLEND-I 使用输入序列所有重叠 k-mer 的哈希值作为向量项。

BLEND-S 概述。BLEND-S 仅使用由频闪序列播种机制选择的 k-mer 的哈希值。

SimHash 技术中用于计算给定项向量的哈希值的步骤概述。向量项是以二进制形式表示的哈希值。二进制到向量编码将这些向量项转换为其对应的位向量表示。Sum 执行向量加法并将结果存储在单独的向量中，我们将其称为计数器向量。解码根据计数器向量中的值生成向量的哈希值。BLEND 使用 SIMD 操作执行这三个步骤，如 SIMD 所示。我们用红色突出显示了 0 位在 SimHash 技术中的转换和传播方式。