一个CM通信gydF4y2Ba

评论文章gydF4y2Ba

性别作为一种算法:计算视角下的进化理论gydF4y2Ba

作者:Adi Livnat, Christos PapadimitriougydF4y2Ba
ACM通信，2016年11月，第59卷第11期，84-93页gydF4y2Ba
10.1145 / 2934662gydF4y2Ba
评论(3)gydF4y2Ba

看看你的周围，你会被进化的成果所震惊。诺贝尔奖得主雅克·莫诺德认为，关于进化论的一个奇怪的现象是，所有受过教育的人都认为他们对进化论相当了解，然而很少有人(如果有的话)真正了解。理解进化论是必要的:“生物学中没有任何东西是有意义的，除非在进化论的光下，”著名的20gydF4y2Ba^thgydF4y2Ba世纪生物学家狄奥多西·多布赞斯基进化论比黑洞和其他科学之谜更接近我们的家——它感觉就像你的家族史。gydF4y2Ba

回到顶部gydF4y2Ba

关键的见解gydF4y2Ba

与大多数科学领域相比，进化论有一个尖锐的开端:查尔斯·达尔文的著作的出版gydF4y2Ba物种起源gydF4y2Ba在1859年。gydF4y2Ba^8gydF4y2Ba当然，事情没有那么简单:在19的前半部分gydF4y2Ba^thgydF4y2Ba几个科学家相信我们周围生命的多样性一定是进化的结果(参见查尔斯·巴贝奇的侧栏和附图)。达尔文的巨大贡献体现在三方面:他认定自然选择是进化的引擎;他提出了共同血统假说，指出不同的物种来自共同的祖先，并进一步暗示所有的生命都来自共同的起源;以及他的理论所拥有的无与伦比的论证力量。当然gydF4y2Ba原点gydF4y2Ba达尔文对遗传学一无所知，也不知道性别在进化中的作用，这是他的几个重要空白。例如，关于性的最终原因，他写道，“整个主题仍然隐藏在黑暗中。”gydF4y2Ba

数学很早就为这一理论提供了依据。孟德尔通过观察表现出不同特征的兄弟豌豆植株的比例和建立模型的数学模式，发现了遗传学。当他的定律在40年后被重新发现时，它们离散的性质被误解为与达尔文对特征的连续感知相冲突。一场深刻的科学危机肆虐了20年，最终在数学的帮助下得到了解决:离散等位基因(参见术语表)可以通过累积贡献产生连续的表型性状。在20世纪20年代和接下来的20年里，R.A.费雪、J.B.S.霍尔丹和S.赖特开发了数学方程，用来预测一个种群的遗传组成如何在几代人之间发生变化。人口遗传学的数学理论在侧栏“达尔文和孟德尔的和解方程”中有简要介绍。这是所谓的“现代进化综合”的关键gydF4y2Ba^thgydF4y2Ba因为它提出了一种统一达尔文主义和孟德尔主义的方法。gydF4y2Ba

---

性不仅本质上是普遍的，而且似乎是生活的中心舞台，是各种各样行为和结构的基础。gydF4y2Ba

---

在此后的近一个世纪里，进化论研究蓬勃发展成为一门成熟、全面、享有盛誉的科学学科，而在过去的二十年里，它被大量的分子数据所淹没，这是一个巨大的科学金矿，为进化论的信条提供信息，并常常挑战它。然而，尽管现代进化生物学取得了卓越的成就，仍有几个重要的问题超出了我们目前的理解:gydF4y2Ba

• 性在进化中扮演什么角色?gydF4y2Ba重组繁殖在生命中几乎无处不在(甚至细菌交换遗传物质)，而专性无性繁殖物种似乎是罕见的进化死胡同。然而，专家们对性何以如此有利还没有达成一致意见。gydF4y2Ba
• 进化优化到底是什么?gydF4y2Ba随着计算机科学家编码的所有进化启发的优化启发式(我们将在下文中讨论)，这个问题在过去几十年里也被生物学家们深思熟虑。gydF4y2Ba
• 变异的悖论。gydF4y2Ba由于选择，人类和许多其他物种的遗传变异比理论预测的要高得多;假设变异是中性的也有它的问题。gydF4y2Ba
• 突变是完全随机的吗?gydF4y2Ba我们知道它们在基因组中远不是均匀分布的，但它们会是复杂遗传机制的结果吗?gydF4y2Ba

