动力系统视野下的马尔科夫链 ：一个量化进化的案例
【新智元导读】计算机领域里的理论“动力系统“和“马尔科夫链” 可用于搭建分析生物进化的模型，进而量化地理解进化，这对理解诸多经济、政治和文化现象有着显著的意义。
原文标题：Markov Chains Through the Lens of Dynamical Systems: The Case of Evolution
来自：http://www.offconvex.org/
本文中我们将以一种高级的方式介绍进化以及我们怎样使用动力系统和马尔科夫链等数学工具来为进化建模。这样，关于进化的问题就可以转化为关于动力系统和马尔科夫链的问题——这些问题有的很容易回答，另外一些则指向了现有算法和优化技术中的缺口。特别是，我们将展示一种能表达病毒进化的设定，并提出了这样一个问题：进化可以以多快的速度发生？这个问题将指向计算机科学的一些有价值的问题。
从达尔文和华莱士的先驱性工作开始，在过去两百年间，我们对于进化以及进化如何在四十亿年间塑造了多样而复杂的生命等问题的理解已经取得了巨大的科学和数学进展。不过，进化理论不是一个简明的理论，那些想要寻求数学清晰性的人会在进化理论中遇到模糊。我们将介绍进化的基本结构，关注一种曾用来为病毒进化建模的具体设定，并提出一些关于这类进化的效率的问题。
进化概说
抽象地看，我们可以把进化看作一种机制（或元算法），它以一个（有繁殖能力的）种群为输入，以种群的下一代为输出。在任何时间，种群都由不同类型的个体构成，而这一切都发生在一个资源有限的环境之中。哪些个体将被选择为下一代中的成员，而哪些将被淘汰，这都取决于个体所属的类型在环境中的适应度。繁殖过程可以是无性的——例如简单的克隆，也可以是有性的——这时就需要两个（或更多）个体联合起来产生后代。此外，在繁殖过程中也会发生从一个类型转变为另一个类型的突变（mutation）。每个繁殖、选择或突变的步骤都既可能是决定论性的，也可能是随机性的。这样，进化便是一个以种群为输入的决定论性或随机性函数。
种群的大小、类型的数量、每种类型在环境中的适应度、突变的概率和起始状态都是进化模型中的参数。通常，人们会确定这些参数，然后研究种群会如何随时间而演化——种群是否会达到一个极限状态或稳态；如果达到了这样的状态的话，这种极限状态将如何与这些参数一起变化；能以多快的速度达到这种极限状态。
毕竟，如果进化缺乏效率的概念，它将是一个不完整的理论。
对这个问题的一个重要但有所不同的视角来自 LeslieValiant 的研究，该研究关注用计算学习理论来量化地理解进化。最后，你现在或许已经猜到，在这种一般性层面上，进化包含了一些先验的与生物学无关的过程。实际上，在 Nowak 的著作中，进化模型被用来理解许多社会、经济和文化现象。
无限种群 = 动力系统 有限种群 = 马尔科夫链
给定一个（可以包含随机步骤的）进化模型，最初为了理解它，我们通常会假设这个种群的数量无限，而所有的步骤实际上都是决定论性的。我们很快将看到这方面的例子。这使得种群中的每个类型部分的进化都可以被建模为一个从（用Δm 表示的）概率单纯形到其自身的决定论动力系统，此处m 是类型的数量。不过，真实的种群是有限的，并常常产生诸如随机遗传漂变之类的实质性随机变化。为了理解作为种群规模的函数的种群极限行为，我们既不能假设种群是无限的，也不能忽视进化步骤中的随机性。因此，为了研究有限种群，我们就需要诉诸马尔科夫链。更具体地，我们下面将描述一个无性种群的易错演化的决定论和随机论模型。
决定论性无限种群模型
考虑一个无限种群，这个种群中的每个个体都属于 m 个类型之一。每个具有类型 i 的个体的适应度都由正整数 a[i] 来表示，而我们使用一个 m*m 的对角矩阵A 来记录这些适应度，在矩阵中每个 (i,i) 位置上的值为 a[i]。繁殖过程是易错的（error-prone），而易错性由另一个 m*m 的概率矩阵 Q 来记录，矩阵Q 中每个 （i,j）位置上都记录了 j 类型在繁殖过程中突变为i 类型的概率。在繁殖阶段，现有种群中的每个类型 i 都会产生自身的 a[i] 个复制品。在繁殖过程中可能会发生突变，所以在我们的决定论性模型中，我们假设在 i 类型的所有个体中会有比例为Q[i,j] 的个体转化为 j 类型。由于经过繁殖总的概率质量可能会超过1，在选择阶段我们会对概率质量进行归一化，以确保它仍具有单位值。
因此，一个类型的适应度会影响它在所选种群中的表现。在数学方面，我们可以用向量 x(t)∈Δm来记录每个类型在进化的 t 步骤中所占的比例。这样，向量 x(t) 的演化就由动力系统 x(t+1)=QAx(t)/∥QAx(t)∥1 来制约。（这也是我们在上一篇文章中所讨论的动力系统之一。）因此，进化过程的最终结果并不是一个单一类型，而是一个类型间的恒定分布。我们看到，当 QA > 0 时，这个动力系统收敛于唯一的固定点，即 QA 的最大右特征值。因此，无论进化从何处开始，这个动力系统都会收敛到这个固定点。在生物学方面，可以发现相应的特征值是种群的平均适应度，这实际上也是那个被最大化了的量。
进化能有多快呢？简单的线性代数告诉我们，这一过程的收敛速度取决于 QA 的次高特征值与最高特征值之间的比值。最后，我们注意到与有性生殖种群相对应的动力系统也不难描述，有人已从优化角度研究过它。
随机有限种群模型
现在考虑上面描述的进化动态过程的一个随机、有限种群版本。在这里，仍假定种群是无性的，但它现在具有固定有限的规模 N。在归一化之后，种群的构成仍然由时间 t 时的点 X(t)∈Δm 来记录。当参数由无限种群设定下的矩阵Q 和 A 来描述的时候，如何从这个模型中产生出 X(t+1) 呢？在繁殖阶段，我们先把每个类型 i 的个体替换为 a[i] 个 i 类型的个体。这样这个中间过程种群中的 i 类型个体的总数便是 a[i]*N*Xi(t)。在突变阶段，中间过程种群中的每个个体都独立地、按照矩阵Q 而随机地突变。最终，在选择阶段，通过从中间过程种群中选取 N 个个体，种群又回到规模数量 N。
所有这些步骤都描绘在图2 中。请注意随机性意味着，即便我们以相同方式启动系统，链条的不同运作过程也会产生出非常不同的结果。向量 X(t+1) 是所产生的种群的归一化后的频率向量。上面描述的马尔科夫链的状态空间的大小为(N+m−1，m−1)。当 QA>0 时，这个马尔科夫链是遍历性的，并因此具有唯一的稳态。不过，与决定论性的情形不同，这个稳态并不容易得到先验的计算。除了那些最平凡的情形之外，它不具有闭式表达式。那么我们如何计算它呢？
混合时间
（当 m 比 N 小时）状态数量大致随 N^m 而增长。即使在 m =40，种群规模为10,000 的情况下，状态数量也将超过 2^300，这比这个宇宙中的源自数量还多。因此，我们最多能指望用一个算法来获取接近稳态的状态。事实上，由于马尔科夫链中的每个步骤都可以有效执行，进化已经为我们提供了一个算法。不过，进化的效率则依赖进化用来达到接近稳态的时间——即进化的混合时间。不过，总的来说，除非提供一个对混合时间的（经过证明的）界限，我们没有别的办法来表明马尔科夫链已接近其稳态。在计算机科学中，对马尔科夫链的混合时间的界限的证明是一个重要领域，该领域也和统计学、统计物理学和机器学习等学科相联接。不过，在进化中，混合时间的重要性不只是从稳态的取样中计算统计量，它还能告诉我们多快能达到一个稳态。我们很快就能从该模型在病毒进化中的应用中看到混合时间的生物学重要性。
病毒进化与药物设计：混合时间的重要性
上面描述的马尔科夫链最近在对无性繁殖的 RNA 病毒种群的建模中找到了用处。（诸如 HIV-1 等的）模型显示出强烈的随机行为，而这能够指导药物和疫苗的设计策略。
引文：例如，一个 HIV-1 感染者的 HIV-1 有效种群规模约为10^3 - 10^6，因规模太小而无法使用无限种群模型。
让我们看看这是怎么一回事。RNA 病毒由于其原始复制机制而经常在繁殖期间经历突变。突变会引入基因变异，这样种群在任何时间都由不同的类型构成——有些类型（在捕获宿主细胞方面）十分有效，而有些则不那么有效。需要注意的典型情形是，当有效类型的数量只占 m 中较小的比例的时候。为了简化，让我们假定我们处于这样的设定中：在繁殖过程中每个类型都以概率τ突变为另一种类型，而以概率 1−τ*(m−1) 保持自身不变。因此，当τ从 0 增长到 1/m 时，直观上病毒种群的构成也会从聚集于那些有效类型改为均匀分布于所有类型。当种群在稳态中的大部分概率质量都聚集于那些有效类型时，种群作为整体是有效的，而如果不聚集于那些有效类型的话，我们就可以宣布这个种群的死亡。
Eigen 在一个先驱性工作中观察到，实际上存在着一个被称为错误阈限的关键突变率，超出这个突变率后就会出现相变——也就是说，病毒种群会突然从高度有效转变为死亡。
（对这个观察的证明见此链接。）而这暗示了一种抗病毒的策略：驱动它们的突变速率超过其错误阈限！有趣的是，人体已经通过生产能增进病毒突变率的抗体而使用了这一策略。在人工方法方面，也可以通过利巴韦林等致突变药物来实现这一效果。这时关键是要在很高的精度上了解错误阈限：对人体使用过量的致突变药物可能会产生不可欲的副作用，从而导致癌症等并发症；而当突变率低于阈限时增加突变率则会提高病毒的适应度，让它更有效地适应环境，从而使它更具破坏性。对错误阈限的机选要求对稳态的知识，并因此需要知道混合时间的界限。此外，当为一种致突变药物的效果建模时，模型的收敛速度也会决定最短需要多长的疗程。
而如果病毒种群在受感染患者的整个一生中都未达到稳态，那么这种方法恐怕就没什么用了。
总结
我们希望通过这个例子，我们能让你相信，效率是进化的一个重要方面。特别是在我们所展示的这些设定中，对进化马尔科夫链的混合时间的知识是个关键问题。尽管这很重要，然而我们仍然缺乏所有参数的混合时间的严格界限，即便是在本文所考虑的这些最简单的进化模型中。先前的工作要么忽略了突变，要么假定模型是中性的（也就说是，假定所有类型具有相同的适应度），要么转而去关注扩散限制，而扩散限制要求突变和选择压都比较弱。这些界限只在进化的某些特殊情况中起作用，而我们想知道那些对所有参数都有效的混合时间界限。在一系列研究中，我们表明，只要种群足够大，广泛种类的进化马尔科夫链（包括本文中描述的那些）都可以在所有参数设定下快速混合！此外，对这些问题的分析已引向了新的技术，这些技术可以分析马尔科夫链和随机过程的混合时间，而这些技术的重要性已超出了进化论。我们将在下一篇文章中解释这些技术，并在更一般的意义上从效率的角度继续讨论进化。