A Block Decomposed QUBO Workflow for Chromosome-Y Phylogeny Reconstruction

每一个生命体都携带在 DNA 中书写的历史，这是一份关于种群如何在数千年中移动、混合与分离的分子记录。对于科学家而言，重建这段历史就像是在尝试拼凑一个巨大的、破碎的拼图，其中拼图碎片是遗传变异，而完整的图像则是物种的家族树。追踪人类祖先最可靠的方法之一是观察 Y 染色体，这是一种几乎以不变的形式从父亲传给儿子的微小 DNA 片段。由于它不会与来自母亲的 DNA 混合，Y 染色体充当了一条清晰、 unbroken 的后代谱系，使研究人员能够绘制出人类家族树的深层分支。然而，随着遗传数据量的增长，寻找正确树结构的任务变得异常困难。即使是将适量的人群排列成家族树，其可能的组合方式也极其庞大，以至于超过了标准计算机逐一检查所有可能性的能力。这种组合爆炸迫使科学家依赖于“启发式算法”（heuristics），即通过快速猜测最佳答案，但并不保证该答案一定是真实的。

位于撒丁岛 CRS4 的一个研究小组开发了一种新的计算工作流来解决这一问题，该方法结合了两种不同的策略：将一个巨大的问题分解为更小、更易处理的部分，并使用一种专门的量子启发式算法来解决这些部分。他们的工作专注于人类 Y 染色体数据，特别是观察被称为单核苷酸多态性（SNPs）的遗传密码中的单字母变化。研究人员从包含遗传信息的数据集中开始，从中剔除了 72 个缺乏必要遗传变异的无信息样本，最终留下 78 个男性群体进行分析。随后，他们利用这种新方法重建了进化树。他们并没有试图一次性解决整棵树（这对于现有技术来说过于复杂），而是将任务分成了两个主要决策：首先，确定哪些人群应该在树上聚类在一起；其次，确定树的最顶端——即“根”——应该放置在何处，以展示时间的流向。

为了做出这些决策，研究人员将生物学问题转化为一种被称为“二次无约束二值优化问题”的数学格式。通俗地说，这是一种将寻找最佳树的过程转化为在一片复杂的丘陵与山谷景观中寻找最低点游戏的方法，而最低点代表着最可能的家族历史。挑战在于，这个景观过于宏大，无法一次性探索完毕。团队的解决方案是使用一种称为 ADMM 分解的技术，该技术将巨大的景观划分为相互重叠的较小区域。每个区域被独立求解，然后将结果缝合在一起，形成一个一致的整体。这使得系统能够处理单个计算机原本无法处理的规模问题。

在求解这些较小部分时，团队采用了名为“数字化反绝热量子优化”（digitized counter-diabatic quantum optimization）的方法。这种方法利用量子力学的原理来极快地找到景观中的最低点。与其他需要缓慢迭代试错过程的量子方法不同，这种技术通过一次直接的路径计算即可得出解。研究人员在模拟量子处理器行为的无噪声计算机模拟上测试了他们的工作流。他们发现，该方法成功重建了 78 个群体的家族树。生成的树将“根”置于非洲谱系深处，这一发现与已建立的人类起源科学认知相符。此外，虽然他们新方法识别出的每一个分组都与一种标准的、被广泛接受的建树技术——“邻接法”（Neighbor-Joining）一致，但新方法仅恢复了邻接法参考树中所发现分组量的 40%，这表明虽然该方法具有精确性，但它识别的总簇群数量比标准方法要少。

这项研究表明，这种结合了“拆分大型问题”与“高效量子风格求解器”的混合方法是群体基因组学领域一条可行的发展路径。它提供了一种超越传统启发式算法“猜想”的方法，同时又不需要目前全规模量子计算机所需的庞大且易出错的硬件。通过证明他们可以在模拟量子设备上解决这些困难的树重建问题，研究人员表明这项技术已准备好在未来应用于更大规模的数据集。他们的工作提供了一个清晰、循序渐进的流程，将原始遗传数据转化为一棵带有根部和注释的家族树，并完整包含了定义每个分支的具体遗传标记。这一成就表明，该领域正朝着一个能够以更高精度、更少依赖近似法来绘制人类进化史全貌的未来迈进。