The ties a rounded matrix makes

The matrix a corpus wrote fitted a substitution matrix to 400 pairs of sequences that rarely change, fitted others to different corpora, and counted how many of 200 test alignments came out differently. A matrix fitted to a distant corpus moved 115 of them; one fitted to only eight pairs of the same kind moved 79; one fitted to forty moved 60. Those are large numbers, and that essay could say how many alignments moved but not which.

The parameter plane has few answers supplied the picture that suggests which. As costs vary continuously, a pair’s optimal alignment holds still over a region of settings and changes only at the region’s boundary, where two alignments cost the same. An alignment deep inside its region survives any small change of costs. An alignment near a boundary is one small change away from losing to its neighbour. So the pairs a refit moves should be the pairs whose settings sat nearest a boundary, and a pair’s distance to its nearest tie should predict whether it moves.

This page measures that distance for each of the 200 test pairs and sets it against what five refitted matrices actually do.

Distance to a tie, measured #

The matrix is the one fitted to 400 pairs that stay unchanged at nine positions in ten: six substitution costs between 2 and 5 bits, a gap costing 3. The test pairs are the same 200 as before, forty characters long, drawn at a stay probability of 0.7.

For each pair, the optimal alignment under that matrix is computed, and then the costs are pushed. A direction moves every one of the seven costs at once — each substitution and the gap — each by an amount between minus one and one. Along a direction, the search finds the smallest step at which the optimal alignment changes, by doubling the step until it does and then halving the interval seven times. The step is measured as the largest change it makes to any single cost, which puts it in the same units as a refit: a refit that changes no cost by more than one bit is a step of one. Sixteen directions are tried, and a pair’s margin is the smallest step any of them needs.

That is an upper bound on the true distance to a boundary, not the distance, since a boundary may be nearer along a direction that was not tried. The site’s check turns that caveat into a claim that must fail, and it does: one alignment below changes under a refit smaller than its measured margin.

Separately, and exactly, the search counts whether each pair’s optimum is unique. It is not unique for 170 of the 200. Most of those ties no change of cost can break: two alignments that differ only in where a gap sits along a run of identical letters have identical counts of every substitution and every gap, and so cost the same under every matrix there is. The margin is the quantity that separates the two kinds, since it is zero exactly when some direction makes the traceback’s chosen alignment lose.

With the matrix as the site fits it — rounded to whole bits — the margins fall into two groups with nothing between. Sixty-three alignments have a margin under 0.01: they are already tied with another alignment that a vanishing change of cost would prefer. The next margin is above 0.2. The median is 0.43.

The empty band has a clean explanation. With every cost a whole number of bits, every alignment’s total is a whole number, so two alignments either cost the same or differ by at least one bit. Closing a difference of one bit takes a cost change of one bit divided by the number of substitutions and gaps by which the two alignments differ, so a small margin needs two alignments that differ in many counts and are only one bit apart. On these pairs the smallest margin above zero is 0.2, a one-bit difference spread over five changed counts. So under a rounded matrix there are no near ties. There are exact ties, and there are alignments at least a fifth of a bit away.

Two kinds of tie #

The 170 pairs whose optimum is not unique and the 63 whose margin is under 0.01 are different sets, and the difference is worth keeping apart, because one kind of tie matters and the other does not.

At least 107 of the 170 pairs are tied only in a way no cost can break. Their optimal alignments differ where a gap is placed within a run of repeated letters, or where two equally scored columns trade places, and every such pair of alignments has the same number of each substitution and the same number of gap characters. They cost the same under the fitted matrix, under every refit on this page, and under any matrix whatever. The traceback reports one of them by its order of preference, and no refit will ever report the other, since no refit can change which of two identically scored alignments the rule prefers.

Those ties are arbitrary and harmless. An aligner that reports either answer is reporting the data equally well, and a user comparing aligners that break such ties differently sees disagreement without seeing any fact the data could settle.

The 63 alignments with a margin under 0.01 are the other kind. Their competitors differ in their counts — one more substitution of one kind and one fewer gap, or a transition traded for a transversion — and they cost the same only because the matrix’s entries happen to make those counts add to the same total. A change to the right entry separates them, in a direction set by the change. These are the ties that refits tip, and they are the ties the rest of this page is about.

