---> Bowtie <---

Bowtie把小的DNA序列拼到大的基因组上（注：RNA-seq其实最终的测序形式也是DNA）。

Bowtie使用Burrows-Wheeler算法对基因组进行index以保证小的内存占用。可以使用多线程。支持多个系统平台，如windows，Mac OS， Linux。

【Bowtie的限制】：

Bowtie设计初衷就是大基因组物种，短测序片段的mapping工作，当这些小序列至少有一个好的alignment，大部分测序质量非常高而且每一条reads的map数量比较小（接近1）。暂时不支持gapped 的alignment。

Bowtie的使用：

Bowtie有三个程序：bowtie aligner，bowtie-build indexer和bowtie-inspect index inspector，其中bowtie aligner 为主程序。

【bowtie aligner/bowtie】

bowtie以一个index和许多reads作为输入，输出alignments。

Mapping 之后的alignment 需要考虑哪些alignment是合法的，哪些是需要汇报出来的，又因单端（single end）和双端（paired end）测序方法得到的不同数据有所不同。

Bowtie默认的是于Maq相似的策略，也就是-n 模式（-n 2 -l 28 -e 70），但是也可以使用更为简单点的end-to-end k-difference策略，即-v 模式（ -v 2）。这两种模式互不兼容。

如上面限制中所讲，当满足这三个条件时，bowtie运行速度非常快，如果数据情况不同时，可能会有较长的运算时间。如果bowtie运行太慢，可以进行一些相应调整（Performance tuning）

如果reference序列中有一个以上的不确定碱基（N，-，R，Y等）时，alignment被认为是不能接受的，但是如果在reads序列中则可以被接受，当然这要看所使用的mapping策略，当reads中有不确定碱基时，被认定为与所有的碱基mismatch。

Bowtie报告alignment的过程是随机，这是为了避免mapping的偏好性，即bowtie系统性地遗漏掉一些非常好的alignment。不管何时bowtie报告alignment时都是随机选取的。这些随机性由伪随机数产生器来产生，而且认为对于同一个read来说，当起始的“seed”值相同时（--seed），bowtie总是会产生相同结果。

在默认模式下，bowtie会有一定的链偏好性，当输入的reference和reads发生（1）有些reads在正负链都可以map（2）一条链上这样的位置与另一条链上这样位置的数目不相同时，这种情况会可能发生。当对于一个给定read发生这种情况时，bowtie会以50%的概率选择一条链或者另一条链，然后随机地报告在选择的那条链上的map情况。当使用--best 选项时，通过强制性地要求bowtie选择与map 位置数量成正比的那条链来进行汇报，以减轻这种偏好性。

【-n 模式】（默认）

使用这种模式时，处理策略与Maq类似。

1. alignment 可以在高质量一端（左端）的前L个碱基（L大于等于5，使用 -l设定）中有不超过N个的mismatches（N用 -n 来设定，介于0-3）。这L个碱基被称为“seed”

2. 所有mismatch的位置（不仅仅是seed中）的Phre quality（？）的和不超过E（用 -e 来设定），如果质量不可用，Phre quality默认为40。

        可能会有很多可能的alignment满足这些条件，bowtie会比较倾向mismatch较少，第二项中和较小的alignment。当给--best 选项时，bowtie会保证报告的alignment以这两项标准来说是最好的（1更优先），这些报告的alignment是从好到坏的顺序。当使用--best 选项时bowtie的速度也会变慢。

需要注意的是，Maq会将碱基的quality约略到最近的10个（？），而且高于30的quality会约略成30，为保持可比性，bowtie也进行同样的处理，使用--nomaqround 选项可以不采用这种约略。默认下，bowtie对于-n 2和-n 3模式不是完全敏感（fully sensitive）。在这些模式下，bowtie会设置一个“backtracking limit”来限制对那些不太可能有alignment的低质量read的alignment的寻找的程度，也就是说寻找可能的alignment的“努力”程度。这可能会漏掉一些合法的具有2-或3-个mismatch的alignment。这个限制程度被默认设置为一个合理程度（不使用--best 的话是125，使用的话是800），但是用户可以用--maxbts选项来增加或者降低这个限制，如果使用-y模式的话，会相对比较慢，但是可以保证足够的敏感性（full sensitivity）。

