最近對(duì)分析流程里用的bwa和mutect2的原理感興趣，打算稍微了解下。說起來本科時(shí)候也學(xué)過一些經(jīng)典算法，印象最深刻的就是NW全局比對(duì)和SW局部比對(duì)了。當(dāng)時(shí)老師是正好抽到我的代碼作業(yè)，好像我是有個(gè)回溯沒整出來，最后得個(gè)70分。就是工作后發(fā)現(xiàn)這東西壓根用不上。（而且講真，如果精于算法和統(tǒng)計(jì)的話，生統(tǒng)和算法工程師，待遇和發(fā)展上都比生信強(qiáng)。）總之業(yè)余選手一名，如有謬誤還請(qǐng)指出。
BWT算法的作用，是使字符串中相同字母臨近，便于后續(xù)壓縮。
而平時(shí)用到最多的bwa-mem比對(duì)，其實(shí)是在逆向解碼的過程。
首先，假定要處理序列為 ACAACG，將序列末尾補(bǔ)上$
即：ACAACG$
迭代將字符串的首字符，移到末尾，直到$到達(dá)首位。最終得到原始的矩陣如下（也有說將末尾字符移到首位的，這個(gè)其實(shí)不影響）。
現(xiàn)在，我們先不管原始矩陣排序的事，取出原始矩陣中的首列（F列）和尾列（L列），可以得出以下信息：
第一行：$后的字符為A，這個(gè)A是所在F列中的第一個(gè)A
第二行： A在字符C前，A是所在L列中的第一個(gè)A，C是所在F列中的第一個(gè)C
第三行：C在字符A前，C是所在L列中的第一個(gè)C，A是所在F列中的第二個(gè)A，
第四行：A在字符A前，一個(gè)A是所在L列中的第二個(gè)A，另一個(gè)A是所在F列中的第三個(gè)A
第五行：A在字符C前，A是所在L列中的第三個(gè)A，C是所在F列中第二個(gè)C
第六行：C在字符G前，C是所在L列中第二個(gè)C，G是所在F列中第一個(gè)G
第七行：G在字符$前,G是所在L列中第一個(gè)G
而顯然F列與L列在刪去$后完全相同，也就是說L列中的第n個(gè)A/T/C/G就是F列中的第n個(gè)A/T/C/G。
顯然，根據(jù)這些信息，可以反推出原始序列為 ACAACG。
現(xiàn)在，我們將原始矩陣每行按字典排序
同理，當(dāng)然也可以推出原始序列。
已知對(duì)每行來說，L列的字符都在F列的前面。則從F列的結(jié)尾字符$開始回溯（見下圖綠框）。
得到 $ ->G->C->A->A->C->A->$，即ACAACG
只是這時(shí)候有一個(gè)我也不了解的問題，顯然上述成立要求是——在字典排序后，L列中的第n個(gè)A/T/C/G就是F列中的第n個(gè)A/T/C/G，但這一論點(diǎn)，要如何證明成立？只能說，這可能是字典排序的特性？不確定的事我就不亂說了哎。
