国际期刊收录！华大与量旋科技联合开发长短读长混合组装量子算法，助力量子计算应用研究

近日，深圳华大生命科学研究院联合量旋科技，共同开发了基于长短读长混合从头组装的量子算法，基于量子计算实现了带有重复序列和测序错误的从头组装。相关研究成果于4月23日在国际期刊《PRX Life》上发表。

《PRX》（Physical Review X）是由美国物理学会出版的一份同行评议的开放获取科学杂志，涵盖了纯物理学、应用物理学和跨学科物理学的所有分支，被誉为物理学者的“梦之期刊”之一。《PRX Life》 建立在《PRX》的标准之上，旨在发表物理学与生物学交叉领域最重要的研究成果，同时吸引更广泛的定量生命科学领域的科学家参与，注重卓越和持久的影响力。

在这篇研究成果中，研究团队创新性地开发了一种可以在量子计算机上完成含有测序错误和重复序列的基因组从头组装任务的量子算法。整个工作大致可以分为三个部分：

一、基因组组装问题转为QUBO问题

根据二代测序技术得到的数据构造德布鲁因（de Bruijn）图，并引入三代测序技术得到的数据来确定重复基因片段的位置，构造目标函数。最后根据从头组装算法需要满足组装路径是连续的单路径作为约束条件，并结合目标函数构造无约束的损失函数。

二、使用分布式VQE算法进行求解

基于传统VQE算法，使用分布式计算的方式，将大的QUBO问题分成多个小的QUBO问题，并生成多个比特数较少的参数化量子态，构成传统VQE算法中的量子态，最后将多个小的QUBO问题和多个比特数较少参数化量子态进行期望值测量，优化迭代，最终估算得QUBO问题的解，即测序片段的正确组装顺序。

三、根据问题设计问题启发式参数化量子线路

根据QUBO问题中变量的取值情况以及约束条件，设计问题启发式参数化量子线路，以实现生成的参数化量子态仅包含问题的可行解，减少搜索空间，提高算法性能。

图1. 基于分布式VQE算法的基因组组装流程示意图

该研究创新性地在量子计算机上解决了带有重复序列和测序错误的基因从头组装问题。同时，通过使用分治策略和设计量子线路，实现了量子资源的节约和性能的提升，为探索量子计算在生命科学领域的实际应用做出了努力。

 

基因序列重构难题显著

长短读长混合测序，助力高质量组装

人们通过现有的测序技术，只能得到各种长度的DNA片段的序列信息。将这些较短的序列信息汇总还原成完整的基因片段的过程，称为基因组装。基因组装，特别是没有参考版的从头组装，本身就是一个非常复杂的问题。

在实际应用中，重复序列和测序错误等问题的存在更是使问题难度上升一个等级。这就好比把几副拼图拆散了混到一起后重新复原，其中一些图片可以拼在多个不同的位置，但是只有一个位置是正确的，还有一些图片的形状不对，无法拼到它正确的位置上。

为了解决实际组装中存在重复序列和测序错误问题，研究者引入了短读长和长读长的混合测序数据。这是因为短读长测序的精度非常高，且成本低廉，但难以跨越重复区域，而长读长测序能很好跨越重复区域，但是错误率高且成本很高。同时利用两种数据，可以在较低的成本下利用二者的优势，实现高质量的组装。

图2. 展示了带有重复序列和测序错误的短读长和长读长数据进行编码后放到量子计算机上计算得到表示正确解的量子态并最终解码得到正确的组装序列。

 

3倍效率提升！

创新量子线路为基因组组装提速

量子计算基于量子叠加和量子纠缠原理，具有强大的并行处理能力，可以有效地解决二代测序需要大量计算资源的问题。但是由于量子硬件的限制，当前量子计算还处于有“有噪声的中等规模量子”时代（Noisy Intermediate-Scale Quantum，NISQ）。在NISQ时代，如何利用有限的量子资源探索具体的实际应用是一个非常重要的研究课题。

研究团队基于VQE算法（被视为在NISQ时代最有希望实现的量子算法之一），采用了一种称为“分而治之”的策略，设计了分布式VQE算法。通过这种方式，研究人员能够在仅使用10个量子比特的情况下，完成原本需要多达140个量子比特才能解决的任务，显著减少了所需的量子比特数量。当前，基于分布式VQE算法的基因组组装方法已经在模拟器中完成了多个小规模的基因组组装任务，展现出良好的可扩展性。

此外，研究人员针对基因组装问题的特点，特别设计了一种问题启发式参数化量子线路，以提高算法的性能。在基因组装任务中，我们需要将测序得到的片段按照正确的顺序拼接起来。由于量子比特能够表示的解的数量远远超过了问题可能的解的总数，这导致了搜索空间的冗余，从而降低了寻找正确解的效率。

为了解决这个问题，研究人员设计出一种专门的量子线路，成功地减少了需要搜索的解空间（如图2所示）。与通用的硬件高效量子线路相比，这种定制的量子线路能够实现约3倍的收敛速度提升，从而更高效地找到正确的基因组装顺序。

（a）

（b）

图3.基因组组装问题的参数化量子线路示意图

 

量子算法正逐步转化为现实力量

推动生命科学等更多领域发展

该研究让我们看到了量子计算在处理复杂生物信息学等生命科学问题上的巨大潜力，特别是在基因组学和生物信息学领域。

Pistoia Alliance、QED-C 和 QuPharm 联合进行的一次调查显示：82%的生命科学公司认为量子计算将在未来10年内对行业产生积极影响。量子计算正逐步转化为推动该领域快速发展的现实力量，通过开发出新的算法和策略，解决传统计算机难以解决的复杂问题，为人类健康事业带来更加光明的前景。

以新药研发为例。由于药物研发的风险巨大，不仅周期漫长，而且成本高昂。一款创新药平均需要投入20亿美元和10年时间才能进入市场，但是其成功率令人担忧，临床研究的成功率不足10%。然而，借助量子计算技术，企业可以通过精确地模拟量子力学来更准确地模拟生化反应过程。如此一来，企业可以在更短的时间内找到更高效的药物分子，这将大大加速药物发现和新药开发进程。

实际上，目前量子算法不仅在生命科学已有应用，同样也能解决物流领域的供应链问题等等。以分布式VQE算法为例，这是一种可以在NISQ时代专门求解大规模QUBO问题的经典-混合量子算法。未来，分布式VQE算法可以应用于更多的领域，如金融领域中用于投资组合优化、期权定价等问题，帮助金融机构提高服务质量、降低风险；在能源领域，用于电力系统的优化、设备调度和可再生能源的集成，从而提高能源效率，减少碳排放。

通过跨学科合作，不同领域的专家共同探索量子计算在各自领域的应用潜力，开发出更加高效、实用的算法和解决方案，这也将为人类社会带来更加深远的影响和变革。

该研究由深圳华大生命科学研究院主导，联合深圳量旋科技有限公司、武汉华大生命科学研究院共同合作完成。方旌锴、林跃锋和黄俊翰为该论文的共同第一作者；黎宇翔、项金根和徐讯为论文的共同通讯作者。研究已通过伦理审查，严格遵循相应法规和伦理准则。