正如我们在本文中所述，计算机科学家和生物学家最近的联合研究，将计算的思想和概念引入生物学，在这些问题上取得了相当出乎意料的进展。在线附录中的其他背景和文献可在ACM数字图书馆(gydF4y2Badl.acm.orggydF4y2Ba)在“资料来源”下。gydF4y2Ba

回到顶部gydF4y2Ba

进化与计算机科学gydF4y2Ba

在过去的70年里，计算机科学家，从冯·诺伊曼开始，gydF4y2Ba^37gydF4y2Ba都被进化论所启发和吸引。在20世纪50年代，从事优化工作的计算机科学家开发出了局部搜索启发式:从一个随机解开始，重复以下步骤:如果这个解的“突变”比当前解更好，就改为该解，直到发现局部最优解。所谓“突变”(更常见的是使用“邻居”一词)，我们指的是在非常少量的特征上不同于当前的解决方案;例如，在旅行推销员问题中，一个突变可以改变旅行的两个或三个边缘，形成一个新的旅行。这个过程从随机开始重复多次，这个策略可以被看作是维持种群的顺序方式(参见Papadimitriou和Steiglitz)gydF4y2Ba^32gydF4y2Ba一项关于20世纪80年代的调查)。gydF4y2Ba

这个局部搜索的基本思想在20世纪80年代被一个热力学隐喻强化了，gydF4y2Ba^20.gydF4y2Ba帮助算法逃避局部最优和障碍:gydF4y2Ba模拟退火gydF4y2Ba这种局部搜索的变体被称为“局部搜索”，它甚至允许采用一种不利的突变，尽管其概率会随着不利和时间的推移而降低。另一种变体叫做gydF4y2Ba与赢家同行gydF4y2Ba^1gydF4y2Ba更接近进化，因为它保持了一个解决方案的种群，将停留在局部最优的个体传送到更有希望的点。请注意，所有这些启发式都是受到无性进化的启发(解决方案之间不会发生重组);这种类型的启发式已经在许多实践领域中得到了成功的应用，并且有几个实践中非常重要的难题，例如图划分，在这方面这种启发式可以与最著名的启发式相竞争。gydF4y2Ba

在20世纪70年代，约翰·霍兰德(John Holland)提出了另一类启发式算法，称为遗传算法:gydF4y2Ba^14gydF4y2Ba解决方案的种群通过突变进化gydF4y2Ba而且gydF4y2Ba重组。重组在优化问题上应用起来要困难得多，因为它预先假定了一个遗传密码，将问题的特征映射到可重组的基因上(要了解困难，可以想想旅行推销员问题:旅行团可以突变，但它们不能重组)。群体中每个个体解决方案的进化适应度(即它将拥有的孩子数量)与潜在问题中被最大化的数量成正比。在许多代之后，人口中可能会包含一些优秀的解决方案。霍兰德的想法立即引起了人们的注意，并吸引了大批追随者，到目前为止，关于这一主题已有大量的参考书目(参见米切尔的著作)gydF4y2Ba^28gydF4y2Ba和戈德堡gydF4y2Ba^12gydF4y2Ba)．条款gydF4y2Ba进化算法gydF4y2Ba而且gydF4y2Ba进化计算gydF4y2Ba通常被用作“遗传算法”的大致同义词，但它们通常描述更一般的概念，例如非常有趣的算法工作，也被归类为人工生命的研究，其目的不是为实际优化问题找到好的解决方案，而是通过揭露硅的新奇、复杂的进化现象来理解自然界的进化，参见Jong。gydF4y2Ba^16gydF4y2Ba

