參考：
0.bowtie jimmy 介紹
1.BWT算法
2.BWA mem 算法
3.BBQ（生信基礎(chǔ)問題16）-BWA算法原理及軟件實(shí)用
4.20171026-基于BWT算法的比對(duì)軟件原理解析（BWA & Bowtie & Bowtie2）
5.BWT-FM 算法（Burrows-Wheeler Transform And FM Index）
6.【哈佛大學(xué)】2019年生物信息學(xué)與計(jì)算生物學(xué)課程--劉小樂老師--2020 STAT115 || 英文字幕
7.比對(duì)軟件 - 專題
BWT 算法介紹：
BWT(Burrows Wheeler Transform)
BWT辅髓，數(shù)據(jù)轉(zhuǎn)換算法与斤，其實(shí)也是一種壓縮算法锈锤，基本思想就是找到字符串的重復(fù)部分來進(jìn)行壓縮寓落，還可以用來進(jìn)行序列比對(duì)庙睡。BWT會(huì)將字符串轉(zhuǎn)換成一個(gè)類似的字符串，但是轉(zhuǎn)換后的字符串的相同字符是相鄰的凰荚，這樣髓梅，我們就可以對(duì)數(shù)據(jù)進(jìn)行壓縮了。這個(gè)算法的解壓縮也很方便簡(jiǎn)單壳繁。
BWT原理
BWT編碼部分
BWT編碼壓縮步驟如下：
- 首先對(duì)要轉(zhuǎn)換的字符串震捣，添加一個(gè)不在字符串里的ASCII碼表里最小的字符。如 AGGAGC ——>
蒿赢。
- 對(duì)字符串進(jìn)行依次循環(huán)移位，得到一系列的字符串剩胁，如果字符串長(zhǎng)度為 n诉植， 就可以得到n個(gè)字符串，如下面圖里的第二列所示昵观。
- 對(duì)2中的位移后的一系列的字符串按照ASCII進(jìn)行排序晾腔，如下圖的第四列所示，第三列是排序后的字符串的原index位置啊犬。
- 取位移后的一系列字符串的首字母出來作為 F 列灼擂， 最后一個(gè)字母作為 L 列。如下圖 F 列 和L 列所示觉至。
- L 列就是最后的編碼結(jié)果剔应。
| No. | rotated | index | sorted | F | L | LF |
|---|---|---|---|---|---|---|
| 0 | AGGAGC$ | 6 | $AGGAGC | $ | C | C->$ |
| 1 | GGAGC$A | 3 | AGC$AGG | A | G | G->A |
| 2 | GAGC$AG | 0 | AGGAGC$ | A | $ | $->A |
| 3 | AGC$AGG | 5 | C$AGGAG | C | G | G->C |
| 4 | GC$AGGA | 2 | GAGC$AG | G | G | G->G |
| 5 | C$AGGAG | 4 | GC$AGGA | G | A | A->G |
| 6 | $AGGAGC | 1 | GGAGC$A | G | A | A->G |
由編碼過程，參考上圖语御，其實(shí)可以發(fā)現(xiàn)BWT編碼有三個(gè)特性(循環(huán)位移決定)峻贮，
- L 列的第一個(gè)元素是源字符串的最后一個(gè)元素。
- 循環(huán)位移可知应闯，同一行的 F 列和 L 列的元素在源字符串里是相鄰的纤控，而且 L 列元素的下一個(gè)字符就是 同行里 F 列的元素。
- 同一種字符在 F 列和 L 列里的rank是一樣的碉纺，比方說船万， F 列里的第二個(gè) A 和 L 列里的第二個(gè) A 在源字符串里是同一個(gè)A刻撒。 F 列里的第一個(gè) G 和 L 列里的第一個(gè) G 在源字符串里是同一個(gè)G,rank如下圖所示。
根據(jù)以上這三個(gè)條件耿导， 我們就可以進(jìn)行BWT解碼声怔，也就是解壓縮。
BWT解碼部分
BWT解碼舱呻，已知 L 列醋火， 推源字符串。
- 由 L 列 得到 F 列箱吕。因?yàn)長(zhǎng) 列 和F 列其實(shí)都是源串的字符的不同排列方式胎撇，但是我們知道 F 列是按照 ASCII碼排序的，所以從 L 就可以推出 F 殖氏。
- 根據(jù)第一個(gè)性質(zhì)，我們可以得到源串的最后一個(gè)字符是 L 列的第一個(gè)字符姻采，作為當(dāng)前字符(下面依次往前遞推)雅采。
- 依據(jù)上一步得到的作為當(dāng)前字符， 根據(jù)第三個(gè)性質(zhì)慨亲，我們可以得到同一個(gè)字符在 F 列中的位置婚瓜，作為當(dāng)前字符。
- 依據(jù) F 列里的當(dāng)前字符刑棵，根據(jù)第二個(gè)性質(zhì)巴刻，我們可以得到當(dāng)前字符的上一個(gè)字符是同行里的 L 列里的元素,將新增字符作為當(dāng)前字符，然后跳轉(zhuǎn)到第 3 步蛉签。
- 直到所有字符全部推算出來胡陪。
整個(gè)過程如下圖所示：
BWA/Bowtie/Bowtie2 比對(duì)算法
三者比對(duì)都是基于BWT轉(zhuǎn)換算法，或壓縮算法碍舍。
由于二代數(shù)據(jù)數(shù)據(jù)和三代reads特點(diǎn)存在差別柠座。BWA 這些主要是基于二代測(cè)序來設(shè)計(jì)。
用于二代測(cè)序的比對(duì)軟件分為SOAP類 ;BWA 類
但是SOAP 是將基因組分成很多小讀段片橡，因此內(nèi)存消耗很大妈经，速度不理想。
BWA此類算法捧书，采用BWT方法吹泡，有效節(jié)省空間，及其快速確定比對(duì)位置经瓷。
下面列出序列建index 過程：
下面列出用index,獲取query 比對(duì)位置過程
一些補(bǔ)充問題：
