模式匹配(DNA大数据)中是否存在预先存在的高效算法?
有很多算法，如Knuth-Morris-Pratt算法，Boyer-Moore算法，基于索引的前向后向多模式算法，但它们效率很高，在较大时性能很差。所以请帮助我了解有效的算法在模式匹配…
看一下BLAST算法
我相信这一定在其他地方讨论过。
我猜你已经只使用两个比特来存储字符串了(而不是每个字符使用八个比特)。这不仅减少了四倍的存储大小(我猜你的字符串可以长达数亿个字符)，而且还减少了传输这些数据的时间(例如，从磁盘到内存或从内存到CPU缓存)。
下面假设有很多查询，而要搜索的字符串保持不变，因此基于字符串计算和存储一些额外的数量是合理的。
-
我建议你看看可以使用Ukkonen算法在线性时间内构建的后缀树。
-
如果这是不可行的，也许你应该考虑一种混合的方法，比如建立一个固定的集合字典，包含所有可能的单词，长度不超过固定的L，并将你的字符串划分为要搜索的区域。
- 为字典中的每个单词存储它们出现的区域索引(在构建此列表时包括下一个区域的L-1字符)
- 在搜索单词时，将其分割为长度为L的字符串，并检查这些字符串出现在哪些区域。假设最大搜索字符串长度不超过一个区域的长度，您的搜索字符串只能出现在搜索字符串的所有部分(长度为L)出现(或在前/后区域)的区域
- 使用标准字符串搜索算法，只搜索结果区域的搜索字符串(这可能类似于布鲁姆过滤器的作用)