回到遗传算法，文献中已经报道了一些解决实际优化问题的成功案例，但普遍的印象似乎是，遗传算法在实践中远不如局部搜索和模拟退火成功。如果这是真的，那就相当了不起了——一个巨大的科学奥秘，因为在自然界中，完全相反的情况发生了:重组是成功的和普遍存在的，而专门的无性繁殖是极其罕见和挣扎的。gydF4y2Ba

作者们从2006年开始合作对进化进行计算理解，正是为了调查这个谜团，我们在本文中叙述了我们的发现。就在同一年，莱斯利·Valiant第一次写了他的进化理论，这是另一次试图用计算术语理解进化的尝试。gydF4y2Ba^36gydF4y2BaValiant把进化看作是一个理想适应度函数的近似值，它是在多项式多个世代中由多项式大的基因型种群所形成的gydF4y2Ba^35gydF4y2Ba通过突变学习。值得注意的是，在他的理论中没有重组(性)，尽管它可以被添加到一个适度的优势。gydF4y2Ba^17gydF4y2Ba在这个意义上，函数的几种自然类别是可进化的;实际上，函数易受一种有限的弱形式的学习称为gydF4y2Ba统计学习gydF4y2Ba．gydF4y2Ba^18gydF4y2Ba在“基因之间的游戏”一节中，我们讨论了机器学习算法和进化之间另一个有趣的联系。gydF4y2Ba

回到顶部gydF4y2Ba

性的角色gydF4y2Ba

性在生命中几乎是普遍存在的:在动物和植物中通过精子和卵子的结合发生，在真菌中通过菌丝的融合发生，甚至在细菌中也发生:gydF4y2Ba^34gydF4y2Ba例如，两个细菌细胞可以配对，并在它们之间建立一个桥梁，通过这个桥梁基因可以被转移。许多物种在某些时候进行无性繁殖或自交，但在其他时候也进行有性繁殖，保持它们的基因型洗牌良好。相比之下，不以任何形式或方式交换基因的物种，被称为“专属无性动物”，是极其罕见的，它们栖息在生命之树的稀疏、最近的小枝上，来自失去了性行为的有性祖先物种，并在没有产生子种的情况下走向最终灭绝。gydF4y2Ba^22gydF4y2Ba

性不仅本质上是普遍的，而且似乎是生命的中心舞台，是各种各样奇妙行为和结构的基础:从细菌结合到减数分裂(细胞分裂产生配子)的激烈分子机制，从花的颜色到鸟的求偶舞蹈，从雄鹿打架一直到人类激情的戏剧，生命的大部分似乎都围绕着性。所以为什么?性在进化中可能扮演什么角色?gydF4y2Ba

一个常见的答案是，性别产生了大量的基因多样性，因此它一定有助于进化。但是，就像性行为将基因组合组合在一起一样，它也会将它们分解:下一代将缺少高度成功的基因型，因为孩子的一半基因来自父母双方。要说性的作用是创造特殊的、高度有利的基因组合，就好比看一个男人钓到鱼后把鱼扔回海里，然后得出结论说他想给家人的餐桌带来食物。(顺便说一句，遗传算法的设计者们很清楚性的这个缺点，他们通常会把最成功的个体传给下一代，这一策略被称为“精英主义”，然而这是自然界不容易模仿的。)gydF4y2Ba

进化理论家花了大约一个世纪的时间来寻找性别在进化中的作用的其他解释，但所有的20个gydF4y2Ba^thgydF4y2Ba世纪的解释只有在特定的条件下才有效，这与自然界中普遍存在的性相矛盾。gydF4y2Ba^{9gydF4y2Ba，gydF4y2Ba一个gydF4y2Ba}

这不是一个小问题。想象一下，例如，即使大部分陆地世界是绿色的，我们也不知道树叶为什么会存在。这在我们对自然的理解上是一个相当大的差距。不知道性的作用是一个更大的差距，因为交换基因的生命形式远远多于光合作用。难怪性在进化生物学中被称为“问题女王”。gydF4y2Ba^6gydF4y2Ba

