The grain a corpus chooses for itself

The lattice that decides the ties rounded one fitted substitution matrix seven ways and found that the grain of the lattice was not what decided how many alignments sat on a tie. What decided it was how many of the six fitted costs the lattice kept apart. Half bits merged the same pairs as whole bits and left more ties; an eighth of a bit kept all six apart and reproduced the unrounded fit exactly.

Every lattice on that page was chosen in advance, as whole bits had been in the ties a rounded matrix makes, where rounding first put a third of the test alignments on a tie. It ended by turning the question round. A fit knows where its numbers are, so it could choose its own lattice — the coarsest grain that keeps every pair of costs on different multiples. Or it could choose a better one: the coarsest that keeps apart only the pairs the corpus has enough evidence to separate. It also named the risk. A grain that changes when the corpus is resampled is a new source of instability, introduced by the repair.

Both rules are measured here, and the second turns out not to be a lattice at all.

What the corpus knows about its own numbers #

A cost that is not one gave every pair of letters its own substitution cost. The corpora in these essays are drawn from a generator that uses exactly two. The four letters appear uniformly; a letter survives with probability 0.9, and when it mutates it becomes its transition partner eight times as readily as either transversion. Work that through the log-odds and the generator’s own matrix has a transition cost of 1.644 bits and a transversion cost of 4.644 — two numbers, not six.

A fitted matrix has six, because the fit estimates each pair separately and noise makes them differ. How much of the difference is noise can be measured. Resample the corpus’s 400 aligned pairs with replacement a hundred times, refit each time, and the spread of each fitted cost across the refits is its standard error. The pair of sequences is the unit resampled, because the columns inside one pair are not independent.

The picture settles most of the argument before any rule is applied. The two transitions sit within each other’s error bars. So do three of the four transversions, and all four overlap the generator’s value. The fitted matrix’s six numbers are two numbers plus noise, and the noise is several times larger than most of the gaps between them.

A lattice that keeps all six apart must resolve the smallest of those gaps, which here is between ac and cg, eighteen thousandths of a bit apart. That gap is a tenth of its own standard error. The first rule chooses its grain by resolving a difference the corpus has no evidence for. A result the size of its own noise found the same thing in a coding experiment, where a reported win of 0.022 bits a symbol was 0.004 once its spread over sixteen streams was measured.

The first rule, on eight resamples #

If the separating grain is set by noise, it should change when the noise does. Draw eight corpora from the same substitution process with different seeds and compute the grain for each.

At 400 pairs the separating grain ranges from an eighth of a bit to a forty-seventh, a factor of six, on corpora that differ only in their seed. At 1,600 pairs it is finer on average, because the fitted costs converge towards the generator’s two values and the transversions crowd closer together. One resample needs a grain finer than any on the list, and the lattice becomes the exact fit.

This is the instability the previous page predicted, and it is worse than predicted. The separating grain does not merely wobble. It is a direct readout of the smallest gap between noisy estimates of equal quantities, so its distribution is a property of the noise, and it gets finer as the corpus grows rather than settling. More data makes this rule’s answer less coarse, which is the opposite of what a rule about resolution should do.

The second rule behaves better. The coarsest lattice that keeps apart only the pairs the corpus can distinguish at two standard errors comes out at whole bits on all eight resamples of 400 pairs. But whole bits is also the coarsest lattice on the list, so the rule is pinned against its own limit. And a whole-bit lattice does more than keep apart what must be kept apart. It rounds one transversion to 4 and the others to 5 wherever the fitted values straddle 4.5, which separates pairs the evidence says are equal.

That is the limitation of any lattice, and it is structural. A lattice can only snap each number to its nearest multiple. It cannot put two numbers on the same point because the corpus cannot tell them apart; it can only do so if they happen to round the same way.

What the evidence chooses when it is not asked for a lattice #

The evidence can choose something a lattice cannot. Take every pair of fitted costs whose difference is within two combined standard errors, and merge them. Merge transitively, so that if ac cannot be told from cg and cg cannot be told from at, all three share one value. Give each group the precision-weighted mean of its members.

On the corpus in the first plate that produces three groups: the two transitions together, ac, at and cg together, and gt on its own, since gt at 4.323 is 2.1 standard errors from cg and further from the others. On seven of the eight resamples it produces exactly two groups — the generator’s own structure, recovered from the data by asking the data what it knows.

