A cost built from two properties

The classes held-out pairs cannot rule out fitted a substitution matrix for a four-letter alphabet by choosing, as part of the fit, how many distinct costs it has. Every one of the 203 ways of grouping the six mismatch pairs into classes was fitted with one cost a class. A penalty growing as half the logarithm of the number of aligned columns chose among them, and on corpora from a generator with two classes it found those two on 127 of 128 corpora. It found a third class planted half a bit away once there were 1,600 sequence pairs to see it.

Its closing section asked about a different kind of generator. A cost that is not one began this line of argument with costs computed from a rule about the letters, and a partition is only one such rule: a list of which pairs are the same. Another is a sum. A transversion costs something, a difference in some second property of the letters costs something else, and each pair pays whichever terms apply to it. The section predicted that on such a generator the best partition would need four or five classes where the sum needs two terms. It predicted that the sum would reach the generator’s alignments with less data, because a shared term pools evidence across pairs that no partition would group.

Both predictions hold. The more useful finding is what happens to the partition’s number of classes.

Why the second property has to be graded #

The obvious second property does not work, and the reason takes a line to state. DNA’s letters can be sorted three ways into two groups of two: purines against pyrimidines, amino against keto, and weak against strong pairing. Each of the six mismatch pairs differs in exactly two of those three. ag is two purines, so it differs in the other two properties. ac is two amino letters, and differs in the other two. The same holds for every pair. So any sum of terms, each counting a difference in one of these properties, gives only three distinct costs, one for each pair of properties a mismatch can differ in. The three classes are {ag, ct}, {ac, gt} and {at, cg}. On four letters, every additive rule over two-way properties is a partition with three classes, and the partition search already contains it.

A property that can make the argument has to be graded. The generator here gives each letter a number — a 0, c 1, g 3, t 7, chosen so that the six pairs have six different differences — and a mismatch’s weight is $2^{-(\alpha\,\mathrm{tv} + \beta\,\Delta)}$. Here tv is one for a transversion and $\Delta$ is the difference between the pair’s two numbers. With $\alpha = 3$ bits, the eightfold preference for transitions every earlier page used, and $\beta = 0.2$ bits a unit, the six costs run from 1.43 bits for ag to 5.23 for at, all different. The numbers stand for any measured quantity a letter might carry. They are not a property of real nucleotides, and nothing here depends on which quantity they are.

Each corpus is fitted two ways. As a partition, all 203 groupings are fitted with one probability a class, and the growing penalty (BIC) chooses. A partition of $k$ classes has $k$ free parameters once the identity share is counted, as on the earlier page. As a sum, the identity share, $\alpha$ and $\beta$ are fitted by maximum likelihood. The sum is told the letters’ numbers and nothing else, and the mismatch part of its likelihood is concave, so Newton’s method finds it exactly. It has three free parameters.

A number of classes that moves with the corpus #

The growing penalty chooses two classes at 25 sequence pairs, four at 200 on every corpus, five at 1,600, and all six on only seven of sixteen corpora at 3,200. The prediction said four or five, and it is right in the middle of the range, but the range is the finding. On the earlier page’s generator the chosen partition settled on the truth and stayed there as the corpus grew. Here there is no partition to settle on short of six classes, and the penalty’s choice tracks how many of the six costs the corpus can tell apart. With 25 sequence pairs it can tell transitions from transversions. By 200 it can also split the transversions into a cheap pair and a dear pair. It needs thousands to separate ac from cg, whose costs differ by 0.2 bits.

A partition’s number of classes, chosen from data, is therefore a statement about the corpus’s size as much as about the generator. The growing penalty is doing what it did before: it adds a class when the evidence for it outweighs half a log of the columns. When every pair really is different, it keeps adding classes as long as the corpus keeps growing. The grain a corpus chooses for itself found a rounding grain that varied from resample to resample of the same corpus, and this is its counterpart across sizes. A structure read off a fitted matrix can say more about the fit than about the source.

Six costs on one line #

One corpus of 400 sequence pairs shows the three fits side by side. The chosen partition has four classes. It keeps the two transitions apart, merges ac with cg at 4.03 bits, and merges gt with at at 4.86. Each merged class gets the mean of its members’ evidence. That is right for neither member: at is priced 0.37 bits cheap and gt 0.23 bits dear. The sum places all six within 0.1 bits of the generator, with three parameters. Six free classes land about as close, with six parameters and no shared structure.

