量子计算在基因组组装中的应用

创作时间:

作者:

@小白创作中心

量子计算在基因组组装中的应用

引用

来源

https://www.bilibili.com/opus/989162961485430791

基因组组装是生物信息学中的一个核心问题，它涉及到如何将从生物体中获取的大量短DNA序列片段（reads）重新拼接成完整的基因组序列。随着测序技术的快速发展，如何高效地处理这些海量数据成为了一个亟待解决的问题。近年来，量子计算作为一种新兴的计算模式，为基因组组装问题提供了一种新的解决方案。本文将介绍基因组组装的基本概念、常见算法，以及量子计算在这一领域的应用前景。

基因组组装的基本概念

基因组组装（Genome assembly）是使用测序方法将待测物种的基因组生成序列片段（即read），然后根据reads之间的重叠区域对片段进行拼接。首先，这些片段被拼接成较长的连续序列（contig），然后将contigs拼接成更长的允许包含空白序列（gap）的scaffolds。通过消除scaffolds的错误和gaps，我们可以将这些scaffolds定位到染色体上，从而得到高质量的全基因组序列。这个过程对于研究物种的基因组结构、功能基因挖掘、调控代谢网络构建以及物种进化分析等方面具有重要意义。

随着测序技术的进步和测序成本的降低，我们能够在短时间内获得大量的测序数据，然而基因组组装是一个复杂的过程，尤其是面临动植物等复杂且规模巨大的基因组的组装需要耗费大量的计算资源，因此，如何高效的分析和处理这些数据成为目前基因组学和生物信息学最亟待解决的问题。

图1 DNA 测序流程图(引用自：Next-Generation Sequencing (NGS)- Definition, Types)

基因组组装常见算法

基因组组装算法涉及多种方法，分为有参考基因组的组装和无参考的从头组装（de novo assembly），其中从头组装最常见的两个策略是基于德布鲁因图（De Bruijn graph）和Overlap-Layout-Consensus（OLC）的组装算法。

德布鲁因图（De Bruijn graph）

德布鲁因图是一种有向图，由节点和边构成。其要求是相邻两个节点的元素错开一个碱基。通过将测序得到的reads以k-mer方式排列，德布鲁因图可以帮助我们拼接成更长的Contig。例如，如果几条reads之间有overlap，那么就容易拼接成一个比较长的Contig。实际情况会更复杂，但我们通常保留主干路径，由主干路径组装成Contig1。

Overlap-Layout-Consensus（OLC）

OLC方法首先构建重叠图，然后将重叠图收束成Contig，最后选择每个Contig中最有可能的核苷酸序列。重叠图表示对于一些序列，前后有若干个碱基是一样的。多个reads片段可以构成重叠图。寻找最短的Contig序列，使得所有的reads都是该序列的子集，通常采用贪心算法实现。

图2 OLC (左)和 DBG 算法示意图（右）(引用自：https://qinqianshan.com/bioinformatics/bin/olc-dbg/)

应用量子计算解决基因组组装问题

高质量的基因组装需要较高深度的测序才能满足要求，对于完整的人类基因组组装，通常建议的覆盖度在30x以上。以三代测序（如PacBio和Oxford Nanopore等）用于人类基因组组装为例，通常每个read可以达到几千到几万个碱基，覆盖30x的情况下，可能需要的reads数量在几百万到几千万不等。如此庞大的reads组装在计算重叠图(overlap graph)时通常面临巨大的计算复杂度和算力需求，因此经典计算通常引入重叠过滤、动态规划等方法来降低计算复杂度，如果组装高质量的基因组则需要耗费大量时间，这里我们引入量子算法来加速这一过程。

OLC算法中最关键的一步是通过构建重叠图来确定不同reads间的位置关系，这一步可以转换成组合优化问题的旅行商问题(Traveling Salesman Problem，TSP)。其中不同reads表示不同的城市结点，reads间的重叠长度作为结点间的权重，目标是将所有的reads按照它们之间的重叠长度进行排序，并尝试将它们组装成一个总体重叠长度最长的序列。

量子计算与经典方法得效果对比

我们比较了在不同问题规模下(reads数分别为7、8、9、10)CIM真机和传统求解器Simulated Annealing、Tabu Search的求解时间。对比发现，在同等规模问题上，CIM真机的求解时间要远少于Simulated Annealing、Tabu Search (左图)。同时，随着问题规模增大，CIM 真机求解时间相较于Simulated Annealing、Tabu Search更加稳定(右)。

图4 不同问题规模下(reads数分别为7、8、9、10)“天工量子大脑”CIM真机和传统求解器Simulated Annealing、Tabu Search的求解时间对比