在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