algorithm - 计算两个序列之间相似性的复杂性

Question

用于计算两个序列之间相似性的最著名算法的计算复杂度是多少（如在 DNA 或蛋白质比对/近似字符串匹配中）？

相似性基于：

1. 使用替换评分矩阵对对齐进行评分（用于蛋白质字母表中 20 个符号或 DNA 字母表中 4 个符号的全局或特定位置替换）

2. 差距罚球

Bowtie和BWA短读对齐器中使用的Burrows-Wheeler 变换的线性时间是实际最先进的，还是有解决相同问题的亚线性算法？

[编辑]：考虑应用LSH进行近似匹配，假设参考数据集的预处理/索引将是次线性的

Answer 1

我想在某些时候你最终会阅读整个序列，所以不可能有一个亚线性时间算法。