The sum does better than six free classes on the pairs the corpus has least of. The dearest pairs are the rarest: at is seen about a fourteenth as often as ag. A partition fits each class from its own counts alone. The sum fits $\beta$ from every pair at once, so the evidence that a unit of difference costs 0.2 bits comes mostly from the common pairs, and it prices the rare ones through the rule. That is the pooling the section predicted. It pools across pairs no partition would group, because ag and at belong to different classes on every sensible partition, yet share the $\beta$ that sets both their costs.

The pooling can be measured directly, as the spread of a fitted cost across sixteen corpora of the same size. A corpus of 50 sequence pairs has about 2,900 aligned columns. On one such corpus ag appears 137 times and at 13. Fitted as its own class, at’s cost varies by 0.39 bits from corpus to corpus. Fitted through the sum, it varies by 0.24, because thirteen observations of at are now one small part of the evidence for $\alpha$ and $\beta$. The terms themselves settle quickly: $\beta$ is 0.19 ± 0.04 bits a unit at 50 pairs and 0.202 ± 0.016 at 400, and $\alpha$ is 2.95 ± 0.21 and 3.00 ± 0.07. At 400 pairs the spread of at’s cost is 0.11 bits as its own class and 0.08 through the sum. The gap narrows as every pair’s own counts grow, but it never closes, since the sum always has more evidence behind each cost than the pair alone.

How well each fit predicts a fresh corpus #

The sum predicts a fresh corpus better than any partition at every size: at 100 sequence pairs it loses 0.22 bits every thousand columns against the generator, six free classes 0.41, and the chosen partition 1.01. The ordering among the partitions is the surprise. On the earlier page’s generator the growing penalty was the right way to choose. Here the partition it chooses predicts worse than six free classes at every size, by a factor between 1.7 and 2.5. Merging pairs whose costs differ builds a bias into the fit that no amount of data removes until the merge is undone. The penalty charges a class half a log of the columns as though a split were a luxury, and here every split it declines is real.

The six-class fit and the sum both converge on the generator. The sum gets there faster because it has half the parameters and none of them is wasted: at every size its excess is between half and three quarters of the six-class fit’s.

The alignments a fit gets right #

What a matrix is for is alignment, and the earlier pages scored fits by it. Two hundred test pairs, more diverged than the corpus, are aligned under each fit’s costs. An alignment counts as right if it is optimal under the generator’s own costs.

Fitted on 50 sequence pairs, the sum gets 191 of 200 alignments right. The chosen partition gets 159, and needs 3,200 pairs to pass what the sum had at 50. That confirms the section’s second prediction, and by a wide margin: in data, the partition needs sixty-four times as much. Six free classes get 181 at 50 pairs and 198 at 3,200, closer to the sum than the chosen partition is at every size. The two-class matrix — the earlier pages’ generator, fitted here to data it does not describe — levels off at 144 however much data it sees, because no amount of data makes its two costs into six.

The ties a rounded matrix makes found that an alignment changes when a cost moves past a tie, and that small errors in costs change few alignments. The chosen partition’s errors are not small: 0.37 bits on at is enough to move alignments that sit near a tie between an at substitution and a gt. The sum’s errors at 50 pairs are larger than its errors at 400. Every one of them is shared through $\alpha$ and $\beta$, though, so the costs keep their order: on all sixteen corpora at 25, 50 and 100 pairs the sum ranks the six pairs exactly as the generator does. An alignment that depends only on which substitution is dearer does not change. The lattice that decides the ties found that what matters to alignments after rounding is how many of the six costs a lattice keeps apart. The chosen partition keeps four apart at 400 pairs by construction. The sum keeps all six apart at every size, in the right order, and that is most of its advantage.

The price of naming the property #

The sum was told the letters’ numbers, and that is the whole of what it knows that a partition does not. The same four numbers on the wrong letters — a 0, c 7, g 1, t 3 — make a sum that is still a two-term model, still has three parameters, and still fits its likelihood exactly.

Told the wrong property, the sum predicts a fresh corpus 2.94 bits every thousand columns worse than the generator at 3,200 pairs and does not improve with data, and gets 135 alignments of 200 right — fewer than the two-class matrix’s 144. The two measures disagree about how bad that is. In likelihood the wrong sum is slightly better than the two-class matrix, 2.94 bits against 3.24 at 3,200 pairs, because it still prices the two transitions cheap. In alignments it is worse, because the wrong numbers put the four transversions almost in reverse order, and the order of the costs is what an alignment reads. A partition can be too coarse, and more data will tell it so. A sum over the wrong property is wrong in a way its own fit cannot see. Its $\alpha$ and $\beta$ converge happily to the values that make the wrong rule least bad, and nothing in its likelihood distinguishes being close to the truth from being as close as the wrong rule allows.

