算法帮助！ 使用其伙伴搜索字符串的快速算法
我正在寻找一个快速的搜索目的算法用于一个巨大的字符串（它是一个由数亿到数十亿个字符组成的生物基因组序列）。
此字符串中只有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
结果应该是
-
“ATCAG”配对“CTGAT”
-
“TCAG”配对“CTGA”
提前致谢。
更新：我已经有了确定两个字符串是否可以相互配对的方法。 唯一的问题是进行详尽的搜索是非常耗时的。
我认为这是一个有趣的问题，所以我把一个基于考虑’折叠’的程序放在一起，它向外扫描可能来自不同“折叠点”的对称匹配。 如果N是核苷酸数且M是’maxInterval-minInterval’，则应该有运行时间O（N * M）。 我可能已经错过了一些边界情况，因此请小心使用代码，但它确实适用于提供的示例。 请注意，我使用了填充的中间缓冲区来存储基因组，因为这减少了内环中所需的边界情况的比较次数; 这会换掉额外的内存分配以获得更好的速度。 如果您进行任何更正或改进，请随时编辑该post。
class Program { public sealed class Pairing { public int Index { get; private set; } public int Length { get; private set; } public int Offset { get; private set; } public Pairing(int index, int length, int offset) { Index = index; Length = length; Offset = offset; } } public static IEnumerable FindPairings(string genome, int minLen, int maxLen, int intervalMinLen, int intervalMaxLen) { int n = genome.Length; var padding = new string((char)0, maxLen); var padded = string.Concat(padding, genome, padding); int start = (intervalMinLen + minLen)/2 + maxLen; int end = n - (intervalMinLen + minLen)/2 + maxLen; //Consider 'fold locations' along the genome for (int i=start; i= minLen && matchLength <= maxLen) { yield return new Pairing(ik - maxLen, matchLength, 2*k - (matchLength-1)); } k++; } k++; } //Consider 'even' folding (centered before index) about index i k = (intervalMinLen+1)/2; while (k <= maxK) { int matchLength = 0; while (IsPaired(padded[i - (k+1)], padded[i + k]) && (k<=maxK+maxLen)) { matchLength++; if (matchLength >= minLen && matchLength <= maxLen) { yield return new Pairing(i - (k+1) - maxLen, matchLength, 2*k + 1 - (matchLength-1)); } k++; } k++; } } } private const int SumAT = 'A' + 'T'; private const int SumGC = 'G' + 'C'; private static bool IsPaired(char a, char b) { return (a + b) == SumAT || (a + b) == SumGC; } static void Main(string[] args) { string genome = "ATCAGGACCATACGCCTGAT"; foreach (var pairing in FindPairings(genome, 4, 5, 9, 10)) { Console.WriteLine("'{0}' pair with '{1}'", genome.Substring(pairing.Index, pairing.Length), genome.Substring(pairing.Index + pairing.Offset, pairing.Length)); } Console.ReadKey(); } } 我知道你不是在寻找子串，但我认为创建一个包含匹配的反向基因组串可能是值得的; 那么任务就是在两个字符串中找到共同的子串。
例：
原始字符串
ATCAG GACCA TACGC CTGAT
反转字符串：
TAGTC CGCAT ACCAG GACTA
如果你然后将字符串转换为它的配对值（替换T < - > A和C < - > G，你会得到一些有用的东西：
ATCAG GCGTA TGGTC CTGAT
我知道这种预处理成本很高并且占用了大量空间，但是之后您将能够使用标准字符串算法，并且通过您正在搜索的比较量，它肯定会被修改。
当原始字符串和反向查找字符串我认为你的问题听起来与’ 最常见的子串 ‘问题非常相似，这个问题已得到很好的描述。 您的第二个预处理是构造后缀树以允许快速查找子字符串。
你最终会得到二次运行时间，但我怀疑你能做得更好
最简单的解决方案是从最大高度maxLen的数据构造Trie。 每个节点还应该有一个找到该特定字符串的位置列表（如果按顺序创建trie，它将按升序排列）。
然后，在搜索时，只需反向补充搜索字符串并通过trie。 当您找到匹配项时，检查其中一个匹配项是否位于适当的时间间隔内，如果为“是”，则输出字符串。
如果您需要详细的算法，请告诉我。
该方法在http://www.ncbi.nlm.nih.gov/pubmed/11381028中描述
Genome Res。 2001年6月; 11（6）：1005-17。 细分重复：当前人类基因组计划组装中的组织和影响。
我考虑将字符串转换为16位长度的二进制：
A = 101
T = 010
C = 110
G = 001
每16位单元最多允许5个字符。 与字符串搜索和比较相比，这应该非常快。
使用最高位确定它是4序列单元还是5序列单元。
现在您可以快速排序并将所有4个序列和5个序列单元放入它们自己的组中（除非您需要找到与5个序列单元部分匹配的4个序列单元）。
为了进行比较，你可以再次排序，你会发现所有以G开头的序列都会出现在以T开头的序列之前，然后是A然后是C.然后你可以把一个序列与它的各个部分进行比较。排序的数组是可能的 – 这应该是一个更短，更短的问题空间。
此外，我为序列选择了这三位编码的原因是你可以简单地将两个字符串xor一起查看它们是否匹配。 如果按顺序得到15个1，那么两者完全匹配。 如果没有，那么他们没有。
你必须找出反平行位 – 我对此有一些想法，但这应该让你开始，如果anit-parallel部分成为一个问题，请问另一个问题。