最近對分析流程里用的bwa和mutect2的原理感興趣抹沪，打算稍微了解下纵菌。說起來本科時候也學過一些經(jīng)典算法，印象最深刻的就是NW全局比對和SW局部比對了玄柠。當時老師是正好抽到我的代碼作業(yè)突梦，好像我是有個回溯沒整出來，最后得個70分羽利。就是工作后發(fā)現(xiàn)這東西壓根用不上宫患。（而且講真，如果精于算法和統(tǒng)計的話这弧，生統(tǒng)和算法工程師娃闲，待遇和發(fā)展上都比生信強虚汛。）總之業(yè)余選手一名，如有謬誤還請指出皇帮。
BWT算法的作用卷哩，是使字符串中相同字母臨近，便于后續(xù)壓縮属拾。
而平時用到最多的bwa-mem比對将谊，其實是在逆向解碼的過程。
首先渐白，假定要處理序列為 ACAACG尊浓，將序列末尾補上$
即：ACAACG$
迭代將字符串的首字符，移到末尾纯衍，直到$到達首位栋齿。最終得到原始的矩陣如下（也有說將末尾字符移到首位的，這個其實不影響）襟诸。
現(xiàn)在瓦堵，我們先不管原始矩陣排序的事，取出原始矩陣中的首列（F列）和尾列（L列）歌亲，可以得出以下信息：
第一行：$后的字符為A谷丸，這個A是所在F列中的第一個A
第二行： A在字符C前，A是所在L列中的第一個A应结，C是所在F列中的第一個C
第三行：C在字符A前，C是所在L列中的第一個C泉唁，A是所在F列中的第二個A鹅龄，
第四行：A在字符A前，一個A是所在L列中的第二個A亭畜，另一個A是所在F列中的第三個A
第五行：A在字符C前扮休，A是所在L列中的第三個A，C是所在F列中第二個C
第六行：C在字符G前拴鸵，C是所在L列中第二個C玷坠，G是所在F列中第一個G
第七行：G在字符$前,G是所在L列中第一個G
而顯然F列與L列在刪去$后完全相同，也就是說L列中的第n個A/T/C/G就是F列中的第n個A/T/C/G劲藐。
顯然八堡，根據(jù)這些信息，可以反推出原始序列為 ACAACG聘芜。
現(xiàn)在兄渺，我們將原始矩陣每行按字典排序
同理，當然也可以推出原始序列汰现。
已知對每行來說挂谍，L列的字符都在F列的前面叔壤。則從F列的結(jié)尾字符$開始回溯（見下圖綠框）。
得到 $ ->G->C->A->A->C->A->$口叙，即ACAACG
只是這時候有一個我也不了解的問題炼绘，顯然上述成立要求是——在字典排序后，L列中的第n個A/T/C/G就是F列中的第n個A/T/C/G妄田，但這一論點俺亮，要如何證明成立？只能說形庭，這可能是字典排序的特性铅辞？不確定的事我就不亂說了哎。
