我正在寻找一种用于在巨大字符串中进行搜索的快速算法（它是由数亿到数十亿个字符组成的生物体基因组序列）。
该字符串中仅存在 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”配对
提前致谢。
更新：我已经有了确定两个字符串是否可以相互配对的方法。唯一的问题是进行详尽的搜索非常耗时。
我知道您不是在搜索子字符串，但我认为创建一个包含匹配项的反向基因组字符串可能是值得的；那么任务就是找到两个字符串中的公共子字符串。
Example:
原字符串
ATCAG GACCA TACGC CTGAT
反转字符串：
TAGTC CGCAT ACCAG GACTA
如果您随后将字符串转换为它的配对值（替换 TA 和 CG，您会得到一些有用的东西：
ATCAG GCGTA TGGTC CTGAT
我知道这种预处理成本高昂并且消耗大量空间，但是之后您将能够使用标准字符串算法，并且根据您正在搜索的比较量，这当然是合理的。
当原始字符串和反向查找字符串时，我认为你的问题听起来与 '最长公共子串 http://en.m.wikipedia.org/wiki/Longest_common_substring_problem' 问题描述得很好。第二个预处理是构建一个后缀树以允许快速查找子字符串。
你最终会得到二次的运行时间，但我怀疑你能做得更好
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
