I think the article is talking about the "full fledged" problem, while the computation you talk about could be using a set of optimizations aimed particularly a

I think the article is talking about the "full fledged" problem, while the computation you talk about could be using a set of optimizations aimed particularly at base-pair edit distance problem. For example, I could assume that there no deletions and insertions, only changes and then the problem becomes embarrasingly paralell and extremely easy to express in assembly-like operations. So I could paralellize it on a GPU by splitting the string into fixed length substrings and get huge gains. Problem is, can it be safely assumed that there are no deletions and insertions? Wikipedia has a list with some modifications that can also be used to speedup the calculation under certain constraints: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm#Possible_modifications https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...