The lattice that decides the ties

The ties a rounded matrix makes found that a third of its test alignments sat on a tie only because the substitution matrix had been rounded to whole bits. Fitted without rounding, 15 of 200 alignments were within a hair of losing to a competitor; rounded, 63 were. It ended by naming three repairs and predicting what each would do.

The prediction was that a finer lattice would move the boundaries closer together and leave fewer alignments on them. Rounding to half bits or to quarter bits keeps every cost a fixed-point number, so the arithmetic stays exact and the comparisons stay integer comparisons, and the ties should thin out.

The first step of that prediction is wrong, and it is wrong in the direction that matters.

Half bits is a finer lattice than whole bits and it produces a quarter more ties. A grain of a twentieth of a bit is finer than a grain of an eighth and produces a third more. The sequence 63, 79, 41, 23, 15, 20 is not a sequence falling towards 15; it is a sequence that happens to reach 15.

What the grain is actually deciding #

The right-hand column of that plate holds the explanation, and it is exact rather than statistical.

An alignment’s total cost is a sum of substitution costs and gap costs. Two alignments tie when their totals are equal, and the fewer distinct numbers there are to add up, the more ways there are for two different bags of counts to reach the same sum. The lattice creates ties by collapsing distinct entries onto shared values, and how fine it is decides that only by accident.

The accident is visible in the plate. The two transitions — a with g at 1.6674 and c with t at 1.7105 — are four hundredths of a bit apart, and a lattice of an eighth separates them because a boundary at 1.6875 happens to lie between. A lattice of a tenth, five times finer in the sense the prediction used, sends both to 1.7. The same thing happens at the other end: cg at 4.6874 and ac at 4.7059 are nineteen thousandths apart, separated by an eighth-bit lattice whose boundary sits at 4.6875 and merged by every coarser one and by the tenth.

The two rows between them make the same point without the coincidence. A quarter-bit lattice separates the transversions gt and at from the pair cg and ac but leaves that pair merged, so four entries become three and 41 alignments sit on a tie; a fifth-bit lattice separates cg from ac and merges ac with at instead, giving five distinct values and 23 ties. Neither is a refinement of the other — a fifth is not a multiple of a quarter — and each keeps apart a pair the other merges. The count of surviving values is what predicts the ties in both cases, and the ordering of the two grains does not.

So the question “is this lattice fine enough” has no answer that depends only on the lattice. It depends on where the fitted numbers fell, which is a property of the corpus, and a matrix fitted to a different corpus would be separated by a different set of grains.

Half bits, and why it is worse than whole bits #

The half-bit case deserves its own look, because it is the repair anybody would reach for first and it is the worst row on the plate.

Halving the grain does exactly what the prediction said to the empty band: at whole bits no alignment has a margin between 0.01 and 0.2, because every total is a whole number and the smallest non-zero difference between two totals is one bit; at half bits seven alignments appear in that gap, because the smallest non-zero difference is now half a bit and it can be closed by a smaller change of cost.

That part of the prediction holds. What it did not consider is which entries the finer lattice merges. Whole bits sends gt at 4.3229 to 4 and the other three transversions to 5, so the four transversions are two distinct numbers. Half bits sends gt, cg and ac all to 4.5 and only at to 5, so they are two distinct numbers again — but now three of the four agree rather than three of the four disagreeing, and an alignment that trades one transversion for another has become exactly free.

That is the mechanism in one sentence: a lattice does not merely blur the costs, it decides which substitutions become interchangeable. Three interchangeable transversions produce far more exact ties than two, and the sixteen extra ties are the result.

The arithmetic of a single pair makes it concrete. Take two alignments of the same sequences that differ in one column: one spends a g-for-t substitution where the other spends a c-for-g. Unrounded they cost 4.3229 and 4.6874, so the first is cheaper by 0.3645 of a bit and there is a fact of the matter about which alignment wins. At whole bits they cost 4 and 5, so the first is cheaper by a whole bit and the fact is preserved and exaggerated. At half bits they both cost 4.5, the difference is zero, and the two alignments are tied — the aligner reports whichever its traceback reaches first, and a change to the corpus that moves either entry by a tenth of a bit flips the report with nothing to warn the reader. The fitted matrix knew which was cheaper; the half-bit matrix threw that away and the whole-bit matrix did not.

