注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Allen小笔记

有时会忘记努力...

 
 
 

日志

 
 

进化论中的概率-实践  

2010-01-22 11:45:14|  分类: C/C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这篇文章是看了数学之美番外篇:进化论中的概率论》后的实做.这篇文章强烈推荐读一读.
其中摘取:

论从其诞生以来受到的非难不计其数。这里提到的这篇便收集了广为神创论者提出以及广为大众误解的一些观点。其中有一点尤其引起了我的兴趣,如下:

8. 严格说起来,我们很难相信复杂如蛋白质的物质能偶然出现,更不用说人或是活细胞了。

偶然性在进化中确实存在(例如,偶然性的突变可以产生新的特征),但是进化并不依赖偶然性来产生新的器官、蛋白质或其他实体。截然相反的是,自然选择,作为进化中已知的最主要机制,却会明确保留“需要的”(能适应的)特性,消除“不需要的”(无法适应的)特性。只要选择的影响力存在,自然选择就能把进化向一个方向推进,在出乎意料的短时间内产生复杂的结构。举个例子,现有由13个字母构成的序列“TOBEORNOTTOBE”,假设有几百万只猴子,每只猴子每秒钟挑一条短语,需要78,800年才能从

^13种可能中选出这样的排列。不过,Glendale College的Richard Hardison在20世纪80年代写过一个程序,它能够在随机产生序列的同时,保证那些已经出现在正确位置上的字母不会变化(这样做倒有点《汉姆雷特》 的味道。译注:这个句子看了大半天才明白,嘿嘿)。这个程序平均只需要336次迭代就能生成上文提到的短语,时间少于90秒。更神奇的是,把莎士比亚的整个剧本重新生成一遍也只需要四天半时间。

   我们不妨把人类的DNA链当成一个长长的单词。突变是产生随机枚举的动力。那么根据上面的分析,要枚举出我们现在用的DNA,需要的迭代次数将是跟DNA链上的“字母数”(碱基对)成指数关系的。枚举一个13个字母的单词就需要26^13次方了,上亿碱基对,需要多少次迭代?更不要说人类的一代更迭就平均要耗上十来二十年了。

 类似的,我自己实现了这样子的一段代码.代码也很简单,只是发现一个比较有趣的问题:
 作者原文的公式(等比数列求和),作者这里做了一个假设,每次单词迭代的时候有且仅有可能只正确生成一个字母:
  即,当目标单词长为n时,平均需要[n×25^(n-1)×26^n]/[(26^n-25^n)^2]次枚举才能命中其中一个字母.
  假定,这个DNA链为:allenandrita , DNA链的长度为12.
数学期望∑= 26/12 + 26/11 + ....+ 26/11  ~= 80.68次. 
 当然这个是理论值,我写了一段代码去测试,每次分别执行10, 100,1000,10000,100000次去检查实际需要多少次才能完整的生成这个DNA链:allenandrita
10次检验     ->  62次生成完整的DNA链;
100次检验 -> 77次生成完整的DNA链;  
1000次检验   ->  78次生成完整的DNA链;
10000次检验  ->  79次生成完整的DNA链;
100000次检验 -> 79次生成完整的DNA链.
实际上,我的代码并没有原作者的那个假定, 即每次单词迭代的时候有且仅有可能只正确生成一个字母.但是结果却依然很靠近那个很傻很天真的假定.
那么我们来假定一下:
每一次有2个字母正确的突变生成 --> p2 = (11*12)/2*(1/26)^2*(25/26)^10
每一次有3个字母正确的突变生成 --> p3 = (10*11*12)/(3*2)*(1/26)^3*(25/26)^9
...
每一次有N个字母正确的突变生成 --> pn = (n*(n+1)..*12)/(n*(n-1)*..*1)*(1/26)^n*(25/26)^(12-n)
实在是打不出来,数学表达式.总之,随着N变大,pn概率越小.
p2 ~= 0.06596.也就是说同时出现2个正确的字母的概率已经小到了几乎不怎么影响我们的实际值了.

刚开始,我错误的使用了srand()函数,把它放入while循环了,可想而知,以现代CPU的频率来看,Time()函数返回的就是同一个值.也就是说srand()的seed都是同一个值,那么rand()出来的结果看起来真的很有"规律". :)
更多的随机函数的讨论,可以看:

随机数有多随机?

想要代码的人:Mail to :bloodysofiya@163.com
  评论这张
 
阅读(410)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017