由于性别会破坏基因组合，进化中主要认为有效的选择作用于个体的等位基因，gydF4y2Ba^38gydF4y2Ba也就是说，每个(非中性的)等位基因本身要么是有益的，要么是有害的。根据这一思路，有两种主要的力量驱动着等位基因的频率:作为独立角色作用于等位基因的选择(等位基因通常被认为是对适应度的附加贡献)和随机遗传漂变(如前所述，对等位基因频率的随机抽样效应)。等位基因之间的相互作用，位点内部和位点之间的相互作用，尽管它从一开始就引起了种群遗传学的兴趣gydF4y2Ba^{10gydF4y2Ba，gydF4y2Ba39gydF4y2Ba}在“上位性”一词下起了次要作用，常常被当作是对上述问题的一个简单更正。几年前，在与生物学家Marcus Feldman、Jonathan Dushoff和计算机科学家Nicholas Pippenger合作时，我们提出了一个问题，等位基因之间的相互作用是否对以一种尚未探索的方式理解性的作用至关重要。gydF4y2Ba^{23gydF4y2Ba，gydF4y2Ba24gydF4y2Ba，gydF4y2Ba25gydF4y2Ba，gydF4y2Ba26gydF4y2Ba}基于用来描述基因型频率如何随世代变化的标准方程(参见达尔文和孟德尔侧栏)，我们证明了两性和无性之间的一个重要区别:在无性进化中，等位基因的最佳组合总是占上风。然而，在性别存在的情况下，自然选择倾向于“混合”等位基因，这些等位基因即使可能不参与任何真正伟大的基因组合，也能在各种不同的组合中充分发挥作用。gydF4y2Ba^{23日gydF4y2Ba}换句话说，在侧边栏中假设的3乘3适应度情景中，无性进化的获胜者将是适应度矩阵中最大的条目(在本例中为1.05)。相比之下，粗略地说，性进化会倾向于那些平均值较大的等位基因(行和列);这里的“平均”考虑到了这些基因型在人群中的流行程度，正如我们将探讨的那样。gydF4y2Ba^bgydF4y2Ba

回到顶部gydF4y2Ba

性别是一个随机算法gydF4y2Ba

在过去几十年里，算法研究中最核心和最引人注目的主题之一是随机化的惊人力量。gydF4y2Ba^29gydF4y2Ba矛盾的是，唤起机会通常是解决计算问题最安全、最有目的和最有效的方法。首先，它有助于避免最坏的情况，如快速排序。第二，从分布中抽样gydF4y2BaDgydF4y2Ba帮助在相互竞争的假设之间做出决定gydF4y2BaDgydF4y2Ba:用于软件测试的随机算法，以及用于测试素数或多项式恒等式的有效性的随机算法是这样的。gydF4y2Ba

性别下的进化可以看作是后一种随机算法的实例。假设我们想设计一个假设的进化实验，以确定在所有基因组合中，某一特定基因的新等位基因是否比其替代等位基因表现得更好。如果种群是无性繁殖的，可以通过在一个个体的基因组中插入这种突变，然后测量由此建立的谱系，看它是否繁殖。这种抽样是非常低效的，因为我们从一个小的样本池(刚好在群体中可用的基因型)中取样，并且必须在许多个体中重复多次插入。但如果种群是有性的，那么在log之后插入一次突变gydF4y2BangydF4y2Ba一代又一代,gydF4y2BangydF4y2Ba是与这种特殊等位基因相互作用的基因数量，gydF4y2Ba^33gydF4y2Ba我们将从所有的样本中取样gydF4y2Ba可能的gydF4y2Ba原则上可以构建的基因组合。性使进化能够从基因组合的整个空间中快速取样，在它们出现在种群中的分布情况下。更重要的是，性别下的进化不仅决定了相互竞争的假设(哪个等位基因表现更好)，而且还决定了gydF4y2Ba实现了gydF4y2Ba这个决定(最终，并且极有可能，它将决定谁是赢家)。gydF4y2Ba

最后，用计算机科学家所熟悉的术语和概念来解释性生活在生活中无处不在的另一个观点，请查看红蓝树定理侧栏。gydF4y2Ba

回到顶部gydF4y2Ba

基因之间的博弈gydF4y2Ba

