計算兩個序列之間相似性的複雜性

Question

計算兩個序列之間相似性的最佳已知算法（如DNA或蛋白質比對/近似串匹配）的計算複雜度是多少？

的相似性基於：

1. 得分使用對準substitution scoring matrices（用於Protein alphabet 20個碼元的全局或位置特異性取代或在DNA字母表4個符號）

2. Gap Penalty

線性時間Burrows–Wheeler transform用於Bowtie和BWA短讀取對齊器實際的最新技術或有亞線性算法解決同樣的問題？

[編輯]：將LSH爲將次線性假設引用數據集

Answer 1

我想在一些點你最終讀取整個序列，以便不能有一個的預處理/索引近似匹配的思維亞線性時間算法。