【- v模式】

在-v模式下，alignment 不能有超过v个mismatch，其中v是通过-v选项设定的介于0-3的一个数。质量值将被忽略。如果很多合法的alignment，bowtie会汇报mismatch最少的。当使用--best 选项时，bowtie会按照mismatch数目的最好来汇报，顺序也是从好到坏。同样使用--best会比不用慢一些。

+++++++++++++++++++++++++++++++++++++++++++++++++++++

层（strata）

在-n模式下，层以“seed”序列中的mismatch来定义；

在-v模式下，层以整个alignment中的mismatch来定义。一些bowtie的选项（如--strata， -m）以层的概念来限制报告的alignment的数目。

【报告模式】

使用-k, -a, -m, -M, --best和--strata选项可以控制要报告哪些alignment。

-a 是all的意思，即报告全部的alignment。

-k 选项用来设置报告前几的alignment，可以是大于0的任意整数

如果使用默认的话，bowtie会报告它遇到的第一个alignment，因为—best选项没有被指定，所以不能保证bowtie会报告最好的alignment。默认模式等价 -k 1。

-a --best --strata ：以mismatch作为标准来进行排序和汇报，如使用--strata ，--best 也必须同时使用。

-a -m 3：限制有3个以上合法alignment的read报告，也就是只报告少于3个alignment的alignment，这种模式在用户想得到非常unique的alignment时很有用。

【双端数据】

使用双端数据需要满足以下条件：

1.两条序列必须有满足-v/-n/-e/-l选项的alignment。

2.成对序列的距离必须满足-I/-X/--fr/--rf/--ff选项的要求。

报告模式同样以-k,-a,-m选项来进行控制，但是对双端数据来说，--strata和—best选项不能使用。

Alignment中的双端，总是距离参考序列开始一段最近的一段在前。

对于map到重复序列的双端数据来说，找到一对有效的paired-end alignment非常耗时，所以默认bowtie会通过设置一个尝试的次数，默认值为100.这可能会丢失掉一些两端都落在重复序列中的双端数据，用户可以--pairtries 或者-y选项来增加bowtie的sensitivity。

【multiseed heuristic】

为了快速减少所有需要考虑的可能的alignment的数量，bowite2首先从reads以及reads的反向链中提出“子序列”（或者叫seeds），然后借助FM Index以不允许gap的方式map，这就是“multiseed alignment”,与bowtie1干的有点像，只不过bowtie1是对整条链进行这样的处理。

这种起始处理方法让bowtie2比不做这种筛选快非常多，但是有一些alignment可能会被漏掉。比如有可能对整条read来说是可能的alignment，但是因为错配或者gap，每一条子序列都无法匹配而导致整条alignment被滤掉。

在速度与sensitivity之间可以通过调整seed长度（-L），选出的seed之间的距离（-i），以及每一条seed中的错配允许数（-N），对于sensitivity更高要求的匹配，应该考虑a.让这些reads相互之间距离更短b. seed更短c.允许更多的错配。可以一个一个的调整这些选项。此外-D和-R也可以用来调整sensitivity和速度。

【不确定碱基】

在bowtie2中所有的不确定碱基（除ACGT之外）都被当成N来对待，reference中的N会有相应的惩罚，可以通--np 来设置惩罚分数。使用--n-ceil 设置一个alignment中不确定碱基数量的上限。XN来报告一条alignment中不确定碱基数量。

需要注意的是，multiseed heuristic不允许有不确定碱基，所以只有那些有不确定碱基的read来说，必须有不包含不确定碱基的子序列存在才可以。

【预设参数】

