參考：
踏踏實(shí)實(shí)做技術(shù)：BWA排惨，Bowtie弱卡，Bowtie2的比對(duì)算法推導(dǎo)
mapping pipline
remove multiple mapping reads的方法
CHIP-seq: Bowtie2遥倦、BWA用的比較多
RNA-seq: Tophat囊蓝、Bsmap
甲基化：BS-seeker
其中BWA & Bowtie & Bowtie2軟件均是基于BWT算法
二代測(cè)序的特點(diǎn)：
1. 短 250bp
2. 相對(duì)較高的精度 1% = Q30（不懂）
三代測(cè)序的特點(diǎn)：
1. 長(zhǎng)抖拦，有structure variation (這也是為什么要做三代測(cè)序算法開(kāi)發(fā)的原因之一)
2. 不穩(wěn)定
1. pairwise alignment
global---NW
local--SW
1. backtrack算法：
$ bwa aln genome read1.fq > aln_sa1.sai
$ bwa aln genome read2.fq > aln_sa2.sai
$ bwa samse genome aln_sa1.sai read1.fq > aln_se.sam
$ bwa sampe genome aln_sa1.sai aln_sa2.sai read1.fq read2.fq > aln_pe.sam
2. 比對(duì)算法原理：
BWT算法
Seq1
Seq2
兩條序列比對(duì)：pairwise alignment方法
全局比對(duì)：NM算法 局部比對(duì)：SW算法
3. 比對(duì)到reference基因組的方法：
1)在seq中取出一個(gè)較小的seed(30bp?)
2)通過(guò)seed找到ref的index,通過(guò)index去和附近的序列做pairwise比對(duì)
3)通過(guò)seed找ref的index的過(guò)程有兩個(gè)算法（短序列比對(duì)到基因組）
- 華大SOAP久又，MAQ。將基因組打斷成小段励两，將位置和序列存成HASH字典黎茎。
- BWA，bowtie算法当悔。解決速度問(wèn)題傅瞻。
BWT算法：
raw:ACAACG 添加$
M矩陣：
ACAACG$ 平移
$ACAACG
G$ACAAC
CG$ACAA
ACG$ACA
AACG$AC
CAACG$A
M首字母進(jìn)行排序
T矩陣：
$ACAACG
AACG$AC
ACAACG$
ACG$ACA
CAACG$A
CG$ACAA
G$ACAAC
T矩陣第一列為F列,最后一列為L(zhǎng)列
F列： $AAACCG
L列： GC$AAAC
關(guān)系：對(duì)應(yīng)L是F的前一個(gè)。L排序得到F盲憎。單字母相對(duì)位置不變（L中的第一個(gè)C對(duì)應(yīng)F第一個(gè)C嗅骄，以此類(lèi)推。）
保留L和L中每一個(gè)字母的相對(duì)位置饼疙，1.L可以推出F溺森。2.根據(jù)L、F相對(duì)位置可以還原ref
好處是能夠窮舉出所有的比對(duì)情況窑眯，所以可以選擇全局最優(yōu)的結(jié)果屏积；最大的缺點(diǎn)是比對(duì)的非常慢。
2.將query seq打斷成seed磅甩，比對(duì)ref index經(jīng)歷了兩代算法
1. 第一代：華大基因--SOAP MAQ # 缺點(diǎn)是內(nèi)存占用大肾请，慢，但是找的準(zhǔn)
2. 第二代：BWA更胖，Bowtie铛铁，Bowtie2 # 解決了速度慢的問(wèn)題
3.BWT 最初用于數(shù)據(jù)壓縮
BWT（Burrows-Wheeler Transform ）
假設(shè)原始的序列是
（1）Raw ACAACG # 壓縮后能還原，且比對(duì)次數(shù)盡可能少
第一步却妨，在raw seq中加$符號(hào)饵逐，并平移，形成一個(gè) raw matrix
第二步彪标，根據(jù)Raw Matrix的首字母進(jìn)行排序倍权，得到轉(zhuǎn)換矩陣Matrix’，默認(rèn)$符號(hào)排在第一位，
第一列為First 列薄声，F(xiàn)列
最后一列為L(zhǎng)ast列当船，L列
F和L的關(guān)系
- F是L的前面一列；
- 對(duì)L拍完序以后就是F默辨；
- 單字母的相對(duì)位置不變
所以最后只用保存L列和每個(gè)字母的相對(duì)位置就可以了德频，根據(jù)L列和每個(gè)字母的相對(duì)位置可以干兩件事情：
- 推出F列
- 根據(jù)L和F列的相對(duì)位置可以完整地還原ref相對(duì)位置
例如：第一個(gè)是L-對(duì)應(yīng)F-
的前一個(gè)是G缩幸，L-G對(duì)應(yīng)F-G壹置；F-G的前一個(gè)是L-C，依次類(lèi)推表谊，得到原來(lái)的ref：ACAACG$
bowtie和bowtie2兩個(gè)版本之間的區(qū)別--gap
1. bowtie/BWA # bowtie只允許mismatch钞护，不允許gap；BWA都允許
2. 用bowtie的話是看不到gap open的
bowtie1 不支持gap open
14bp（high quality）---14bp（low quality of high quality）--8bp（real low quality）
分成三斷seed爆办，seed1+seed2比對(duì)總共的mismatch <= 2难咕，則繼續(xù)8bp的比對(duì)；如果 > 2 直接放棄后面的比對(duì)距辆；
bowtie2 支持gap open
第一步步藕，選擇seed區(qū)域；
20里面選18---
（18+2）+（18+2）+（18+2）+...+(18+2)
保證一個(gè)fragment是20挑格，seed 是18bp
或者，10里面選16--
fragment = 16沾歪，overlap = 6漂彤，
那么根據(jù)BWT算法，就把拆分的seed mapping到基因組的大概位置灾搏；
然后把基因組可能mapping上的那段區(qū)域挑出來(lái)挫望，和query seq做比對(duì)（用NW或者SW算法），因?yàn)閝uery seq NW和SW允許gap open
注意
根據(jù)gap或者reads quality罰分得到MAPQ狂窑，當(dāng)MAPQ高于一個(gè)閾值是認(rèn)為可以比對(duì)上的媳板，低于閾值就認(rèn)為比對(duì)不上，那如果有20個(gè)高于閾值的就認(rèn)為有20個(gè)比對(duì)結(jié)果泉哈。
unique map
1）只有一個(gè)seq map上
2）只有一段MAPQ特別高蛉幸，其他的MAPQ特別小，
這兩種情況認(rèn)為是unique map
只有一個(gè)map的結(jié)果怎么處理丛晦；
