临溪笔记

Tag: 算法

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

“突变率很低,地球年龄又很短,要想演化出人类这样具有高度文明的智慧生物是完全不可能的。”——这是智设论者用以攻击演化论的常见论点。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],但未能给出数学上的解释和证明。其灵感来源于“无限猴子定理”。

在50亿年后太阳变成红巨星之前能精确比对多少分子序列?

最近在构思一篇关于“计算人类末日”的文章,搜集了一些相关的资料,突然联想到了标题中的这道曾经的作业题,遂随手写下此文。。 (作者不是标题党,不过标题中的这个问题我还是要放到本文的最后再来回答。) 当分子生物学中唯一的法则“中心法则”饱受系统生物学家的攻击和批评[1]的同时,由基因组学发展出来的另一个“中心法则”——序列决定结构,结构决定功能——则显得更加无懈可击。而生物信息学也正是基于这一新的法则来分析海量的生物学数据的。由此,序列分析也成为了这一新学科的基础。这里的“序列”主要指的是生物大分子中的DNA、RNA和蛋白质。 序列分析中的主要工作之一是序列比对。通过检验不同序列间的相似性程度,可以对它们之间的同源性和进化关系进行判断。我们现在看到的那些进化树,虽然在一些细枝末节上还存在很大争议,但它们大多都是通过这种分子水平上的序列比对而构建起来的,比以往的博物学家们只能在形态学和解剖学上进行比较要精确得多了。 通过测序,我们可以把这些线性的生物大分子变成由特定字符集组成的字符串,存储到熟悉它们的计算机中。如DNA的字符集是{A,T,C,G},RNA是{A,U,C,G},蛋白质则是那20种基本氨基酸的单字母缩写。在计算机中用处理字符串的方法来分析这些序列,比用纯生物学的方法要方便、快捷、准确多了。 那么到底要如何比对这些序列呢?这里就不得不要提到一个算法——动态规划(Dynamic Programming).讲解“动态规划”的中文维基页面上用斐波那契数列的例子来解释这个算法是如何工作的。如果没有理解,也没有关系,因为心理学告诉我们,只要能把抽象的问题具体化,其实也没有什么是难理解的。所以这里让我们来考虑一下下面这个更加现实的问题。 假设你要去一个陌生的大城市旅游,但坏消息是你只有不到一天的时间,肯定不能把城市里所有的景点游览完。同时还有个好消息:你有这个城市的地图,可以提前规划路线。作为限定条件,在这个城市里游览的时候,你只能向东或向南前进,不能走回头路。那么你要如何选择路线才能尽可能多地浏览景点呢?这个问题也就是经典的“曼哈顿游客问题”(Manhattan tourist problem). “曼哈顿游客问题”中的地图。(在这里我们可以忽略那条斜街。)图像来源: An introduction to bioinformatics algorithms

用迷宫困住死理性派?没门!

这是一种充满复杂通道的建筑物,很难找到从其内部到达入口或从入口到达中心的道路。在世界的不同文化发展时期,这些奇特的建筑物始终吸引人们沿着弯弯曲曲、困难重重的小路吃力地行走,寻找真相。还在找出口吗?不妨看看死理性派是怎么走迷宫的吧。 迷宫的历史和它的结构 迷宫最早出现于希腊神话中——用来囚禁 克里特岛国王 米诺斯 的半人半牛的怪物儿子 弥诺陶洛斯 。米诺斯每年都会送 7 对童男童女进来供他儿子享用。后来在米诺斯女儿阿里阿德涅的帮助下,雅典英雄 忒修斯 靠着一团金线,摸进迷宫顺利地杀死了这头怪物。 早期的一些绘画艺术还原了这座传说中克里特岛迷宫。很多人发现,这座迷宫虽然很绕,却并没有岔路,只要“一条道走到黑”,就能来到中心。也就是 欧拉路径 ,即从迷宫的入口到中心遍历了所有的边且没有重复。 从左至右:迷宫中的弥诺陶洛斯,14世纪杰里科地图,克里特式迷宫。 图像来源:Wikipedia 想象一根有限长的绳子,如果要用这根绳子来围成一条路径,且使得人在走这条路径的时间花费尽量长,那么最直接的方法就是建造这样的“克里特式迷宫”,让线圈紧密地盘绕再盘绕。 克里特式迷宫可以当做很美的装饰画,也能在工业实践中得到广泛应用,但它因为没有极具迷惑性的岔路,“迷”的属性并不算突出。因此后来就从这种最初的迷宫中,又发展出了各类复杂的迷宫。 从数学上来说,形状奇怪、看起来让人眼花缭乱的各种各样的迷宫,无非是一个图。当我们不考虑各结点的具体位置,而只考虑其相对位置,也不考虑各条边的具体长度和形状时,就可以把迷宫的拓扑结构画出来。 对于非克里特型迷宫(克里特型迷宫中没有分岔和歧路,不能用“图”表示),可根据其拓扑结构分为两大类,单连通的和多联通的。单连通的迷宫,图中没有回路。多联通的迷宫,图中包含回路。那如何判断一张迷宫地图是单连通的还是多联通的呢?只要看它的墙的结构就行了:如果迷宫中的墙都是互相连着的,那它就是单连通的;如果迷宫中有孤立的、不与其他墙相连的墙,这个迷宫就是多联通的。迷宫的类型不同,在其中行走到达目的地的策略也就不同。 破解黑暗中的迷宫 对于事先我们并不知晓全貌的迷宫,或者即使我们能了解到它的全貌(比如一些旅游景点中的迷宫),但置身其中时仍会有“旁观者清,当局者迷”的感觉。这样的迷宫该如何破解呢? 当然,你可以选择神话中忒修斯拉线绳的方法——如果你有足够长的绳子的话,这无疑是最保守和安全的方法。但这里要介绍的几种比它巧妙的多的方法。 首先就是“左/右手法则”方法。顾名思义,就是进入迷宫后,选择一个方向,之后贴着墙壁一直走下去。这是最常见的走迷宫方法,其原理其实在上面“克里特式迷宫”中也已提到,就在于考察迷宫的拓扑结构,无论围墙是多么的蜿蜒曲折,把它抻直了也就是一根线段而已,迷宫的出入口分别对应着这条线段的两个端点。我们从入口进(或者选择该条线段上任意一点开始),沿着这条线笔直走下去,当然会走到出口。但这个法则也时常有失灵的时候。因为它的前提是“入口和出口都在一条线段上”,也就是说这堵墙必须是连通的才行,而如果遇到“回字形”迷宫,出口和入口并不连通,则会出现绕了一圈返回原地的情况。