设为首页收藏本站
开启辅助访问
切换到窄版

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
查看: 4269|回复: 0

bwt算法

[复制链接]
发表于 2011-10-6 11:01:03 | 显示全部楼层 |阅读模式
在短序列比对中,blast显得尤为笨拙,而Maq、bowtie、SOAP等则优势尽显,Maq和SOAP作者都是中国人,骄傲一番,其中以bowtie、Maq最为有效,我只用过bowtie,可谓神速。bowtie、Maq之所以成功,我觉得最重要的就是bwt算法的应用,这个本来用于文本无损压缩的算法必将像BLAST一样以后进入生物信息学课堂成为经典,仔细读并揣摩bwt算法,你会感到作者无穷的智慧能淹死你。
算法简介转自:http://hi.baidu.com/rodimus/blog ... 8e7af699250ab6.html

bwt算法:

全称Burrows-Wheeler transform,BW是两位发明者的明称,T则是强调这种算法的特性。
这种算法是非常巧妙的。
这种算法是先把输入的数据则重排列,使得相同的字符,尽量地排在一起,这样方便压缩。如果只是想把相同的字符放在一起,可以简单地对各个字符统计一下出现次数,然后放在一起。这种算法巧妙的地方是,它还可以根据重新排列后的字符串,算出原始的字符串,从而解压缩。
重排列的过程如下:
把输入串的所有rotation(所谓rotation是指轮换,比如abcd有四个轮换,abcd,bcda,cdab,dabc)排序,然后依
次把这些rotation的最后一个字符串接起来成为新的串。这里要注意两个地方,一是各个字符出现的次数是否跟源串相同,二是相同的字符是否更多地放在
一起。
第一点是很容易证明,取这些rotation的任意一位串连起来,各个字符出现的次数跟源串都是相同的。
第二点很难证明,现在粗略分析一下。假设源串含有the,排序的结果应该是"he"打头的ratation排在一起,这样最后一个字符是"t"的字
符也应该排在一起。为什么不用这些rotation的第一位串联起来呢?用第一位的话,解释起来更直观,但是用第一位串联起来的话,无法反映射回去。
现在来讨论一下怎么反映射。反映射的算法非常巧妙,从OI到ACM都考过这道题。有O(N)的算法的,实现起来也不难,只是比较难想到。
用banana举例,它的六个rotation排序为
abanan
anaban
ananab
banana
nabana
nanaba
则转换后的结果为nnbaaa,因为是有序的,我们可以反推出第一列应该为aaabnn,从而可以知道有下列六对相邻关系
na,na,ba,ab,an,an
这些相邻关系里最小的一对应该是ab,把这六组相邻关系排序一下,为ab,an,an,ba,na,na
从而知道六个rotation的第二列分别为b,n,n,a,a,a
如果不是这样的话,则它们不应该这样排列,这其实是反证法
从而可以得出另一组相邻关系,nab,nan,ban,aba,ana,ana,继续上面的过程,可以得出长度为四的相邻关系,一步步递推,最终得
出原始的所有的rotation。但是怎么知道哪个rotation是源串呢?只要在源串的结束处加一个特殊字符,然后再求rotation,最终结束符
放在最后的rotation就是源串了。


推荐阅读:
[1]李彦军,苏红旗,杨峰,李述迪,姚书科,.基于BWT的文本压缩算法研究[J].计算机技术与发展,2009,(5).
[2]Langmead B, Trapnell C, Pop M, Salzberg SL. Ultrafast and
memory-efficient alignment of short dna sequences to the human
genome. Genome Biology , 2009,10:R25.
[3]http://maq.sourceforge.net (Maq, Unpublished).
[4]Li R, Li Y, Kristiansen K, Wang J: SOAP: Short Oligonucleotide
Alignment Program. Bioinformatics 2008, 24:713-714.
您需要登录后才可以回帖 登录 | 注册

本版积分规则

QQ|申请友链|小黑屋|手机版|Archiver|生物信息学论坛 ( 蜀ICP备09031721号  

GMT+8, 2017-1-17 10:52 , Processed in 0.098690 second(s), 19 queries .

Powered by Discuz! X3

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表