algorithm - 用于在两个非常长的文本序列中查找唯一集的快速算法

Question

我需要比较 X 和 Y 染色体的 DNA 序列，并找到 Y 染色体特有的模式(由大约 50-75 个碱基对组成)。请注意，这些序列部分可以在染色体中重复。这需要快速完成(BLAST 需要 47 天，需要几个小时或更短时间)。有没有特别适合这种比较的算法或程序？同样，速度是这里的关键。

我把它放在 SO 上的一个原因是为了从特定应用程序领域之外的人那里获得观点，他们可以提出他们在日常使用中用于字符串比较的算法，这些算法可能适用于我们的使用。所以不要害羞!

Answer 1

1. 构建一个 suffix tree S 在序列 X 上。
2. 对于序列 Y 中的每个起始位置 i，在 S 中查找字符串 Y[i..i+75]。如果找不到从位置 i 开始的匹配项(即如果在 j < 75 个核苷酸匹配后查找失败)那么你已经找到了一个长度为 j 的字符串，对于 Y 是唯一的。
3. 所有起始位置 i 中最小的此类字符串是最短的唯一字符串(如果您对最小化长度不感兴趣，则在找到任何此类字符串后就停止)。

总时间:O(|X| + m|Y|)，其中 m 是最大字符串长度(例如 m = 75)。

可能还有更高效的基于广义后缀树的算法。