c# - 算法求助!与伙伴一起搜索字符串的快速算法

Question

我正在寻找一种用于在巨大字符串中进行搜索的快速算法(它是由数亿到数十亿个字符组成的生物基因组序列)。

此字符串中只有 4 个字符 {A,C,G,T}，并且“A”只能与“T”配对，而“C”只能与“G”配对。

现在我正在搜索两个可以反平行配对的子串(两个子串的长度限制在 {minLen, maxLen} 之间，间隔长度在 {intervalMinLen, intervalMaxLen} 之间)。

例如，字符串是:ATCAG GACCA TACGC CTGAT

约束:minLen = 4，maxLen = 5，intervalMinLen = 9，intervalMaxLen = 10

结果应该是

1. “ATCAG”与“CTGAT”配对

2. “TCAG”与“CTGA”配对

提前致谢。

更新:我已经有了判断两个字符串是否可以配对的方法。唯一担心的是进行详尽搜索非常耗时。

Answer 1

我知道您不是在搜索子字符串，但我认为创建一个包含匹配项的反向基因组字符串可能是值得的；然后任务就是在两个字符串中找到共同的子字符串。

例子:

原始字符串

  ATCAG GACCA TACGC CTGAT

反转字符串:

  TAGTC CGCAT ACCAG GACTA

如果您随后将字符串转换为它的配对值(替换 T<->A 和 C<->G，您会得到一些有用的东西:

  ATCAG GCGTA TGGTC CTGAT

我知道这种预处理的成本很高，而且会占用大量空间，但之后您将能够使用标准字符串算法，并且根据您正在搜索的比较量，这肯定是合理的。

当原始字符串和反向查找字符串时，我认为您的问题听起来与'longest common substring 惊人地相似。 ' 问题得到了很好的描述。您的第二个预处理是构建一个后缀树以允许快速查找子字符串。

你最终会得到二次运行时间，但我怀疑你能做得更好