Alignment — where it appears
Named by 15 essays across 5 fields — each of them below, with the objects they name alongside it.
A band as wide as the answer
If two strings are close, the optimal route stays near the diagonal and nine cells in ten cannot be on it. A band of three finds the right answer on a pair 300 characters long — and a band of thirty-two is needed before anything can prove it.
A cost that is not one
The same eighty-one cells, filled by the same recurrence, return 6, 10, 10 and 15 — in edits, in cost, in bits and in bits again. Only the first is a count of anything, two of them are equal by arithmetic coincidence, and the alignment each one chooses is different.
The zero that moves the answer out of the corner
One extra term in the recurrence — a floor at zero — and the answer stops being in the last cell. It becomes a maximum over all 1,040 of them, the traceback's starting point is a search, and the whole mode is meaningless unless a randomly matched pair of characters scores negative on average. That last condition is on the scoring scheme, not on the sequences.
A cell that has to know where it is
A gap of four characters is usually one event, not four. No recurrence over a single table can charge it that way, because the price of a gap character depends on how the cell above it was reached and a cell holding one number has thrown that away. The repair is three tables, and it costs exactly three times the cells.
A distance divided by a length is not a rate
Two substitutions turn "ab" into "ba", a distance of two over an alignment of two columns — a rate of 1.00. Deleting, matching and inserting also costs two, over three columns, for 0.67. Both are alignments of the same pair, the second has the better rate, and the optimal alignment is not the one that achieves it. Over every pair of strings up to three characters on three letters, 21% disagree.
A distance that is a path through a grid
How far apart two strings are is a shortest-path problem on a grid whose every edge is drawn by the recurrence — and finding a string in a text costs 4,988 character comparisons where measuring how far it is from one costs 96,000.
The alignment that fits in one line
Compute the table twice and hold three rows of it. The factor of two is a geometric series and is predicted exactly; measured, it comes down from 2.269 to 2.052 as the strings grow, and the peak is 3(m+1) cells on the nose.
The matrix a corpus wrote
A substitution matrix is not a property of an alphabet. Fit one to four hundred pairs of sequences that rarely change and the dearest substitution costs five; fit the same model to four hundred pairs that often change and it costs two. Two hundred test pairs aligned under each matrix give different alignments in 115 cases — and a matrix fitted to eight pairs of the first kind moves 79 of them, from sampling alone.
The row that starts at zero
The same 1,413 cells, filled by the same recurrence in the same order, answer 148 and 0. One line of initialisation decides which question the table was asked, and only one of the two answers is about whether the pattern is there.
The parameter plane has few answers
Sweep the cost of opening a gap against the cost of extending one over five hundred and seventy-six settings, and the optimal alignment of intention against execution takes four values — one of them at 571 of the settings. Under a linear model the plane divides into three wedges through the origin, because doubling every cost changes nothing and only the ratio is a parameter. Tuning an aligner is choosing a region, and most of the plane is one.
The ties a rounded matrix makes
Measure how far each optimal alignment is from a tie — the smallest change to any one cost that makes another alignment win — and it predicts which alignments a refitted substitution matrix will move. A resample of the same corpus moves 30 of the 63 test alignments that sit on a tie and 3 of the other 137. A matrix fitted to a different divergence moves alignments far from a tie as well, and the prediction weakens to a chance of 0.62. And a third of the alignments were on a tie only because the matrix was rounded to whole bits — fitted without rounding, 15 of 200 are, and every prediction improves.
The lattice that decides the ties
Rounding a fitted substitution matrix to whole bits puts 63 of 200 alignments on a tie where the exact fit puts 15. Rounding to half bits — a finer grain, and the obvious repair — puts 79. What tracks the ties is not how fine the lattice is but how many of the six fitted costs it keeps apart: whole and half bits both leave three, an eighth of a bit leaves all six, and matches the exact fit exactly.
A distance that is not a distance
Under unit cost the edit distance obeys the triangle inequality and this site asserts that it does. Under a stated substitution matrix it need not, and on 42,840 enumerated triples it fails 2,832 times — taking with it every structure that prunes by distance, at a measured 13.22% of the bounds they rely on.
A lookup that stops caring how wide an entry is
Buckets of eight entries aligned to a cache line read 1.20 lines a lookup when an entry is eight bytes and 19.25 when it is 128, because the bound was arithmetic about alignment and the arithmetic stops holding. Keeping one byte of each key's hash in a separate array and the entries in a parallel one reads 2.21 lines at every width from four bytes to sixty-four — and for a key the table does not hold, 2.05 against 31.98.
Eight cells at once
The anti-diagonal fill order exists because its cells do not depend on one another, and every table filled here has been walked one cell at a time anyway. Computed eight at a time, a step touches 5.71 cache lines on the layout that stores the table by diagonals and 10.87 on the one that stores it by rows — and per cell the first keeps falling to 0.42 while the second stops at 1.27. The prediction that a diagonal step would touch three or four lines was wrong, and line-aligning each diagonal only takes it to 4.94.
Named alongside it
The objects these essays reach for when they reach for this one.
Cost modelEdit distanceDynamic programmingHonest limitSubproblemSubstitution matrixTracebackMeasurementParameter choiceTrade offAffine gapApproximate matching