The sum has one guarantee a partition lacks, and it holds whatever the property. A distance that is not a distance found that a substitution matrix need not obey the triangle inequality, and that every structure that prunes by distance fails with it. A sum of a constant, a transversion term and a difference along a line obeys it for any non-negative $\alpha$ and $\beta$, because each piece does. Six free classes fitted to 25 sequence pairs break it on three corpora of sixteen, when a rare pair’s cost comes out above the sum of two common ones. The sum breaks it on none, the right property or the wrong one.

The growing penalty can see the wrong property, once it is allowed to compare the two kinds of model. Scored with its three parameters against every partition, the sum over the right property beats every partition’s score on 7 of 16 corpora at 25 pairs, 15 of 16 at 50, and all sixteen from 100 up. The sum over the wrong property never does, on any of the 128 corpora from 25 pairs to 3,200.

The control is the earlier page’s generator, where only the transversion term exists. The sum then carries a $\beta$ with nothing to fit, and pays for it: 0.61 bits every thousand columns against the chosen partition’s 0.47 at 50 pairs, converging by 400. The growing penalty, offered both kinds of model, chooses the partition on every one of sixteen corpora at every size. So one criterion, applied across both kinds of model, chooses the right kind in both directions. The parameter plane has few answers swept a gap-opening cost against a gap-extension cost and found the optimal alignment takes only four values over 576 settings. The sum is a model with a plane of two parameters of its own. Its answers are as few as that page’s: at 50 pairs, where $\alpha$ and $\beta$ are still uncertain by a tenth of their size, they already order the six costs as the generator does. It prefers the sum when the costs are a sum over the property it was given, and the partition when they are classes. The matrix a corpus wrote found that a fitted matrix belongs to its corpus rather than its alphabet, and this is the same point one level up: the form of the matrix belongs to the corpus too, and can be chosen from it.

Where the measurement stops #

One generator, one setting of its terms. Every corpus uses $\alpha = 3$ and $\beta = 0.2$ bits, 90% identity and 4% indels. A smaller $\beta$ makes the six costs closer together, the partition’s classes slower to appear, and the sum’s advantage larger at small sizes. A larger one makes the partition’s merges more costly still.

The property is given, not learned. The sum is told the letters’ numbers. Its advantage is the advantage of knowing a true fact about the letters. The wrong-property measurement says what that fact is worth when it is false, but not what it is worth half-true — a property that orders most pairs correctly and a few wrongly.

Four letters, six pairs. Every partition could be enumerated because six pairs have 203 groupings. A protein alphabet of twenty letters has 190 pairs and a number of partitions with more than two hundred digits, so a partition search there is a heuristic, and the argument for shared terms is stronger than anything measured here.

Uniform letters. Letter frequencies are equal in every corpus, so a cost is minus the logarithm of the pair’s probability plus a constant. With unequal frequencies the scale needs the letters’ own probabilities, and nothing about the comparison changes.

Still open: a property the corpus has to find #

The sum won because it was told the right numbers, and lost to the simplest matrix when told wrong ones. The obvious next model does not need telling. Give each letter a position on a line as a free parameter, and let a mismatch cost $\alpha\,\mathrm{tv}$ plus $\beta$ times the distance between the two positions. With four letters that is three free positions (one can be fixed at zero), a scale and the transversion term. That is five parameters, between the sum’s three and six free classes.

The measurement that follows fits that model to the same corpora — by alternating between the positions and the two terms, since the likelihood is no longer concave in all of them together. It asks two things. The first is whether the fitted positions recover the generator’s order of the letters, and from how many sequence pairs. The second is where the model’s alignments fall between the sum’s and six free classes’. The prediction is that it needs about four times the sum’s data to find the order. Once it has the order, it should behave like the sum with two wasted parameters, and so sit between the sum and six free classes at every size. It could fail on small corpora, where the positions of the rare letters’ pairs are poorly determined and the fit can put two letters in the wrong order at a small loss of likelihood. Then the model would inherit the wrong-property failure measured here, without ever having been told anything wrong.