2.2 基于前/后缀树的索引方法

    后缀树是一种重要的数据结构，AVID、MUMmer、MUMmer等序列比对算法都是基于后缀树的这个结构，但与两序列相似性比对时用于寻找最大公共子序列不同，read在参考序列中mapping时，是将read或其子序列在按序排列的所有后缀中一一比对找到匹配位置。算法VCAKE、SSAKE、SHARCGS、BWA-SW应用前缀树数据结构，它将序列所有的前缀用树的结构表示，原理与后缀树相同。如图3所示为序列S=GATGAC的前缀树和前缀DAWG (DirectedAcyclic Word Graph，有向无环词图)。

    由于后缀树结构在比对大型序列时，空间占用比较大，Abouelhoda等改进了Manber和My-ers提出的后缀树存储方法，称为增强后缀数组来提高空间利用率。Ferragina和Manzini提出的FM (full-text minute-space)-indexc是一种基于BWT (burrows-wheeler transform)的全文本压缩索引结构 ......