That is also why the inversion could not have been predicted from the grain. Whether a lattice preserves an ordering among entries depends on where its boundaries fall relative to them, and the matrix a corpus wrote established that the entries move by up to half a bit between corpora of the same kind — so the lattice that preserves them is itself a property of one fit rather than of the method.

An eighth of a bit gives the exact fit back #

The other half of the original question was whether a fine enough lattice recovers what the unrounded fit does while keeping integer arithmetic, and there the answer is a clean yes.

Fifteen and fifteen is not an approximation; it is the same set of alignments on a tie, because all six costs survived both and the sums that collide are the same sums. What the lattice bought is that the arithmetic stays exact — an eighth-bit matrix is an integer matrix in units of an eighth of a bit, so nothing in the fill has to compare floating-point numbers for equality, which is the hazard a cost that is not one opened this subject with — and the reason a fourth transition added to the recurrence, as in the edit that reaches back two rows, has to be given a cost on the same lattice as the other three.

And the prediction the previous page cared about comes back with it.

Every refit predicts better under the finer lattice, and the improvement is largest for the refits the previous page found hardest — the ones fitted to eight pairs and to a different divergence, where the whole-bit margin was barely better than a coin. The reason is the same one again: with three distinct costs a great many alignments have a margin of exactly zero, and a margin of zero cannot rank anything.

The split behind that number is worth reading directly, because the previous page had to report it as a rate rather than as a rule.

Under the eighth-bit fit a resample moves all fifteen of the alignments on a tie and 21 of the other 185 — a hundred per cent against eleven. At whole bits the same refit moved 30 of 63 and 3 of 137, which is a good prediction in the aggregate and a poor rule for any individual alignment: being on a tie left the odds under a half. The finer lattice turns the same statistic into something a report could carry beside an alignment, which was the use the parameter plane has few answers proposed for it in the first place.

And what the lattice does not do is suppress the refits that carry real information. The matrix fitted to a corpus of a different divergence moves 115 alignments at whole bits and 115 at eighth bits — the same number, and the largest change it makes to any single cost falls only from 3.00 to 2.63. The fine lattice removed 48 of the 63 ties and left the far refit’s effect untouched. So the two are separable: most of what the rounding was doing was manufacturing coincidences among the costs, and none of it was carrying the difference between two corpora.

The repair that does not work at all #

The third repair the previous page named was randomised rounding: round each entry up or down to a whole bit with a probability set by its fractional part, so that the entries stop landing on the same lattice in the same direction. Each entry here is given a fixed threshold drawn from a hash of the entry and a seed, and rounds up when its fitted value’s fractional part exceeds that threshold.

Randomised rounding cannot work here and the reason is arithmetic rather than luck. Rounding to whole bits leaves at most as many distinct values as there are whole numbers in the range the fitted costs occupy, and these six occupy the range from 1.67 to 4.88 — four whole numbers, of which the floor at one bit and the clustering leave two or three reachable. Which entry goes to which of them is what the draw decides, and the count is what the ties depend on. Randomising which value an entry collapses to cannot increase how many values there are.

The plate also shows the failure that looks like a success. On three of the six draws the resample moves nothing at all, which reads as perfect stability and is nothing of the kind: the two matrices are identical, so the aligner has become insensitive to information the refit genuinely carried, and a reader comparing two corpora would conclude they agree when what agreed was the rounding. That is the same shape of error as a distance divided by a length — a quantity that answers a question it was not asked.

What is being claimed, and at what scale #

The alignments themselves are what is being compared, not their scores. Two matrices put their totals in two different currencies and a score under one says nothing about a score under the other, so every “moved” count above is a comparison of which columns came out — the convention the matrix a corpus wrote established and the only comparison available. It means a refit that changes every score and no alignment counts as changing nothing, which is the right answer for a user reading an alignment and the wrong one for a user reading a score.