在种群遗传学中寻找由自然选择优化的数量的研究由来已久。费雪想要一种进化理论，它的数学定律和热力学第二定律一样简洁而核心，gydF4y2Ba^10gydF4y2Ba而赖特指出，二倍体位点上等位基因的频率会朝着增加种群平均适应度的方向变化。gydF4y2Ba^40gydF4y2Ba后来，研究人员再次尝试寻找可以描述进化的李亚普诺夫函数，尽管收效甚微。gydF4y2Ba

我们对涉及混合性的分析最大化原则的研究以一个令人惊讶的结果结束:我们没有回答“进化优化是什么?”这个问题，但是，也许更有趣的是，我们确定了每个基因在性别进化过程中似乎优化的数量。与埃里克·查斯坦和乌梅什·瓦齐拉尼一起，gydF4y2Ba^7gydF4y2Ba我们关注的是达尔文·孟德尔侧栏中描述的标准方程，在一个被称为gydF4y2Ba弱的选择gydF4y2Ba．gydF4y2Ba^30.gydF4y2Ba弱选择是普遍认为基因型之间的适应度差异很小的假设。基因型的适合度gydF4y2BaggydF4y2Ba在这个体系中gydF4y2BaFgydF4y2Ba_ggydF4y2Ba= 1 +gydF4y2Ba年代gydF4y2Ba_ggydF4y2Ba,在那里gydF4y2Ba年代gydF4y2Ba很小,gydF4y2Ba_ggydF4y2Ba是gydF4y2Ba微分健身gydF4y2Ba基因型，范围为[1,1]。gydF4y2Ba

利用弱选择假设，经过一些代数操作后，我们注意到性别下的种群进化方程在数学上相当于一个新的过程，这需要一种完全不同的方式来看待进化:gydF4y2Ba

• 这一过程是有机体基因之间的博弈。回想一下，游戏是几个玩家之间互动的数学模型，每个玩家都有一组可用的行动或纯策略，还有一个效用函数:玩家在游戏中试图最大化的目标，从每个玩家的行动选择到一个实数的映射。这里的博弈是重复的，也就是说，相同的博弈被反复进行了很多轮，每轮对应的是一代人的人口。gydF4y2Ba
• 每个基因/玩家的可用动作与基因的等位基因相对应。gydF4y2Ba
• 在每一代中，每个基因都选择并执行一种混合策略:它的行为是随机的，也就是说，它的等位基因。在这种混合策略中，分配给每个等位基因的概率对应于该等位基因在这一代群体中的频率。gydF4y2Ba
• 博弈论的复杂性主要是由于玩家目标之间的冲突。但在基因参与的游戏中，没有冲突——这不是道金斯自私的基因比喻:所有玩家都有相同的效用函数，这是由玩家的选择导致的基因型的适应度。相同效用的博弈在博弈论中称为协调博弈，是最简单的一种。只有在玩家认知能力较弱或不能有效沟通的情况下，他们才会感兴趣。gydF4y2Ba
• 在重复博弈中，玩家必须根据前几轮的结果，在下一轮更新自己的混合策略。这里有一个最大的惊喜:在这个游戏中，基因使用的更新规则与一个古老的学习算法相同，计算机科学家熟知它的强大能力，在许多困难的问题和环境中出奇地好gydF4y2Ba增加的重量gydF4y2Ba更新算法(MWU),gydF4y2Ba^2gydF4y2Ba在机器学习中也被称为“无悔学习”或“对冲”(参见在线附录中的“专家问题”框)。MWU改变频率gydF4y2BaxgydF4y2Ba_我gydF4y2Ba的gydF4y2Ba我gydF4y2Ba基因的-th等位基因如下gydF4y2Ba

