Hi,
I'm reading your paper, but I have some questions.
Firstly, do I understand correctly that your algorithm fills the complete $n\times m$ DP table, and hence has quadratic $O(n^2)$ complexity? (This won't matter too much for short sequences, but I would like to understand the underlying algorithms.)
You define GCUPS as 'billion cell updates per second'. How do you compute this for e.g. Edlib, which does not fill the entire DP matrix but uses the banded algorithm of Ukkonen'85.
In the supplement, you also use TCUPS and TCPUS (probably a typo), but still use billion cell updates per second. This seems inconsistent.
Hi,
I'm reading your paper, but I have some questions.
Firstly, do I understand correctly that your algorithm fills the complete$n\times m$ DP table, and hence has quadratic $O(n^2)$ complexity? (This won't matter too much for short sequences, but I would like to understand the underlying algorithms.)
You define GCUPS as 'billion cell updates per second'. How do you compute this for e.g. Edlib, which does not fill the entire DP matrix but uses the banded algorithm of Ukkonen'85.
In the supplement, you also use TCUPS and TCPUS (probably a typo), but still use billion cell updates per second. This seems inconsistent.