8

输入：字符串 S = AAGATATGATAGGAT。

输出：最大重复，例如 GATA（如位置 3 和 8）、GAT（如位置 3、8 和 13）等等......

  • 最大重复是子串 t 在 S 中出现 k>1 次，如果 t 向左或向右扩展，它将出现少于 k 次。

  • 内部节点的叶子后代是后缀，每个后缀都有一个左字符。

  • 如果所有叶子后代的左字符不完全相同，则称为“左多样化”节点。

  • 最大重复是左多样化的内部节点。

总体思路：

  • 构建后缀树，然后在树上进行 DFS（深度优先搜索）

  • 对于每片叶子，用它的左边字符标记它

  • 对于每个内部节点：

  • 如果至少有一个孩子标有 *，则标有 *

  • 否则，如果其子标签多种多样，则使用 * 进行标签。

  • 否则所有孩子都有相同的标签，将其复制到当前节点

上述想法是否正确？伪代码如何？然后我可以尝试自己编写程序。

4

1 回答 1

3

你的想法很好，但是使用后缀树你可以做一些更简单的事情。

让 T 成为您的序列的后缀树。

设 x 是 T 中的一个节点，T_x 是 T 的根 x 的子树。

令 N_x 为 T_x 中的叶子数

让 word(x) 是通过从根到节点 x 遍历 T 创建的词

现在使用后缀树的定义，我们得到：

word(x) = N_x 的重复次数，这个词的位置就是每个叶子的标签

这个算法将是一个基本的树遍历，对于树中的每个节点计算 N_x，如果 N_x > 2 将其添加到您的结果中（如果您也想要位置，您可以添加每个叶子的标签）

伪代码：

输入 ：

我的序列

输出：

结果（以计数和位置重复的单词列表）

算法 ：

T = suffixTree(mySequence)

对于 T 中的每个内部节点 X：

  T_X = subTree(T)
  N_X = Number of lead (T_X)
  if N_X >=2 :
  Result .add ( [word(X), N_X , list(label of leafs)] )

返回结果

例子 ：

让我们以 wikipedia 的后缀树为例：“BANANA”：

在此处输入图像描述

我们得到：

N_A = 3 so "A" repeats 3 times in position {1,3,5}
N_N=2  so "N" repeats 2 times  in position {2,4}
N_NA=2  so "NA" repeats 2 times in position {2,4}

我发现这篇论文似乎以与您相同的方式处理您的问题，所以是的，我认为您的方法是 write ：

使用后缀树拼写近似重复或常见的主题

提炼

我们在本文中介绍了两种算法。第一个从在字母 Sigma 上定义的序列中提取重复的基序。例如，Sigma 可能等于 {A, C, G, T}，并且该序列代表 DNA 大分子的编码。搜索的主题对应于同一字母表中的单词，这些单词在序列中出现最少 q 次，每次最多有 e 个不匹配（q 称为 quorum 约束）。 [...]

您可以下载并查看它，作者为您的算法提供了伪代码。

希望这可以帮助

于 2011-10-14T11:40:01.850 回答