在哪里gydF4y2Ba米gydF4y2Ba_我gydF4y2Ba的期望差适合度是正的还是负的gydF4y2Ba我gydF4y2Ba-当前基因库中的第一个等位基因。这个量gydF4y2Ba米gydF4y2Ba_我gydF4y2Ba是衡量我们所谓的gydF4y2Ba可混性gydF4y2Ba等位基因的gydF4y2Ba我gydF4y2Ba在当前的基因组合中，它与其他基因的等位基因形成合适组合的能力。总而言之，在性进化的每一代中，每个基因通过一个因子来提高其每个等位基因的频率，这个因子随着该等位基因在当前一代中的混合性而增加。自然地，由方程得到的量被适当地归一化，以便加为1。gydF4y2Ba

这是一种全新的看待进化的方式。这是一个富有成效的观点，因为它变得更有趣:让我们回头看看更新后的等式1，再问一个问题:基因对等位基因的新概率的选择，是在优化什么吗?这一次，答案非常清晰:是的，等式1中所示的基因对等位基因频率的选择优化了以下特定于该基因的等位基因频率函数:gydF4y2Ba

在这里gydF4y2Ba米gydF4y2Ba_我gydF4y2Ba表示等位基因的累积相对适合度gydF4y2Ba我gydF4y2Ba的和gydF4y2Ba米gydF4y2Ba_我gydF4y2Ba在公式1的所有代中gydF4y2BatgydF4y2Ba1.很容易注意到，这是一个严格凹函数，因此有一个最大值，这个最大值可以通过常规计算检查，正好是等式1中更新的新频率!注意到的第二项是分布的熵gydF4y2BaxgydF4y2Ba这是一个众所周知的衡量分布多样性的指标。gydF4y2Ba

这里有很多出乎意料和发人深思的地方，但也许最令人惊讶的是，这种对进化的全新解释潜伏了近一个世纪，如此接近这些老生常谈的方程的表面。像MWU这样有效的算法参与性别下的进化也很重要。我们报纸的一篇评论指出了这一点gydF4y2Ba^5gydF4y2BaMWU也存在于无性生殖中。事实上，无性进化可以被简单地认为是MWU帮助大自然选择基因型。然而，我们的观点是，在性进化中，这幅图要复杂得多，有机得多，发生在生命层次的更深处:个体基因相互作用，每个基因使用MWU“管理它在等位基因上的投资”，在由其他基因创造的环境中，当然还有环境。gydF4y2Ba

函数是进化中罕见的显式优化原理。第二项，尤其是它的大常数系数(回想一下选择强度gydF4y2Ba年代gydF4y2Ba是小的，|gydF4y2Ba米gydF4y2Ba_我gydF4y2Ba| 1)认为，对多样性的关注是这一机制的一个重要组成部分，这一评论可能与遗传多样性如何保持的问题有关。但在非多样性术语中有一个神秘之处:适应度系数的累积性质gydF4y2Ba米gydF4y2Ba这表明，在决定下一代的基因组成方面，任何前一代的表现都和当前一代的表现一样重要。这怎么可能呢?gydF4y2Ba

通过博弈论和机器学习，以及最大化原理，进化和算法之间令人惊讶的联系是最近才出现的，对它们的全面解释还在进行中。gydF4y2Ba

如前所述，我们所讨论的关于性的洞见揭示了遗传算法的奥秘。在启发式和进化论之间存在着不匹配。启发式应该努力创建包含优秀个体的种群。相比之下，性别下的进化似乎擅长于一些明显不同的事情:创造一个“好种群”。所以，难怪遗传算法不是最好的启发式方法。另一方面，这些见解也表明，当寻求解决方案的鲁棒性时，或当真正的目标未知或不确定或容易变化时，遗传算法可能是有价值的。gydF4y2Ba

回到顶部gydF4y2Ba

随机突变吗?gydF4y2Ba

什么是突变?点突变(单个碱基的变化，比如a变成C)只是故事的一部分，因为许多重要的突变都是DNA小片段和大条带的重排:复制、删除、插入、倒置等等。gydF4y2Ba^13gydF4y2Ba长期以来，人们一直认为突变是辐射损伤或复制错误等意外事故的结果。但到目前为止，我们有大量的证据指向导致和影响突变的相关生物机制。gydF4y2Ba^22gydF4y2Ba