Whether the near ones move #

The first refit is the cleanest test: a second corpus of 400 pairs drawn from exactly the same model as the first, so that the only difference between the two matrices is sampling. It changes one cost by one bit and leaves the rest alone, and it moves 33 of the 200 test alignments. Thirty of those 33 were on a tie. Three were not. On a tie, an alignment moved almost half the time; anywhere else, one time in forty-six.

That is the prediction holding as well as it could. A one-bit change in one cost tips ties, and it tips about half of the ties it touches, since a tie can be tipped in either direction and the traceback had chosen one side of it. It almost never moves an alignment that had a fifth of a bit or more to spare.

The other refits change more. Fitted to forty near pairs, the matrix again differs by one bit in two entries and moves 60 alignments, 39 on a tie. Fitted to eight near pairs, it differs in four entries and moves 79, only 30 of them on a tie. Fitted to corpora of greater divergence, it differs by up to two and three bits, and moves 95 and 115 — most of them from alignments that were nowhere near a tie. A refit that changes a cost by three bits is not a small perturbation to anything with a margin of half a bit.

How far a resample moves the costs #

The margins are only half the comparison; the other half is how much a matrix’s own entries move when the corpus behind them is drawn again. The unrounded fits say it directly, since there nothing hides a change below half a bit.

Refitted to a second corpus of 400 near pairs, the largest change to any entry is 0.47 of a bit. Refitted to 40 pairs it is 0.52, and to 8 pairs 0.91. Those are sampling errors: the corpora come from exactly the model the first one came from, and the matrices disagree because a few hundred sequences are a few hundred sequences.

Set beside the margins, the numbers are the same size. The median unrounded margin is 0.32 of a bit, and the median rounded one 0.43. So half of the test alignments are within one resample’s worth of cost change of a tie, before the question of divergence even arises — a matrix fitted from a corpus this size does not determine them. The flat bottom of a shallow curve found a tuning optimum that the data could not locate within a wide flat region; here the region is not flat, and what the data cannot locate is which side of a boundary half of the answers fall on.

By quarter of the margin #

The quarters draw the same result as a gradient. For the resample, movement is concentrated in the narrowest quarter and falls to nothing in the widest. For the far refit, the widest quarter loses 23 of its 50 alignments, nearly as many as the narrowest, and the margin is barely telling the moved from the unmoved.

One number summarises a refit’s gradient: the chance that a randomly chosen alignment the refit moved has a smaller margin than a randomly chosen one it left alone. For the matrices as the site rounds them it is 0.86 for the resample, 0.82 for forty near pairs, 0.71 for eight, 0.68 for a corpus at stay 0.7 and 0.62 for the far corpus. The order is the order of how much each refit changes the costs — largest change one bit, one bit, one bit in four entries, two bits, three bits.

So the margin does what the parameter plane suggested, within the regime the parameter plane describes. It ranks alignments by how likely a small change of costs is to move them. It says much less about a large change, because a large change crosses boundaries far from where an alignment sits, and an alignment’s distance to the nearest boundary is not its distance to every boundary a big refit might cross.

What the rounding did #

The site rounds fitted costs to whole bits by convention, as nearly every published substitution matrix does. The measurement can be repeated with the fitted log-odds left as real numbers, floored at one bit as before, and it changes the picture in three ways.

It removes most of the ties. Unrounded, 15 of the 200 alignments have a margin under 0.01, against 63 rounded, and the empty band fills: 34 alignments between 0.01 and 0.1 and 34 more between 0.1 and 0.2. Forty-eight more test alignments sit exactly on a tie when the matrix is rounded than when it is not, and for each of those the traceback’s order of preference — substitution, then deletion, then insertion — decided which of two equally good alignments to report.

It sharpens every prediction. Unrounded, the chance that a moved alignment had the smaller margin is 0.93 for the resample, 0.92, 0.88, 0.86, and 0.79 for the far corpus. No refit moves a single alignment from the widest quarter of the unrounded margins except the two refits to different divergences, and those move 3 and 16.

