结构化共祖模型下的成对共祖时间:计算概述
《Theoretical Population Biology》:Pairwise coalescence times under the structured coalescent: A computational overview
【字体:
大
中
小
】
时间:2026年10月23日
来源:Theoretical Population Biology 1.4
编辑推荐:
摘要
两两合并时间在群体遗传理论和推断中具有根本重要性。然而,在结构化合并模型下计算期望及相关量仍然具有挑战性。这里,我们分析了两种常用的近似策略——时间分解法和谱系独立性假设——并刻画了它们潜在的理论假设和计算性质。我们还总结了近期将该问题与广义 Lyapunov 方程联系
摘要
两两合并时间在群体遗传理论和推断中具有根本重要性。然而,在结构化合并模型下计算期望及相关量仍然具有挑战性。这里,我们分析了两种常用的近似策略——时间分解法和谱系独立性假设——并刻画了它们潜在的理论假设和计算性质。我们还总结了近期将该问题与广义 Lyapunov 方程联系起来的算法进展。这些方法实现了降低复杂度的精确计算,我们进一步将其扩展到更一般的模型设置。最后,我们讨论了迭代求解器在加速推断中的潜在作用。综上所述,这些见解阐明了计算格局,并为结构化群体中更灵活和准确的推断奠定了基础。
引言
在合并理论中,两两合并时间——即谱系对追溯至最近共同祖先的时间——构成了一类基本随机变量。两两合并时间的分布及其期望等功能量起着关键的中介作用:一方面,它们反映了群体结构和人口史的关键方面;另一方面,它们支撑着许多常用的群体遗传摘要。这一核心作用使得两两合并时间在从群体遗传数据中进行人口推断方面尤为宝贵。
当群体在空间上被细分且群体间发生迁移时,结构化合并模型(Notohara, 1990, Takahata, 1991)提供了一个广泛使用的理论框架来模拟它们的基因谱系历史。它被表述为有限谱系集配置上的连续时间马尔可夫过程,其中个体谱系根据指定的迁移率沿着时间倒序穿过离散的群体集,并在占据同一群体时以规定速率合并。在此过程中,两两合并时间由两条谱系的起始位置表征,因此自然携带了空间结构和迁移动态的信息。这为通过两两合并时间与不同群体遗传摘要之间的关系,从遗传数据中推断反向迁移率和合并率提供了基础。
人们已努力使用基于突变和重组的两类摘要进行此类推断。在低突变率极限下,两两合并时间的期望唯一决定了 FST(Slatkin, 1991)以及更广义的谱系单倍型协方差结构(McVean, 2009)。这些关系构成了 EEMS(Petkova et al., 2016)和 FEEMS(Marcus et al., 2021)的基础,后者从等位基因频率数据中估计迁移率的空间变化。
在重组背景下,长共享合并片段(LPSC 片段,或同源区段)的长度分布受两两合并时间随机控制(Palamara et al., 2012, Carmi et al., 2013)。这种关系是 MAPS(Al-Asadi et al., 2019)的基础,该方法利用片段共享模式检测细尺度空间结构。
尽管两两合并时间在空间遗传推断中应用广泛,但在结构化合并模型下计算其分布及相关功能量仍然是一个主要挑战。在一般情况下,这通常需要求解一种特殊类型的广义 Lyapunov 方程,正如本文所示。对于具有 d 个群体的系统,使用暴力求解法求解此类方程涉及将方程矢量化为大小为 O(d2) 的线性方程组,导致计算复杂度为 O(d?)。
由于这种令人望而却步的计算成本,EEMS、FEEMS 和 MAPS 等方法依赖于强烈的简化假设来降低复杂度。具体来说,EEMS 和 FEEMS 采用了“阻力隔离”框架(McRae, 2006),通过两阶段分解来接近预期的两两合并时间:(1) 两条谱系首次占据同一群体的预期时间,和 (2) 共定位后的预期合并时间(Slatkin, 1991)。当迁移是顶点传递(各向同性)且合并率均匀时,第一项严格等于单谱系迁移链预期通勤时间的四分之一(Matsen and Wakeley, 2006, Lundgren and Ralph, 2019)。通过可逆随机游走与电气网络之间的经典对应关系(Nash-Williams, 1959),通勤时间等价于有效电阻,后者可以高效计算(Babi? et al., 2002, Bapat, 2004)。由于有效电阻可以针对任何对称(或更广义地,可逆)迁移设置进行计算,EEMS 和 FEEMS 将此基于电阻的公式扩展到一般对称迁移作为一种启发式近似。
然而,在非各向同性设置下,这种启发式近似的理论性质和误差边界在很大程度上仍未得到刻画。此外,在自然群体中,由于环境、行为或历史因素,基因流经常是非对称和不可逆的——在这种场景下,基于电阻的框架即使作为启发式也严格失效,因为非可逆链无法定义有效电阻。在此类设置中坚持使用基于电阻的推断可能会引入巨大的系统误差并扭曲推断的人口历史(Lundgren and Ralph, 2019)。
MAPS 处于略不同的位置;虽然出于实际便利通常假设对称迁移,但其潜在框架在结构上对这一要求的依赖程度低于基于电阻的方法。从这个意义上说,它站在更灵活的理论基础上。然而,这种灵活性是通过在计算合并时间密度时假设两条谱系独立演化而获得的。在 3.2 节中,我们将看到这种近似产生的概率密度函数是不可归一化的,导致积分发散和数值不稳定。尽管 MAPS 中基于重组的推断提供了一种针对这些效应的隐式正则化形式,但在将此策略扩展到更一般的人口推断时仍需谨慎。
鉴于这些理论和数值挑战,必须超越这些近似,转向求解潜在广义 Lyapunov 方程的精确且计算高效的框架。最近,Shen 和 Novembre (2025) 通过引入一种算法解决了这一差距,该算法精确求解控制预期两两合并时间的矩阵方程,时间复杂度改进为 O(d?)。通过绕过基于电阻方法的限制性对称要求和独立性假设的非归一化问题,这一算法进展使得推断细尺度非对称基因流成为可能。基于这一精确框架,Shen 和 Novembre (2025) 开发了 FRAME(细分辨率非对称迁移估计),这是一种专门设计用于处理大规模基因组数据集中非对称迁移复杂性的方法。
受此进展启发,本文重新审视了结构化合并模型下两两合并时间相关的更广泛计算挑战。我们表明,许多功能量——不仅是期望——的计算从根本上与求解一类广义 Lyapunov 方程联系在一起。为了应对这些挑战,我们首先分析了 EEMS、FEEMS 和 MAPS 采用的特定计算策略,刻画了它们所依赖的假设及其计算性质。然后,我们总结了 FRAME 中介绍的精确算法框架,并展示了其向更广泛的功能量和模型配置的扩展。最后,我们讨论了使用迭代方法近似求解广义 Lyapunov 方程的诱人可能性,提供了进一步扩展这些方法以适应日益复杂的人口模型的视角。
章节摘要
结构化合并模型下的两两合并时间
假设我们有两条谱系,其中每条谱系在 d 个群体间向后迁移,直到它们彼此合并。设 mij 为谱系从群体 i 迁移到群体 j 的瞬时迁移率,设 γi 为两条谱系位于群体 i 时的合并率。迁移率汇总在 L 和 γ 中,其中 L=∑i≠1m1i?m12…?m1d?m21∑i≠2m2i…?m2d??…??md1?md2…∑i≠dmdi 是对应加权有向图的拉普拉斯矩阵,且 γ=(γ1,γ2,…,γd) 是...向量
近似策略
为降低计算复杂度,以前的工作(Petkova et al., 2016, Marcus et al., 2021, Al-Asadi et al., 2019)采用了各种近似策略。在本节中,我们分析这些方法背后的关键假设及相关计算性质。
精确计算方法
最近,Shen 和 Novembre (2025) 采用了一种新算法,以 O(d?) 的时间复杂度求解广义 Lyapunov 方程,并开发了一种从基因组数据推断非对称基因流的新方法。这里我们展示该算法并将其扩展到非奇异情况。
讨论
这项工作提供了结构化合并模型下两两合并时间的计算概述,重点关注其数学形式、计算挑战以及使其在群体遗传推断中可用的策略。通过将合并时间矩及相关量的计算框定为广义 Lyapunov 方程,我们统一了现有工作的几个分支,并澄清了常见近似中固有的权衡。
我们重新审视
致谢
我们感谢 John Novembre 在修改手稿方面的反馈和帮助。我们也感谢 Vivaswat Shastry 和 Sherif Negm 的建设性讨论。本研究得到了 NIH NIGMS 资助 R35-GM149521 的支持,该资助授予 John Novembre。
Hao Shen
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号