bwt算法是一种压缩算法，在生物信息学中，被用作序列比对，其中bwa中就有所应用。算法主要步骤可以分为编码和解码两步。
编码
假如我们现在有一个长度为6的序列AGCCAT
- 将标识符
#放置序列末尾，然后从末尾拿一位放到第一位，如此重复7次（序列的长度 + 1）就可以产生一个7*7的字母矩阵（下图左） - 选取标识符位于第一位的一行，并将其放到第一行，剩余的按照字典顺序（A>B>C>D ...）进行排序放置（下图右）
- 将第一列作为F（first）列，最后一列作为L（last）列，只需要保留F和L两列即可（如下图）
- L列第一个元素是原始序列
AGCCAT的最后一个元素 - 每一行中，F列元素是L列元素的下一个元素，（「T->#」 、「C->A」、「C->C」、「G->C」、「A->G」）
- L列中每个元素的相对位置与F列中对应元素的相对位置具有对应关系（L列中从上往下数第一个T对应于F列中从上往下数的第一个T）
解码
解码时
- 先从根据F列找到同一行的L列元素，根据L列元素在L列的相对位置，去找对应的F列对应相对位置的元素（比如，第一列为**#->T**，T在L列是第一个T，那么去F列找第一个T）
- 找到F列的元素后，在去找同一行的L列元素，根据L列元素在L列的相对位置，再去找F列中对应相对位置的元素（比如，「T->A」，A在L列是第二个，那么去找F列的第二个A，可以得到「A->C」）
- 重复2过程，即可将原来的序列复原（在找的过程中是先找序列中最后一个，所以找的时候需要倒着写）
序列比对
讲完了编码和解码，那么BWT算法是怎么来进行比对的呢？比如这里有AGC和CAT两条序列，那么下面讲解如何使用BWT将他们比对到我们的AGCCAT中。
从上面的解码过程可以发现，我们的解码过程是从最后一位，根据F和L列的关系开始解码，即从后向前进行解码，所以比对的时候，我们也需要从后向前进行比对。
CAT
首先在F列找到T，与T同一行的为A，A在第L列中为第二个，所以找F列中第二个A对应L列为C，至此，我们找到了一条「T->A->C」的路径，这条路径就是我们需要比对的「CAT」比对结束。
AGC
对于AGC来讲，会有两个结果，因为最后一个元素为「C」，而C在F列中有两个，所以会有两条路径，使用和上面相同的方法可以得到：
- 对于第一个C：「C->C->G」
- 对于第二个C：「C->G->A」
很明显，我们发现「AGC」可以比对到从第二个C出发的路径上。
总结
BWT由于F列和L列之间的关系（L列的元素后面的那个元素是F列），使得我们的比对过程变成了寻找符合条件的路径的问题。
