后缀树系列三:后缀树的应用

  • A+
所属分类:生物信息学

前面两篇转载的后缀树系列文章已经描述了后缀树的线性构建算法。创建后缀树的O(n)算法,除了1995年E. Ukkonen大幅简化的算法,还有Peter Weiner的73年年度最佳算法、Edward McCreight1976的改进算法、Juha Kärkkäinen 和 Peter Sanders2003年进一步简化的线性算法,可以根据自己喜好选择。
转载的本系列文章应该预设有第三篇的(后缀树应用),但是没找到,那就自己总结一下吧。
先扩展一下后缀树的概念:广义后缀树(Generalized Suffix Tree)。传统的后缀树处理一坨单词的所有后缀。广义后缀树存储任意多个单词的所有后缀。注意我们需要区分不同单词的后缀,所以叶节点用不同的特殊符号与后缀位置配对。

主要应用场景

1. 查找字符串 Pattern 是否在于字符串 Text 中(生信中的exact string matching)

解决方案:用 Text 构造后缀树,按在 Trie 中搜索字串的方法搜索 Pattern 即可。若 Pattern 在 Text 中,则 Pattern 必然是 Text 的某个后缀的前缀。 采用后缀树的方法,其总的计算复杂度并不劣于KMP等经典方法,可以作为重要的替代方法。此外更重要应用场景如下: Exact set matching problem(多个子串的情况); The substring problem for database of patterns(多个母串的情况)。

2. 计算指定字符串 Pattern 在字符串 Text 中的出现次数

解决方案:用 Text+`$` 构造后缀树,搜索 Pattern 所在节点下的叶节点数目即为重复次数。如果 Pattern 在 Text 中重复了 c 次,则 Text 应有 c 个后缀以 Pattern 为前缀。

3. 查找字符串 Text 中的最长重复子串

解决方案:用 Text+`$` 构造后缀树,搜索 后缀树中最深的非叶节点。从 root 到该节点所经历过的字符串就是最长重复子串。

4. 查找两个字符串 Text1 和 Text2 的最长公共部分(即Lowest Common Ancestor)

解决方案:连接 Text1+`#` + Text2+`$` 形成新的字符串并构造后缀树,找到最深的非叶节点,且该节点的叶节点既有 `#` 也有 `$`。 另外,这个可以从两个推广到多个字符串。 查找LCA的算法是O(1)的复杂度,代价是需要对后缀树做复杂度为O(n)的预处理。 曾记得以前学过树结构的LCA各种算法,比如Tarjan算法(DFS+并查集,离线)、RMQ(时间戳,在线)、树链剖分等,年代久远,这些东西都记不清楚了T_T。 此外,还有一种二进制树检索LCA的方法,用二进制的每一位表示路径方向,0表示左儿子,1表示右儿子。只需将需要比较的两个节点的二进制值进行XOR计算,即可得知二者重叠的路径(根据XOR的定义知,左边连续的0右多少个,则有多少重叠)。将任意后缀树mapping到二进制树中,即可快速地检索出LCA。(关于二进制树,具体请参考*Algorithms on Strings, Trees and Sequences* 一书)

5. 查找给定字符串 Text 里的最长回文(palindrome in DNA or RNA)

解决方案:将 Text 整体反转形成新的字符串 Text2,例如 "abcdefgfed" => "defgfedcba"。连接 Text+`#` + Text2+`$` 形成新的字符串并构造后缀树,然后将问题转变为查找 Text 和 Text1 的最长公共部分。 注意,DNA或RNA中回文的定义略有区别。

6. 识别DNA污染问题

定义:给定一个新测序的DNA序列S1和一个来自可能的污染物的DNA序列S2, 发现S2中所有出现在S1中且长度超过给定阈值x的子串,如果S2中的某个子串出现在S1中, S1可能已经被污染了。 解决方案:本质上是LCA问题的变种。

7. All-pairs suffix-prefix matching

定义:给定字符串Si和Sj,若Si的后缀与Sj的前缀匹配,则称suffix-prefix match。如果将两个字符串的问题,推广到多个字符串S1,S2,S3...Sk的情况,对于任意其中两个Si和Sj进行suffix-prefix match,其中最长的suffix-prefix match称为All-pairs suffix-prefix matching。 解决方案:可以在线性时间内解决,本人暂时未仔细阅读这个方法,请参考*Algorithms on Strings, Trees and Sequences* 一书。

8. Circular string linearization

定义:字符串S中的任意一个位置切断,而原先的首位相接,可以得到新的字符串。如何选择这个位置,使得新字符串的字典序最小。 解决方案:给定长度为n的字符串S,先复制成2倍长度变成SS,构建SS+`$` 的后缀树T,从T的根节点开始,每次顺着字典序最小的分支走下去,直至深度为n,得到的字符串对应的切割方案即为所求。

9. Suffix trees in genome-scale projects

一些基因工程里已经应用了后缀树的方法,比如Arabidopsis thaliana(拟南芥)、Yeast(酵母)、Borrelia burgdorferi(博氏疏螺旋体)等

其他应用场景

1. Longest common extension; 2. Finding all maximal palindrome in linear time; 3. Exact matching with wild cards(通配符); 4. The k-mismatch problem; 5. Approximate palindrome and repeats; 6. Faster methods for tandem repeats; 7. A linear-time solution to the multiple common substring problem.

空间优化

构建Directed Acyclic Word Graph,简称DAWG。具体请查看相关资料(比如*Algorithms on Strings, Trees and Sequences* 一书中就有章节讲述:Building a smaller directed graph for exact matching)。 *Algorithms on Strings, Trees and Sequences* 一书中还有几个空间优化的例子: A reverse role for suffix trees, and major space reduction; Space-efficient longest common substring algorithm; Suffix arrays——more space reduction.

其他

*Algorithms on Strings, Trees and Sequences* 一书中还提到了一些相关的知识。 1. Boyer-Moore如何解决exact set matching problem; 2. Ziv-Lempel 数据压缩; 3. Minimum length encoding of DNA.

推荐的参考资料

关于后缀树的讲解,还有一些不错的文章:
1. 后缀树 (该作者不允许转载。。)
2. 祥林嫂精神恍惚痛苦呼唤之关于Suffix Tree[后缀树] (图文可见
此博客 )

其他参考资料:

  • Pattern Searching | Set 8 (Suffix Tree Introduction)
  • 后缀树的构造方法-Ukkonen详解
  • Ukkonen’s Suffix Tree Construction – Part 1
  • Suffix Trees
  • Compressed Trie
  • Pattern Searching using a Trie of all Suffixes
  • Algorithms on Strings, Trees, and Sequences
  • C# Suffix tree implementation based on Ukkonen's algorithm
  • Ukkonen's suffix tree algorithm in plain English?
  • Ukkonen 的后缀树算法的清晰解释
  • Fast String Searching With Suffix Trees
  • Esko Ukkonen's Paper: On–line construction of suffix trees
  • Graphviz - Graph Visualization Software
  • a suffix tree algorithm for .NET written in C#