演化的时间复杂度与黄鼠狼程式

by 林溪|D-Horse

“突变率很低,地球年龄又很短,要想演化出人类这样具有高度文明的智慧生物是完全不可能的。”——这是智设论者用以攻击演化论的常见论点。2010年,美国宾夕法尼亚大学的数学家Herbert Wilf和遗传学家Warren J. Ewens则用数学方法对这种观点予以有力还击,他们给出的答案是:There’s Plenty of Time for Evolution[1].

可以把基因组的演化想象成一个密码破解的过程。我们对这个密码几乎一无所知,但知道它的长度为L,其中的每个字符都来源于一个有K个字符的字母表。按照智设论者的观点,这个密码是这样来进行暴力破解的:用字母表中的字符随机生成一串长度为L的密码,与正确的密码相比对,如果不正确,那么再重新生成(不记忆已比对过的字符串),再比对,直到与正确的密码相一致为止。这个破解算法的时间复杂度为指数级的O(K^L),也就是说平均要K^L次才能破解出正确的密码。这是什么概念呢?让我们想象一个拥有20000个可突变基因位点的基因组,即L为20000,另外在基因组水平上,根据生物学统计信息,这里的K值可近似取40(具体怎么算出来的见文末注解[2]),那么要想正确演化出这样的基因组平均需要10^34040代,即使按每年可繁衍、演化100代计算,也需要10^34038年,而生命的演化史也只有3*10^9年而已。。

智设论者的想法肯定是错误的,那么到底是哪里出了问题呢?很简单,就是他们忽略了演化的一个关键因素:自然选择。基因突变是演化的原料,自然选择则是演化的动力。修改一下上文的模型,可以设定这样一个“间谍”,在你每次进行破解之后,这个“间谍”会告诉你哪些位置猜对了,这些猜对的位置便不用再猜,只用继续再猜那些没猜对的即可,这个“间谍”即相当于起到了“自然选择”的作用。这也是符合遗传学规律的,那些适应性强的基因(比如与表达眼睛相关的)一旦固定就很难消失,不会因为其它基因(比如与表达肝脏相关的)未能演化出来而被淘汰。根据这个模型,Herbert Wilf计算出的演化时间复杂度为O(K*logL),并给出了用于描述平均需要演化多少次的公式:

这里的β(L)是一个关于logL的周期函数。(具体论证过程请参考原论文。)

现在用这个公式再计算下上文中所述的那个例子,代入K=40,L=20000,结果约为390,只需要390代即可。

当然,这只是一个非常简化的关于演化的数学模型,生命的演化过程远比我们想象的要复杂得多。事实上,在1986年,道金斯也曾提出过一个“黄鼠狼程式”(Weasel program)来回击演化中类似的常见误解[3],但未能给出数学上的解释和证明。其灵感来源于“无限猴子定理”。

——————以下内容摘自维基百科:黄鼠狼程式——————

概观

在道金斯的著作The Blind Watchmaker里面第三章,他介绍了以下程式, 并且提到了著名的无限猴子定理:

I don’t know who it was first pointed out that, given enough time, a monkey bashing away at random on a typewriter could produce all the works of Shakespeare. The operative phrase is, of course, given enough time. Let us limit the task facing our monkey somewhat. Suppose that he has to produce, not the complete works of Shakespeare but just the short sentence ‘Methinks it is like a weasel’, and we shall make it relatively easy by giving him a typewriter with a restricted keyboard, one with just the 26 (capital) letters, and a space bar. How long will he take to write this one little sentence?

这个情境是说,对于任何一个无意义的字串,假设里面有随机的28个字母,那么所有可能的组合就有27^28, 或者说大约是10^40,所以一只猴子产生出正确答案的机率是非常非常小的。这里无论哪种特定顺序,且是28个字母的字串作为答案时,其正确的机率都跟道金斯选择的目标”METHINKS IT IS LIKE A WEASEL”一样的小(注解)。

我们可以使用借由一个高速产生字母和空白组合的电脑程式,来模拟道金斯假说中的猴子。但是即使我们以每秒钟几百万个组合的速率,并且给予宇宙的年龄这么长的时间去尝试,我们还是几乎不可能正确的产生”METHINKS IT IS LIKE A WEASEL”这个目标字串。

道金斯想借由这个范例来解释对演化一个常见的误解,这个误解是,演化认为像是DNA或者像蛋白质这类有机物,这些东西是大自然中由原子随机组成这么复杂的形式。根据这些计算显示,要随机排列出任何蛋白质的氨基酸序列都是极度不可能的。

道金斯之后证明了有累积效应的天择会大量减少到给定目标所需的步骤。根据道金斯的说法:

We again use our computer monkey, but with a crucial difference in its program. It again begins by choosing a random sequence of 28 letters, just as before … it duplicates it repeatedly, but with a certain chance of random error – ‘mutation’ – in the copying. The computer examines the mutant nonsense phrases, the ‘progeny’ of the original phrase, and chooses the one which, however slightly, most resembles the target phrase, METHINKS IT IS LIKE A WEASEL.

算法范例

虽然道金斯本人没有提供他的程式码,但是一个”黄鼠狼”式的算法可以操作如下:

1.从一条具有28个字母的随机字串开始
2.复制100个相同的字串,然后每个字母有5%的机率会换成另一个随机的字母
3.将每个字串与目标 “METHINKS IT IS LIKE A WEASEL”作比较,给每个字串进行评分(正确的字母出现在正确的位置上此字串得一分)。
4.如果任何字串达到28分,也就是满足条件时,程式停止
5.否则,取用分数最高的字串,然后回到步骤2

在这里,一个”字母”指的是大写的字母或空白。 在道金斯的书里面没有明确指出字串的复制数目跟突变机率,这里的100个复制跟5%的突变机率只是个范例。另外值得注意的是,正确的字母并没有被”锁住”:也就是说,即使一个字母已经出现在正确的位置,还是有可能在下一代突变的时候被改掉。

——————以上内容摘自维基百科:黄鼠狼程式——————

在对具体器官演化史的研究上,科学家们也发现很多器官的演化要比我们想象的要快。比如眼睛,从眼点演化出鱼眼,只需要35万代。以一代为一年(这是大部分低等动物的情况)计算,也就是说,只需要35万年,这在地质年代上只是一瞬间。(参考道金斯The eye in a twinkling和方舟子《达尔文的眼睛》。)

[1]Wilf, H. S., and W. J. Ewens. 2010. There’s plenty of time for evolution.

[2]k=40:平均每个新生儿都会有5个基因突变发生在编码区或调控区,按每年诞生100万新生儿计,那么总共有500万基因突变,换言之对于一个有20000个基因的基因组,其每个基因都有约250个突变型,但是每1万个突变基因中只有1个是有可能被自然选择出来的。

[3]黄鼠狼程式中的“黄鼠狼”来源于道金斯引用的莎士比亚《哈姆雷特》中的台词METHINKS IT IS LIKE A WEASEL(据我看它像一只黄鼠狼)。之所以引用这句,据说是因为1984年时,美国人哈迪森(Richard Hardison)曾在课堂上引用《哈姆雷特》中的经典台词TO BE OR NOT TO BE来演示有关“无限猴子定理”的程序。后来这个程序被公布在他1985年出版的《巨人肩膀之上》(Upon the Shoulders of Giants)一书上。道金斯看到了这个程序,因而想出了“黄鼠狼程式”。关于黄鼠狼程式的代码可以参考这里

[4]无意间发现这篇论文的作者Herbert Wilf老先生在今年年初的时候去世了,这个是他的维基页面。他的一个学生是万智牌的设计者。