例如，我们知道基因组的一个区域与另一个区域发生突变的几率是不同的，并且会受到本地和远端DNA的影响。gydF4y2Ba^22gydF4y2Ba人类近四分之一的点突变都发生在C碱基上，这个碱基在C碱基经过化学修饰后的G碱基之前。gydF4y2Ba甲基化gydF4y2Ba）;gydF4y2Ba^11gydF4y2Ba甲基化被认为是复杂的酶促过程的结果。关于重排突变，有强大的诱变剂(gydF4y2Ba创建突变gydF4y2Ba)，例如转座元件:DNA序列容易从基因组的一个位置“跳跃”到另一个位置，并携带其他DNA序列。gydF4y2Ba^13gydF4y2Ba哺乳动物怀孕的关键步骤(gydF4y2BadecidualizationgydF4y2Ba)是大约1500个基因大规模进化重组的结果，部分是由转座因子介导的。gydF4y2Ba^27gydF4y2Ba此外，参与重排突变的基因序列很可能是功能相关的，因为它们可能在3D空间中彼此接近，并具有序列相似性，这两者都允许通过基于重组的突变机制相互作用(参见LivnatgydF4y2Ba^22gydF4y2Ba和引用)。事实上，影响性别重组的机制也涉及到突变，并且实际上产生不同类型的重排突变，这取决于存在的基因序列。gydF4y2Ba^13gydF4y2Ba最后，不同的人群会经历不同种类的突变，从而产生相同的有利效果，比如疟疾抗性，这表明人群之间的基因差异导致了突变起源的差异。gydF4y2Ba^22gydF4y2Ba

---

在启发式和进化论之间存在着不匹配。启发式应该努力创建包含优秀个体的种群。性别下的进化似乎擅长于一些明显不同的事情:创造一个“好的种群”。gydF4y2Ba

---

由于拉马克的遗产，突变可能不是偶然的这一观点仍然受到怀疑。拉马克在1800年左右相信，有机体可以通过与环境的相互作用，感知进化改进所需的东西，并能够做出正确的遗传变化。从现代生物学的角度来看，这似乎是不可能的——对计算机科学家来说，这听起来就像反转单向函数或哈希函数——意外突变的概念流行起来。但在科学领域，人们不能想当然地认为，唯一相关的选择是那些熟悉的、盒子里的选择。突变是随机的，但把它们看作随机的可能会更有成效，就像随机算法的输出是随机的一样。事实上，突变是一种生物过程，因此它们必然受到基因之间相互作用的影响。这个关于遗传的新概念是令人兴奋的，因为它创造了一个进化的形象，甚至更明确的算法。这也意味着，一个有机体中的基因相互作用会给该有机体的后代留下遗传影响。gydF4y2Ba^22gydF4y2Ba由性创造的幸运基因组合注定从地球表面消失(我们前面比喻中的渔夫把鱼扔了)已经不再重要:它可能已经通过诱变性对种群产生了持久的影响。最后，影响突变的生物机制可能自身进化。gydF4y2Ba

回到顶部gydF4y2Ba

论变异的保存gydF4y2Ba

如果有一个想法渗透到所有关于进化的计算思考的各个方面，就像在过去的章节中解释的那样，那就是:基因之间的相互作用对理解进化至关重要。基因间的相互作用也出现在我们最近的研究中:一个物种内的变异是如何保存的?gydF4y2Ba

经典数据表明，对于种类繁多的植物和动物来说，蛋白质编码位点的多态性(即在一个群体中超过1%的个体中存在多于一种蛋白质变体)和这种位点在个体中杂合的比例分别平均约为30%和7%。gydF4y2Ba^31gydF4y2Ba这个数字远远超出了传统选择理论所能解释的范围。gydF4y2Ba^21gydF4y2Ba遗传变异是由突变产生的，根据群体遗传学的方程，它会因固定而减少，一个等位基因的最终胜利和同一基因的所有其他等位基因的灭绝。在许多关于这个主题的论述中，选择被假设为作用于个体基因，因此适应度是附加的。方程告诉我们，固定会在之后发生gydF4y2Ba最适合的等位基因和第二适合的等位基因之间的相对适合度的差异在哪里。固定看起来相当快。gydF4y2Ba

