假設(shè)當(dāng)前的堿基序列為 ref=ATTCCAGTCGGGTATCCAAGGACT，根據(jù)Burrows-Wheeler Transform（short read）文中的建立O表的方法，建立O表如下：

                                        (Table　O)
   ref   |A |T |T |C |C |A |G |T |C |G |G |G |T |A |T |C |C |A |A |G |G |A |C |T |
   pos   |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|23|
   ---------------------------------------------------------------------------------
    A    |1 |1 |1 |1 |1 |2 |2 |2 |2 |2 |2 |2 |2 |3 |3 |3 |3 |4 |5 |5 |5 |6 |6 |6 |
    T    |0 |1 |2 |2 |2 |2 |2 |3 |3 |3 |3 |3 |4 |4 |5 |5 |5 |5 |5 |5 |5 |5 |5 |6 |
    C    |0 |0 |0 |1 |2 |2 |2 |2 |3 |3 |3 |3 |3 |3 |3 |4 |5 |5 |5 |5 |5 |5 |6 |6 |
    G    |0 |0 |0 |0 |0 |0 |1 |1 |1 |2 |3 |4 |4 |4 |4 |4 |4 |4 |4 |5 |6 |6 |6 |6 |

當(dāng)堿基序列很長(zhǎng)時(shí)(如序列數(shù)據(jù)量大小達(dá)到G級(jí)別)，對(duì)于表中的０，１，２……這些數(shù)據(jù)在RAM中以32bits存儲(chǔ)，這樣要存儲(chǔ)一個(gè)ref的O表需要4x24x32/8 byte = 384 byte.

實(shí)際中，我們采用如下方法對(duì)Ｏ表進(jìn)行壓縮：

1.將ref拆分成8bits一組

拆分之后如下：
ref = ATTCCAGT | CGGGTATC | CAAGGACT
對(duì)于每一組，我們需要存儲(chǔ)的信息如下：
１．每組中的元素；
２．每組中最后一個(gè)元素對(duì)應(yīng)的O表中的內(nèi)容；

2.建立壓縮表

表頭數(shù)據(jù)為：

[|0|0|0|0|]

將第一組內(nèi)容放入壓縮表：

----表頭------A---T---T---C---C---A---G---T---O表在pos=7處的ATCG表中數(shù)據(jù)
[|0|0|0|0|][|100|111|111|101|101|100|110|111|][|2|3|2|1|]

note:

parameter Symbol sym_A= 3'b100;
parameter Symbol sym_C= 3'b101;
parameter Symbol sym_G= 3'b110;
parameter Symbol sym_T = 3'b111;

建立的完整壓縮表：

[|0|0|0|0|][|100|111|111|101|101|100|110|111|][|2|3|2|1|][|101|110|110|110|111|100|111|101|]\
[|3|5|4|4|][|101|100|100|110|110|100|110|101|][|6|6|6|6|]

這樣要存儲(chǔ)一個(gè)ref的O表需要4x4x32/8 + 3x24/8 byte = 73 byte.

對(duì)于長(zhǎng)度為8N的ref序列的O表，其壓縮比為：

origin:    4x8xNx32/8 byte = 128N byte
compress:  3x8xN/8 + (N+1)x4x32/8 byte = 19N + 16 byte 

當(dāng)N-->+∞時(shí)，壓縮比為19/128=14.84%

3.解壓

將壓縮表分塊，每塊大小為32x4+3x8=152bits.
分塊之后示意圖如下：

[|0|0|0|0|][|100|111|111|101|101|100|110|111|]
[|2|3|2|1|][|101|110|110|110|111|100|111|101|]
[|3|5|4|4|][|101|100|100|110|110|100|110|101|]
[|6|6|6|6|]

舉第一塊為例，解壓時(shí)根據(jù)[|0|0|0|0|]確定當(dāng)前O表中的A,T,C,G起始個(gè)數(shù)都為0，
再根據(jù)[|100|111|111|101|101|100|110|111|]可知當(dāng)前塊的元素為ATTCCAGT。
如第一個(gè)元素為A，即在O表的A部分設(shè)置值為base+1，即0+1=1，其余的T,C,G表中的值保持不變。
如第二個(gè)元素為T，即在O表的T部分設(shè)置值為base+1，即0+1=1，其余的A,C,G表中的值保持不變(A表中的值仍為１)。
……
從而將O表解壓出來(lái)。

Note:

在壓縮時(shí)引入這些塊頭數(shù)據(jù)([|0|0|0|0|],[|2|3|2|1|]……)是為了可以將壓縮后的O表分塊并行解壓，互不干擾，只要最后將解壓的數(shù)據(jù)再拼湊回來(lái)即可，提高了程序的并行性，可以加快解壓的計(jì)算速度。