bowtie2有一些预设参数，比--very-sensitive, --sensitive, --fast, --very-fast，等价与一些参数的组合。

Bowtie-build indexer

这个程序从一个DNA序列建立一个bowtie index，其中包括.1.ebwt, .2.ebwt, .3.ebwt, .4.ebwt, .rev.1.ebwt, .rev.2.ebwt(如果DNA序列大于4 billion，后缀会变成ebwt1)。一旦index建好之后，bowtie不再需要reference序列，这几个index文件就足够了。

 

                                      ---> Bowtie2 <----

【Bowtie1 和 bowtie2的比较】

Bowtie2 建index使用的是FM index，与1不同。Bowtie1适用的read很短大概25-50，bowtie2则可以是50以上，甚至几百，几千。

总的来说：

1. 当read长度在50以上时，bowtie2更快，更敏感，占用更少的内存；而长度在50以下时，bowtie1会更好。

2. bowtie2 支持gapped的alignment，不限gap的数量，长度。

3. bowtie2 支持局部的alignment，不需要reads end-to-end（全长）的map，局部alignment会将read进行剪切以优化alignment score。

4. bowtie2 没有reads长度上限，bowtie1最多是1024nt

5. bowite2允许map到含有不确定碱基的参考基因组，而1不允许。

6. bowtie2放弃使用alignment“层”的概念，而是采用alignment连续分值谱的方式。

7. bowtie2 对于双端数据的支持更为灵活，例如，对于一对没有成对align的双端数据，bowtie2 尝试着为每一个read找到不成对的alignment。

8. bowtie2报告的mapping的质量也是连续谱式的，而不像bowtie1中要么是0要么是高

9. bowtie2不再支持colorspace reads。

【bowtie2的限制】

1.不要比对两个非常长的序列

2.如果想对相对较小的基因组（如细菌）上的敏感的alignment进行分析，bowtie2也可以，但最好考虑使用blast或者nucmer。

3.暂不支持colorspace数据。

【打分】

bowtie2与bowtie1相比，最大的改进在于，使用打分机制，而不是完全的mismatch进行衡量。

分值越高说明越相似。

可以使用--ma(match bonus), --np(penalty for having an N in either the read or the reference), --rdg(affine read gap penalty), --rfg(affine reference gap penalty) 来进行自定义。

【End-to-end 模式惩罚】

在高质量区域的一个mismatch默认会被惩罚-6，一个2bp长的gap会被惩罚-11，（gap -5，第一个碱基 -3，第二个碱基 -3）。所以end-to-end模式中一个50bp长的序列如果在高质量区有一个mismatch，有一个2bp的gap会被惩罚-(6+11)=-17分。

End-to-end模式最理想情况是0分，也就是完全匹配。

【局部alignment惩罚】

高质量区一个mismatch默认被惩罚-6，一个2bp的gap被惩罚-11，一个匹配碱基得到2分奖励，所以在局部模式下，一个50bp长但是高质量区一个mismatch，还有一个2bp长的gap，那么总的得分就是2*49-（6+11）=81分。

局部模式下，最理想情况是奖励*长度（2*len）。

【最低分数阈值】

被bowtie2认可的alignment必须达到一定的最低分数阈值，这个阈值是一个关于read长度的函数，在end-to-end模式中最低阈值为 -0.6 + -0.6*L，其中L是read长度，在局部模式下，最低阈值是20+8.0*ln（L），其中L是read长度。也可以通过--score-min 选项来进行调整。具体参考 setting function options。 

Bowtie2-build indexer

bowtie2-build indexer 依然从一个DNA序列中建一个bowtie index，不过后缀变为.1.bt2, .2.bt2, .3.bt2, .4.bt2, .rev.1.bt2和.rev.2.bt2。如果DNA序列较大，则相应后缀变为bt21. 同样一旦index建好，bowtie就不再需要reference 序列。需要注意的是，bowtie2的index和bowtie1的index是不兼容的。