|
本帖最后由 喜欢喝冰茶 于 2013-10-7 12:05 编辑
( C' x5 }9 S( w2 ~
5 N& | G. m( ?* R/ A& j, q; Q& Z已经有同校指出了blast,一个用于对生物大分子的测序程序。这东西正式诞生于1990年,同年人类基因组计划启动。它不仅可以用于DNA/RNA的测序,还可以对蛋白测序。六年前在河里曾经写过一个搭积木的小玩意儿,其中涉及到利用计算方法来预测实验中很难测量的蛋白质空间结构,最有效的计算方法就是同源模型。在这个模型里面,我们允许寻找的字符串,string2可以不用严格的和string1,也就是模板序列,匹配的。换句话说,就是字符串匹配是容错的。具体到主贴里提到的真实问题的挑战,就是模板字符串是人类的基因组(genome),单链长达3billion结构单位,也就是3billion的字符长度,而DNA是双链的,也就是6B的长度。想一想,每个人都是unique的,所以即使都是“健康人”,每个人的基因组都不会完全一样,因此,这种字符串的匹配一定是允许错误的,否则的话,如果大家都一样,即使算法速度再慢都不是问题,因为只做一次,从时间复杂度上,就是0。
, P5 D* F7 S, Q4 g; i4 W
, z5 x4 A( w* B1 B7 N! X; H那么如果考虑容错的匹配,基于bwt方法的算法将面临一个巨大的挑战,因为BWT是严格转换的,可是容错的实际需要,就要考虑转换前和转换后的字符串的错误问题,这会使的问题非常复杂。因此,现在的解决方案就是,当我们需要更多的关注容错的问题时,我们仍然使用传统的,也就是blast所使用的Smith-Waterman算法。具体的细节,感兴趣的可以google/wiki,基本来讲,这是一种被称之为动态编程的计算机算法,可以很好的考虑容错问题,诸如substitution、insertion、deletion或者indel(也就是insertion和deletion的混合体),而这些“错误”,则广泛的存在于病人的基因组中,特别是癌症基因组。当然,现在所使用的smith-waterman基于的方法都是修改了的,主要是计算机算法上的加速,诸如hash的SW算法。* q* a* J6 a; X/ V
1 e5 [4 U, w2 U2 n3 S
但是,bwt基于的方法,运算速度非常快。曾经有朋友几年前做过测试,拿上一代mac book pro,对于5万个长达100字符的输入string2s,string1是人类第一号染色体的DNA序列。blast要跑a couple of minutes,但是第一代bwt based的应用程序,在用手捋了一下头发之后,结果就出来了,当时朋友还以为自己错了。所以相对于blast所使用的算法而言,以bwt为基础的应用,诸如bowtie/bowtie2,bwa(short read version),soap(主要运行于HPC上,由位于深圳的华大基因开发,他们大概是曙光的最大用户),这些闻名遐迩的应用程序(从文章引用次数上,bowtie是最早的,发表于2009年,引用数已经接近3千,bwa大约2千五,soap约为700。引用它们的文章,不仅包括Nature,Science,Cell还有医学领域里的一些著名杂志,像新英格兰医学杂志),使得新型测量技术得以广泛的应用。如果不考虑监管、法律和伦理方面的问题,在可以预见的将来,你的mobile device里存储自己的DNA序列将不再是梦想而是现实,而人们同时希望,DNA序列的检测成为新生儿的常规检查。 |
|