Small typo in WFA paper

[RagnarGrootKoerkamp]

We're getting into very nitpicky things now, but I noticed this, and who knows, maybe you can still fix it for some future version :smile: :

• Equation 3 in the WFA paper is missing some commas in the 2nd line, in the maximum for M^{lo}.
• Edit: thinking more about it, maybe the max in that line should be min instead?
• The pseudocode has $\widetilde M$ while the text has $\tilde M$.

[smarco]

Hi, Ragnar.

Thanks for your comments. Obviously, I cannot easily change them in the published version, but I can change them in my latex version and upload them to Github.

Equation 3 in the WFA paper is missing some commas in the 2nd line, in the maximum for M^{lo}.

Surprisingly, these commas appear in my version (not in the editorial version, though).

Edit: thinking more about it, maybe the max in that line should be min instead?

That is correct. Following the implementation, it should be a min.

The pseudocode has ...

I never understood what happened there. In my latex, all were $\widetilde{M}$. Something got really wrong during the final editorial step.

Anyway, thanks for the corrections.

[ksahlin]

To continue the nitpicking.

In Algorithm 1, function header, I'm guessing it should be WF_ALIGN(q,t,p), i.e. lowercase p where it is the set of penalties. Also, the WF_NEXT function call and header should ideally have p as an argument.

In Algorithm 2 in the WFA paper, it should probably be while q[v] == t[h] (p is undefined in this context).

(I'm posting partly for documentation purposes but also to catch any misunderstandings I may have.)

[RagnarGrootKoerkamp]

In that case, p (or o/e/x) should probably be passed to WF_NEXT as well, since currently algorithm 1 does not actually use p.

[ksahlin]

First, I like to point out that WFA is a beautiful algorithm. Glad that I finally have some time to learn it in depth. Since this is an influential algorithm, it's important to get the details right if presented in other materials such as lectures etc.

Now that said. I have some further questions and comments on Algorithm 4 in the WFA paper for pruning the search.

1. $left_v = |p| - (offset -k)$. I assume this should be $left_v = |q| - (offset -k)$
2. $distance_k$, I assume this should be $d_k$ defined on the row above.
3. Does $\widetilde{M}^{lo}$ and $\widetilde{M}^{hi}$ mean the global highest and lowest offsets over all $s$? Because these offset pointers sometimes are treated individually for each $s$, e.g. in Eq 3?
4. When parsing algorithm 4 it is not immediately clear (to me) what $offset$ is in this function, could it be expressed from quantities defined in the function? I assume the for loop containing the $offset$-variable computes the number of vertical and horisontal steps to the 'end of the rectangle', respectively, and take the maximum of them. This is then the distance for the given point 'on the wave' to the end cell.
5. Are each $dk$ stored (e.g. in a vector) once computed in the for loop? I have this question because I wonder how the $d{\widetilde{M}^{lo}}$ and $d_{\widetilde{M}^{hi}}$) are retrieved later in the while loop for pruning.

[smarco]

This ticket should be open. Thanks for your comments @ksahlin. Let me address these questions/comments as soon as possible.