簡(jiǎn)介
取得測(cè)序序列信息后，在有參考基因的情況下我們通過(guò)Mapping 到參考基因組進(jìn)行后續(xù)分析稀拐；沒(méi)有則重頭拼接序列火邓。
一般而言，基因組的組裝將比read alignment 消耗更多的計(jì)算資源德撬。然而铲咨，read alignment 也有一些基礎(chǔ)的挑戰(zhàn)。
- 參考基因組蜓洪，組裝不完整纤勒，存在一些gap快压。來(lái)源這些gap的read 將unmapped 或是 錯(cuò)誤map 到相似區(qū)域诅愚。
- 基因組存在重復(fù)區(qū)，reads 會(huì)map 到多個(gè)區(qū)域忘朝，比對(duì)軟件一般會(huì)隨機(jī)選擇一個(gè)區(qū)域恐仑。
- 比對(duì)軟件需要容忍read 和參考基因之間的差異（SNV泉坐、Indel）
Read Alignment
一般流程
read alignment 一般分三個(gè)步驟。
- 對(duì)參考基因組建立索引
- 利用index 找到read 在參考基因組的大致位置（一般有多個(gè)候選位置）
- 對(duì)read 和 參考基因組相關(guān)區(qū)域進(jìn)行pairwise alignment（SW菊霜、NW坚冀、漢明距離）
索引技術(shù)
Hashing 是最流行的參考基因組索引技術(shù)。
利用哈希表構(gòu)建短序列（seed鉴逞、K-mer）和參考基因組對(duì)應(yīng)位置的映射關(guān)系记某。在mapping 時(shí)，從read 中截取相應(yīng)長(zhǎng)度的seed 构捡，從哈希表中檢索到參考基因組位置列表（精確比對(duì)）液南。
后綴樹(shù)索引
基于后綴樹(shù)的索引，通常更快勾徽。后綴樹(shù)是一種樹(shù)型數(shù)據(jù)結(jié)構(gòu)滑凉，各個(gè)分支記錄了基因組不同的后綴，共有的前綴只會(huì)被記錄一次喘帚。
Pattern Searching using Suffix Tree - GeeksforGeeks
與哈希表索引不同畅姊，后綴樹(shù)索引能夠通過(guò)繞過(guò)某些node進(jìn)行非精確匹配。除了少量工具單獨(dú)使用后綴樹(shù)索引吹由，更多的工具采用BWT-FM 索引若未，來(lái)模擬后綴樹(shù)遍歷過(guò)程，同時(shí)可以減少內(nèi)存消耗倾鲫。
小結(jié)
基于Hashing 索引和BWT-FM索引的兩大類(lèi)方法粗合，在運(yùn)行效率上沒(méi)有明顯的差異。但是BWT-FM工具乌昔，對(duì)內(nèi)存的消耗更少（Hashing 是其3.8倍以上）隙疚。
確定Reads 基因組比對(duì)位置
大部分的工具采用定長(zhǎng)的seed來(lái)檢索到reads 在基因組上的位置。一般這種seed 定位到的基因組位置比較多（取決于seed大锌牡馈）供屉，大部分工具會(huì)采用啟發(fā)式算法，計(jì)算每個(gè)給定位置的分值溺蕉，設(shè)定檢測(cè)閾值贯卦，從而避免檢查seed 在基因組中出現(xiàn)的每一個(gè)位置。
提高seed長(zhǎng)度焙贷，能同時(shí)減少每條read的seed數(shù)量以及撵割，seed在基因組的位置數(shù)量。但是會(huì)降低比對(duì)的靈敏度（seed 越長(zhǎng)辙芍，對(duì)應(yīng)長(zhǎng)度的read 可以容納的錯(cuò)配數(shù)越低）啡彬。為了提高seed的長(zhǎng)度，同時(shí)不降低比對(duì)的靈敏度故硅，可以采用spaced seeds庶灿。
在比對(duì)過(guò)程中使用不同長(zhǎng)度的seed，可以提高錯(cuò)配的容忍度吃衅，一般稱(chēng)為hybrid seeding往踢。由于基于哈希表的索引方式，針對(duì)不同長(zhǎng)度的seed要建立多個(gè)hash tables徘层，會(huì)需要額外的計(jì)算資源峻呕，所以hybrid seeding 更多的是被BWT-FM索引工具采用利职。
Pairwise alignment
比對(duì)算法的最后一步就是計(jì)算，候選區(qū)域和reads 的實(shí)際相似程度瘦癌，選擇最佳的比對(duì)位置猪贪。
這一步的算法分為兩大類(lèi)，1. 基于動(dòng)態(tài)規(guī)劃的算法讯私；2.非動(dòng)態(tài)規(guī)劃類(lèi)算法热押。
動(dòng)態(tài)規(guī)劃類(lèi)算法(DP)主要是，局部比對(duì)算法Smith-Warterman斤寇、全局比對(duì)算法Needleman-Wunsch桶癣。
非動(dòng)態(tài)規(guī)劃類(lèi)算法(non-DP)：Hamming distance 、Rabin-Karp algorithm娘锁。
對(duì)indel感興趣的話牙寞，DP類(lèi)算法更好。也可以結(jié)合使用致盟。
長(zhǎng)讀長(zhǎng)reads 比對(duì)算法
隨著長(zhǎng)讀長(zhǎng)技術(shù)發(fā)展碎税，相應(yīng)也產(chǎn)生了對(duì)應(yīng)的比對(duì)工具。目前長(zhǎng)讀長(zhǎng)比對(duì)算法沿襲短讀長(zhǎng)算法的三步走方式馏锡。
有些算法甚至將長(zhǎng)讀長(zhǎng)的read切割成的短讀長(zhǎng)雷蹂，再分別進(jìn)行比對(duì)。長(zhǎng)讀長(zhǎng)算法要解決的主要問(wèn)題是杯道，較大的測(cè)序錯(cuò)誤和異常多的seed匪煌。所以現(xiàn)行的算法，要通過(guò)啟發(fā)式的方法從reads中截取比較少的seed 党巾。最近的算法從基因組區(qū)域內(nèi)的一組相鄰的種子中尋找種子的最小代表集萎庭，而不是為整個(gè)種子集創(chuàng)建一個(gè)哈希表，稱(chēng)為minimizers齿拂。使用這種技術(shù)可以提高比對(duì)效率驳规，降低準(zhǔn)確性。
RNA-Seq 比對(duì)算法
RNA-Seq比對(duì)的難點(diǎn)在于署海，這是spliced alignment吗购，需要解決的問(wèn)題是，reads 可能會(huì)跨越內(nèi)含子砸狞，存在一個(gè)大的gap捻勉。
Hashing 是RNA-Seq最常用的比對(duì)技術(shù)。
參考文獻(xiàn)
Alser, M., Rotman, J., Deshpande, D. et al. Technology dictates algorithms: recent developments in read alignment. Genome Biol 22, 249 (2021). https://doi.org/10.1186/s13059-021-02443-7
