Bowtie 里的FM-index 简介
原文链接：http://m.blog.csdn.net/blog/stormlovetao/7048481
最近看新发表的几篇RNA-seq比对，组装的软件，发现HISAT里面也用到了FM-index这个算法，所以就找了一下，原博文链接如上所示，说的很是透彻
另外StringTie用到的算法叫做流神经网络，我发现在chinablog上也有一篇文章详细的介绍，这里就转帖出来
下面是我对这几篇文章的一个粗略的总结，有兴趣的可以看一下，不能保证总结的就对或者完整，权当是一个参考吧，如果哪里错了，欢迎指出错误指出
##############################################
HISAT：
1：index算法基于BWT和以BWT为基础的FM index: FM 算法是以BWT为基础，在计算的过程中加了两个参数，一个是OCC，
Occ[c,r]表示在BWT（T）中第r行之前出现字符c的个数，因为如果把整个基因组存进去，每次都要重头数一遍，消耗量太大，所以是以几百行为一组为一个check point，这样内存就小了，也方便检索；另外一个是SA， 记录第r行在参考基因组中是什么位置，这个过程是在BWT操作中实现的
2：建立index的方式：全基因组FM index和局部index（特色，新的建索引库策略）核心算法会用到tophat3上
HISAT在基因组范围内有48000个局部FM index
每个长度64k，通过测试数据和真实数据的比较，发现这是一个最快的软件
HISAT的基本设计原理：
HISAT利用bowtie2来建立很多低水平结果的FM index，这些index包含两种类型：1：全基因组index；2：大量的小FMindex，每个代表64k，也因为建了很多小的index，所以总的内存使用情况也较低
3 :100bp的reads至少跨越两个exon的占34.5%，分为三类：1：每个外显子至少16bp（25.1）；每个外显子8-15bp（5.1），每个外显子1-7bp（4.2）；
另外跨越三个的3.1%。针对每种reads都有相应的比对策略
基本的比对策略的思想是先在众多index中找，如果比对上多个地方，就往两边延伸；
4：基本的性能对比
速度：110,193条reads/s， tophat 1,954
利用模拟数据正确比对率（99.2%），tophat2(97.4)
在跨越2个exon，只有1-7bp的reads来说，
uniq比对率HISAT（94.4）tophat2(77.8)
另外敏感度和准确性
HISAT（97.3,94.8） Tophat2（90.6,82.6）
100bp，20M的reads
用时26.7min，tophat2 1170分钟
#############################
1：StringTie和Cufflinks算法对比
cufflinks parsimony算法 (简约算法)：生成最少的亚型
说这种算法没有考虑转录丰度，在isoforms方面算的不准。其在算表达量的时候，按照图上的说法是用了最大似然冗余算法。
stringTie先将reads分为不同的类，然后再针对每个类的reads生成一个拼接图来确定转录本，之后每个转录本产生一个流神经网络的最大流算法来评估表达水平
这个算法的意思对应过来就是在一个基因处的若干个转录本，如何分配reads的数目才能让每个转录本的数目都处在最多的状态，发的链接上是用了一个工厂的例子。
这个算法是求解最优化的，在这篇文章上也是第一次用。
2：在RNA组装方面优劣势对比
在组装方面StringTie具有一些优势，在低表达的部分，阈值过滤5%的StringTie比阈值过滤10%的准确度和敏感度还要高（这里的准确度和敏感度是把原始数据随机抽取出来一部分数据，看看这两组随机抽出来的数据的重合度如何和ROC是一个事情）
关于组装效果，StringTie要好于cufflinks，同时他们又远远好于其他软件，就组装错误而言，文章上列举了一个例子，即附表四，cufflinks预测出来的FPKM值可以到293509.68，而StringTie最大是935，这个问题，我们在项目处理中也遇到过
3：性能对比
时间上来说：StringTie 30min cufflink 81min 其他更多
真实数据测试35-76分钟，比其他快3倍
内存比cufflink少一半
找出来的基因中，cufflink找出来的70%在StringTie中有重合，相比于cufflink，StringTie在基因重构方面对三种类型的基因更有效，分别是：低冗余，高exon数目，和多重转录本。
按照作者的说法，StringTie之所以能取得好的效果，是因为模型中有个求最有的过程；其可以通过
转录组的每个组装平衡覆盖度，算法自己可以通过合并覆盖到的深度来限制组装。
作者倒是希望通过StringTie来取代cufflink
########################################
关于tablemaker和ballgown
tablemaker的设计是为了处理cufflinks和cuffmerge的结果，一遍后面用ballgown处理，不过按照文章上说的ballgown也可以直接输入，可以是针对StringTie的结果
ballgown是一个R脚本，用来分析差异结果的，差异分布的结果是基于F-test来检测的，和我们以前用的有些不同；
就测试内存而言，cuffdiff用148G6 9个小时，而ballgown用18秒8G，
就差异结果而言，cuffdiff更保守一些，文章中用了一个例子，就是男性Y染色体的表达量数据和女性落到Y染色体的表达量数据对比，ballgown可以起到很好的效果，而cuffdiff找到的差异基因少。
所有这些软件的开发目的就是为了能在笔记本上跑开生物程序