Six entries is a small number and the argument depends on it. This alphabet has four letters and so six unordered substitution pairs. On a twenty-letter alphabet there are 190, spread over a wider range, and whole-bit rounding would leave perhaps eight or ten distinct values rather than three — so the collapse measured here would be much milder and the half-bit inversion might not appear at all. The mechanism generalises; the numbers do not, and nothing here has been measured on a larger alphabet.

The gap costs were not rounded and were not swept. A gap character costs three bits in every matrix here, written down rather than fitted, so the lattice touches six of the seven costs and the seventh is a constant. That is a real limit: a fitted gap cost would land off the lattice like everything else, and a model that charges a gap by its length rather than per character — the three tables of a cell that has to know where it is — has two gap parameters to round rather than one.

The margins are upper bounds. A margin is the smallest change, over sixteen random directions in the seven-dimensional space of costs, that moves the alignment; a nearer boundary may lie along a direction not tried. The site’s check states that no alignment moves under a refit smaller than its measured margin and requires the measurement to refuse it, which it does.

A tie at zero and a tie that no cost can break are different things, and the counts above are of the first. Around 170 of the 200 pairs have more than one optimal alignment, and most of those alignments differ only in where a gap sits inside a run of identical letters — they carry identical counts of every substitution and cost the same under every matrix there is. Those are not affected by any lattice and are not what is being counted.

And the grain is a choice about the model, not about the arithmetic. An eighth-bit matrix is not more accurate than a whole-bit one. The fitted numbers have their own sampling error — a resample of the same 400 pairs moves entries by up to half a bit — so a lattice of an eighth is resolving differences much smaller than the fit can distinguish. What it buys is that the reported alignment stops being an artefact of the rounding, and that an alignment’s distance to a tie becomes a usable warning. Both are properties of the report rather than of the truth.

What to ship #

The measurements support one recommendation and refuse two.

Round to a lattice fine enough to keep every fitted entry on its own multiple, and check that it does rather than assuming it. For this corpus that is an eighth of a bit and it is not an eighth of a bit in general; the check is the one the plate above performs, which is to count the distinct values after snapping and compare it against the number of entries. That check costs nothing and it is the only thing on this page that transfers to another alphabet unchanged.

Do not choose the grain by fineness alone, which is the rule the previous page assumed and which halving the grain refutes. A grain of a twentieth of a bit leaves five of the six entries distinct and 20 alignments on a tie, and a grain of an eighth leaves six and 15 — the finer lattice is the worse one.

Do not randomise. The scheme cannot add distinct values and its behaviour is set by the draw, and on half the draws tried it made the aligner blind to a resample while leaving it fully sensitive to a change of corpus, which is an instrument whose reading cannot be interpreted.

There is a fourth option this page has not measured and should name: do not round at all. Nothing forces a substitution matrix onto a lattice except convention and the wish to compare integers, and a modern fill compares doubles at the same speed. The reason the convention persists is that a whole-bit matrix is legible — a reader can see that a transition costs two and a transversion five — and a distance that is not a distance is the page about what else gets assumed when a cost model looks simple. The finding here is that the legibility is paid for in ties, and that an eighth of a bit buys most of it back.

Still open: the grain a corpus chooses for itself #

Every lattice on this page was written down in advance and the corpus was not consulted. That is the wrong way round, since the whole finding is that a lattice is good or bad according to where the fitted numbers happen to fall.

A fit knows where its numbers are. It could choose its own lattice: the coarsest grain that keeps every pair of entries on different multiples, or the coarsest that keeps apart every pair the corpus has enough evidence to separate — which is a different and better rule, because two entries nineteen thousandths of a bit apart are not two entries the data has distinguished, and separating them is resolving noise.

The measurement that follows computes both grains for a series of corpora, asks how coarse they turn out to be and how much they vary between resamples of the same corpus, and sets the alignments-on-a-tie count under each against the fixed grains here. The question it has to answer is whether a lattice chosen from the data inherits the data’s sampling error — a grain that changes when the corpus is resampled is a fourth source of the instability this page and the two before it have been measuring, and it would be one introduced by the repair.