Task 5 of 6

Traceback: What Did It Actually Align?

A score is a number; a biologist wants the alignment. That means walking backwards from the best cell, asking at each step which of the three candidates won here, until the score drops to 0 and the local alignment began.

The walk itself is hopelessly serial — one cell at a time, and the path is only as long as the alignment. Putting it on a GPU would be silly. But the question it asks at every step is embarrassingly parallel: "which predecessor explains this cell?" has the same answer whenever you ask it, so compute the answer for all 90 cells in one launch and store it. A pointer matrix — 1 for diagonal, 2 for up, 3 for left, 0 for "stop here" — is what every real aligner keeps beside the scores for exactly this reason.

Knowing what not to move onto the GPU is part of the craft. The fill is |A| × |B| cells of work; the walk is a few dozen steps of pointer chasing that finishes before a kernel launch would have been scheduled.

Goal: write the pointer kernel. Every cell reports which of its three predecessors produced its score, or 0 if the score is 0 and the alignment starts there.

Requirements

A cell whose score is 0 returns 0 — that is where the walk stops, and it also keeps the boundary safe
Return 1 when H[i][j] equals H[i - 1][j - 1] + s
Return 2 when it equals H[i - 1][j] - gap, and 3 otherwise
Test the candidates in that order, so ties prefer the diagonal

Hint 1 — the stop test comes first

Not just because the walk needs it: row 0 and column 0 hold zeros, and putting the test first means those threads return before they ever look at a[i - 1].

if (H[i][j] === 0) return 0;

Hint 2 — comparing scores for equality is safe here

Every score in this matrix is a whole number — match, mismatch and gap are all integers — so === between two of them is exact on every backend. That is a property of this scoring scheme, not a general licence: with fractional weights you would compare against a tolerance instead.

Hint 3 — the whole body

if (H[i][j] === 0) return 0;
let s = this.constants.mismatch;
if (a[i - 1] === b[j - 1]) s = this.constants.match;
if (H[i][j] === H[i - 1][j - 1] + s) return 1;
if (H[i][j] === H[i - 1][j] - this.constants.gap) return 2;
return 3;

Same idea elsewhere

Storing a decision alongside a value so the reconstruction is cheap is the standard move in every parallel dynamic program — the same reason a CUDA Viterbi decoder writes a backpointer array and a GPU video encoder writes mode decisions. The serial tail stays on the host, and the honest question on every platform is not "can this run on the GPU" but "is this the part worth moving".

All tasks in Wavefronts: Aligning DNA on the Diagonal

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.