2014年春，西蒙斯研究所邀请了60名生物学家和计算机科学家来到伯克利，交流关于进化的观点。正是在那段时间里，Costis Daskalakis和Albert Wu共同探讨了如果考虑到基因间的相互作用，我们对固定速度的理解会受到怎样的影响。我们通过几十年前关于局部搜索复杂性的工作来探讨这个主题;gydF4y2Ba^15gydF4y2Ba该理论考察了局部搜索过程达到局部最优的难度，在许多情况下，结论是:“相当困难”。通过将这一观点应用到相互作用基因的选择中，我们证明了存在gydF4y2BangydF4y2Ba-基因系统，其中适应度是某些等位基因对贡献的总和，也就是说，超越对单个等位基因选择的下一步，对单个等位基因的固定需要成比例的2代gydF4y2Ba^ngydF4y2Ba发生。在普遍接受的复杂性假设下，也可以获得更强的结果，即局部搜索通常是难以处理的(见Johnson等。gydF4y2Ba^15gydF4y2Ba详情)。这意味着，如果考虑到基因的相互作用，固定可能会gydF4y2Ba多gydF4y2Ba比单个基因的选择机制要长。gydF4y2Ba

这种见解能解释变异的奥秘吗?还没有，因为到目前为止，除了突变和选择，我们的分析忽略了进化中作用于变异的另外两种强大力量:种群的有限性和杂合性(携带同一基因的两个不同等位基因的二倍体有机体)。gydF4y2Ba

首先,有限性。因为携带相关等位基因的个体数量是有限的gydF4y2BaNgydF4y2Ba，每一代携带每种等位基因的个体数量在[0]的范围内以一种随机游走的方式进化，gydF4y2BaNgydF4y2Ba，忽略了选择，这导致了之后的固定性gydF4y2BaOgydF4y2Ba（gydF4y2BaNgydF4y2Ba一代又一代。gydF4y2Ba^19gydF4y2Ba第二，二倍体引入了超显性的可能性，在这种情况下，拥有一个基因的两个不同等位基因的生物比拥有一个等位基因的两个副本或另一个等位基因的两个副本的生物更适合。在显性情况下，选择方程指向稳定的变异，两个等位基因在群体中享有稳定的高频率。gydF4y2Ba

有限种群效应、杂合性效应和选择效应对跨位点等位基因组合的影响是如何相互作用的，这是进一步研究的重要课题。gydF4y2Ba

回到顶部gydF4y2Ba

后记gydF4y2Ba

计算机科学家对进化取得如此巨大成就的聪明方式感到惊叹:系统具有显著的资源效率、可靠性和生存能力、对外生环境的适应性，更不用说对通信、合作、视觉、运动和推理等难题的独创性和原始解决方案了。人们不禁要问:gydF4y2Ba什么算法能在10分钟内完成所有这些gydF4y2Ba^12gydF4y2Ba步骤?gydF4y2Ba在10号gydF4y2Ba^12gydF4y2Ba之所以会出现一万亿，是因为人们认为这是自生命诞生以来的世代数3.5·10gydF4y2Ba^9gydF4y2Ba多年前(请注意，我们的大多数祖先最多只能活一天)。这并不是一个巨大的数字:手机处理器在一小时内要执行更多的步骤。gydF4y2Ba

在过去的十年里，计算机科学家和进化生物学家共同努力，对围绕进化的核心开放问题提出了新的见解，其中令人惊讶的是，从计算的角度看待进化，提出了一个关于“算法”问题的答案。当然，在这个过程中，更多的问题也被提出，引起了类似的调查。gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

查尔斯·巴贝奇(左)和查尔斯·达尔文(右)的肖像。中间是达尔文的草图，展示了共同世系导致分支模式的原理。gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

数字图书馆是由计算机协会出版的。版权所有©2016 ACM, Inc.gydF4y2Ba

---

评论gydF4y2Ba

---

显示gydF4y2Ba3gydF4y2Ba评论gydF4y2Ba