Scoring the matrices needs a standard that does not come from another fit. The generator is that standard. For each test pair, the alignment a matrix chooses is right if its cost under the generator’s two costs is the least cost available under them. Ties under the generator are genuine — two alignments that trade one transversion for another cost the same — so any of the tied alignments counts. The parameter plane has few answers showed why such ties are common: a cost model has finitely many optimal alignments, and a model with only two distinct costs sits on many of their boundaries at once.

Pooled by the evidence, the fit chooses an alignment the generator agrees with for all 200 test pairs, on every one of the eight resamples. Every other scheme makes mistakes on some resample. The exact fit gets 186 right on its worst, and whole bits 169.

The mistakes have a single cause. The exact fit on the first resample prices gt at 4.323 and at at 4.879, so between two alignments that differ by trading one transversion for the other it prefers the one with gt. The generator scores them equal, so that preference costs nothing — unless it also pulls in a gap or a transition somewhere else that the generator would not have paid for. Fourteen of the 200 alignments on that resample do exactly that. The whole-bit lattice turns the same half-bit difference into a whole bit and makes the same mistake more often.

The separating lattice and the eighth-bit lattice are both slightly worse than the exact fit they approximate — 196.00 and 196.38 against 197.75 — because snapping each value to its nearest multiple adds a rounding error on top of the noise. None of the lattices changes the ranking much, because none of them does the one thing that matters, which is to stop distinguishing the equal costs.

How much a resample changes #

The previous page measured what a lattice does to a resample of the same corpus: how many alignments move between two fits that should agree. The same count is available here, for every pair of the eight resamples.

The exact fit changes 22 of 200 alignments between two corpora drawn from the same process. That is the churn the previous pages measured and blamed on ties, and it is mostly not about ties. It is the fit re-deciding, on each resample, which of four equal transversions is cheapest. The lattice that separates all six adds three more changes on average, because its grain changes between resamples along with the noise.

The pooled fit changes 3.29, and every one of those changes is between two alignments the generator scores as equal. It still chooses between them, by the same fixed tie rule every alignment in these essays uses. What differs between resamples is the precise pooled values, and small changes in them decide which of the alignments the generator scores as equal comes out cheapest. So the pooled fit’s churn is not zero, but it is churn among right answers.

The churn was never a property of rounding. It was a property of estimating six numbers where the generator has two, and the repair is not a finer or a coarser lattice but a smaller number of parameters.

How the answer changes with the size of the corpus #

A standard error shrinks as the corpus grows, so the evidence’s grouping should depend on the corpus size. At the small end it might merge transitions with transversions, and at the large end split the transversions apart once their small true differences become measurable. The generator has no such differences, which is exactly why the second should not happen.

Below forty pairs the evidence is too thin for anything. At ten pairs every scheme changes most of the test alignments between resamples and agrees with the generator on about three quarters of them. The pooled fit is not rescued by pooling, because its groups are pooled from bad estimates.

From forty pairs up the pooled fit’s churn drops to about six alignments and keeps falling slowly. The exact fit’s falls much more slowly, from 47 at forty pairs to 15 at 1,600. At 1,600 pairs the exact fit finally agrees with the generator on every test pair, and still re-decides 15 of them between resamples. The pooled fit reached that agreement at 400 pairs, with a quarter of the data.

Whole bits at 1,600 pairs shows the one way a lattice can be stable. With enough data every fitted transition lies between 1.5 and 2.5 and every transversion between 4.5 and 5.5, so every resample rounds to the same two numbers, 2 and 5, and nothing changes between resamples at all. It is stable because it is wrong in the same way every time. 2 and 5 are not in the generator’s ratio, and whole bits chooses an alignment the generator would not on two test pairs, on every resample. A lattice that happens to reproduce the generator’s structure still carries its rounding error.

Where the line is drawn #

The pooling needs a threshold: how many standard errors apart two costs must be before the corpus is said to distinguish them. Two is conventional, and conventions are constants somebody chose, of the kind the threshold somebody chose went looking for in real code.

Below one standard error the threshold treats noise as signal. The six costs split into four or five groups, and the churn returns to the exact fit’s, because a grouping that splits the transversions has the same problem as not grouping them.

From one standard error upwards the answer barely moves. Between one and six the six costs fall into the generator’s two classes on most resamples, and the churn stays between 2.68 and 3.96. The threshold matters only if it is set absurdly low.