And it changes what counts as a refit at all. A fourth near corpus, of 100 pairs, rounds to exactly the same matrix as the 400-pair corpus and so moves no alignment; unrounded, its costs differ by at most 0.38 of a bit and it moves 24. Rounding is a filter on refits as well as a source of ties: a sample that shifts every cost by less than half a bit is invisible to it, and a sample that shifts one cost across a half-bit boundary moves a whole bit and tips every tie that cost takes part in.

The trade has two sides and neither is an error. A rounded matrix is stable against small resamples that do not cross a rounding boundary, and it has more ties, most of which a small change of the right entry will tip. An unrounded matrix moves a little under every resample, and what moves is precisely what was close. The threshold somebody chose found shipped constants in sorting routines sitting inside wide flat regions where rounding them would change nothing; a substitution matrix is the opposite case, where the grid the constants are rounded to is coarse enough to create the boundaries the answers sit on.

An alignment and its margin #

The practical content is a number an aligner could report beside each alignment and does not. A cost that is not one found that two cost models align the same pair differently; the margin says, for one model, how much of an alignment the model’s numbers actually support.

An alignment with a margin of zero is one of several alignments the matrix scores identically, and it was chosen by the traceback’s tie rule rather than by the data. On these test pairs, under a rounded matrix, that is almost a third of them. An alignment with a margin of half a bit is supported by the matrix against every estimation error smaller than that, and a matrix fitted from a few hundred pairs changes its entries by about that much when resampled. The estimate a plan rests on met the same situation in a query planner, which picks an index or a scan from an estimated count of matching rows: an estimate wrong by a factor of sixty-four cost 13.5 times the right plan on one side of the crossing and at most 4.01 times on the other. There the decision’s cost of error could be bounded before any query ran; here the margin says how large an error in the costs the decision can absorb, and what insurance against an estimate costs priced the choice that does not depend on either.

The margin also says what the tie-breaking rule is worth. The tie that breaks left found a hash table whose tie rule, chosen deliberately, improved its whole load distribution. The traceback’s tie rule is not chosen for anything; it is the order the three predecessors are tested in. On a third of these alignments it is the whole of the reason one answer was reported rather than another.

A bound it is not #

The margin is measured along sixteen directions out of a continuum, and the eight-pair refit shows what that leaves out. One test alignment moves under that refit although no cost changes by more than one bit and the alignment’s measured margin is above one. The refit changed four entries at once, and along that combination of changes there is a boundary nearer than any the sixteen directions reached.

So the measured margin ranks alignments and does not certify any of them. An exact margin exists: every alignment’s cost is a linear function of the costs, as the parameter plane has few answers showed for two parameters, so the smallest change that ties a given alignment with any other is the solution of a linear program over the alignments that could compete. Computing it needs those competitors, and a distance that is a path through a grid is the reminder of how many paths a table holds.

What the measurement leaves out #

One base matrix and one test set. Every margin is measured under the matrix fitted to 400 near pairs, for test pairs drawn from the same mutation model at one divergence. Real test pairs come from many divergences and none of them from a model written down in advance.

Linear gaps. Every matrix here charges a gap character three bits with no opening cost. An affine gap adds a parameter along which ties can lie, and the zero that moves the answer is the reminder that some settings change which cells can be optimal at all.

Sixteen directions. More directions would lower some margins and find the boundary the eight-pair refit crossed. The ranking is stable enough to predict the resample at 0.86 with sixteen; how much better an exact margin would predict is not measured.

The floor at one bit. Both the rounded and the unrounded fits floor every substitution at one bit, which is itself a rounding of the cheapest entries, and a tie can sit on that floor.

Still open: rounding that does not make ties #

The rounding is a choice, and the measurements say what it costs: ties at the boundaries it creates, and refits that it absorbs until they cross a half-bit line and then applies all at once. Rounding to half bits or quarter bits keeps integer arithmetic and moves those boundaries closer together; rounding each entry up or down at random, by its fractional part, keeps ties from lining up across entries.

The measurement that follows fits the same corpora at whole, half and quarter bits and with random rounding, and asks how many test alignments each leaves on a tie, how often a resample moves an alignment, and whether a matrix rounded finely enough gives the unrounded fit’s predictions back while keeping integer costs.