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

Question

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

我把它放在SO上的原因之一是从特定应用领域之外的人那里获得视角,他们可以提出他们在日常使用中用于字符串比较的算法,这可能适用于我们的使用.所以不要害羞!

Answer 1

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

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

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