That insensitivity is a property of this substitution process, and it should be said plainly. The two true costs are three bits apart and the standard errors are a tenth of a bit, so any sane threshold separates the classes and merges the members. A generator whose true costs were themselves close together — three transversion costs a fifth of a bit apart, say — would have a threshold at which real differences merge, and the sweep above would not be flat.

The grains that were chosen in advance #

The matrices biologists actually use made this choice before seeing any test. BLOSUM62, the default substitution matrix for protein search, is a table of log-odds in half-bit units, rounded to whole numbers. Every entry is an integer multiple of half a bit, fixed when the matrix was built, and a program that uses it adds integers.

The previous pages have been measuring what that choice does, and this page adds one thing to it. A fixed grain is at least the same on every corpus. Whatever the ties it creates, it creates them consistently, and a reader who knows the grain knows where the boundaries are. The rule that lets the fit choose its own grain gives that up. Two matrices fitted to two samples of the same process end up on different lattices, and no single grain describes both.

So the comparison worth making is not between a fixed grain and a chosen one. It is between any grain and a matrix with fewer distinct entries. BLOSUM62 has twenty letters and 190 off-diagonal pairs, and those pairs take eight values, the integers from −4 to 3. That is already a severe pooling. It was done by rounding, and nothing guarantees that the entries sharing a value are the ones the underlying counts could not tell apart. Whether they are is a measurable question about that matrix, and the method on this page is how it would be measured.

What was asked and what was found #

The previous page asked for a lattice the corpus chooses for itself. Two versions were specified, and the measurement answers both.

The lattice that keeps all six costs apart is chosen by noise. Its grain ranges over a factor of six between resamples of the same corpus. It gets finer as the data grows instead of settling. It adds churn to the exact fit rather than removing any.

The lattice that keeps apart only what the evidence distinguishes is pinned at whole bits by this process. That is a coarse lattice with a large rounding error, and it cannot merge what it should merge.

What does work is not a lattice. It is a grouping of the costs by what the corpus can tell apart, and it recovers the generator’s structure from the data, gets every test alignment right from 400 pairs, and changes three alignments between resamples where the exact fit changes twenty-two. The matrix a corpus wrote built these fitted matrices, and it treated each cost as its own parameter, which is what a substitution matrix is. The finding here is that on data from this process that is four parameters too many, and the data can say so. Fitting a class to measurements set the same standard for growth curves: a class is granted only when the fit holds, and a model with more parameters than the evidence supports has not earned them.

The limits of the measurement #

A generator with two costs. Everything above is measured against a generator whose structure is simple and whose classes are far apart, which is the case where pooling is easiest. A real substitution process — amino acids, with twenty letters and graded similarities — has no clean classes, and a grouping at two standard errors would merge things that differ a little and truly.

One kind of pooling. The groups are formed by merging every indistinguishable pair transitively. Transitive merging can chain three costs that are pairwise close into one group even when the ends are distinguishable, and a proper clustering would handle that. On this process no chain crossed the gap between the classes.

Standard errors from a bootstrap of a hundred refits. A hundred is enough for the size of an error bar and not for its tail, and the grouping decision at the margin — gt on the first resample, 2.1 standard errors from its nearest neighbour — could go the other way on a different bootstrap.

A fixed gap cost. Every matrix here uses the same gap cost of three bits, as every fitted matrix in these essays has. The generator’s indel rate implies a gap cost of its own, and a fit that estimated it would add a seventh parameter with its own standard error, which would pool with nothing.

Still open: a matrix whose parameters are chosen by the same evidence #

The pooling above decides how many distinct costs there are after the fit, from the fit’s own error bars. The more principled version decides it as part of the fit. For each way of partitioning the six pairs into classes, it fits one cost per class. Each partition is scored by how well it predicts held-out pairs of the same corpus, and the partition that predicts best is kept.

The measurement that follows does that by cross-validation on the same eight resamples. It asks whether the partition chosen is the generator’s two classes on every resample, how the chosen partition changes on a generator with three classes whose costs are half a bit apart, and whether the held-out score can separate a class that exists from one that does not. The prediction is that on the two-class generator the answer is the same as the pooling here. On the three-class generator the held-out score should detect the half-bit class at 400 pairs and miss it at 40. The corpus size at which it switches is the size of evidence that difference is worth, and it is a number no lattice could have reported.