The errors the rest of the pattern needs

The search that spends a budget walks an index as a tree: at each state it may extend by any character of the alphabet, skip a pattern character or insert one, spending a unit of budget whenever the move is not a match. It prunes in exactly one place — an interval that has gone empty has no descendants — and the branches an error opens measures what that costs: 39,957 interval extensions at a budget of three, growing by an order of magnitude per error allowed.

Every published implementation of this search prunes in a second place, and the essays that built the walk recorded the gap in one line: a lower-bound pruning in the index walk, which every published implementation has and which would move the crossing against the table by an unmeasured amount.

This essay is the bound.

The idea, in one sentence #

If a piece of the pattern occurs nowhere in the text, then every alignment of any string containing that piece must spend at least one error inside it.

That is all of it. The rest is arithmetic on where the pieces are.

The construction #

Read the pattern left to right, maintaining the set of text positions where what has been read so far occurs. When the set goes empty, the piece just read occurs nowhere: charge one error, throw the set away, and start a new piece at the current character. $D[i]$ is the number of times that has happened by position $i$.

$D$ is non-decreasing by construction, $D[i]$ is a lower bound on the errors in any alignment of $P[0..i]$, and the whole computation is one pass over the pattern.

The reason it is a lower bound rather than the answer is that the pieces are chosen greedily and independently of where they must land. A piece that occurs somewhere in the text may not occur where the alignment needs it, so the true cost can be higher; it can never be lower, because the pieces are disjoint and each one that occurs nowhere costs at least one error of its own.

Why the index has to be of the reversed text #

The set of positions where a string occurs is an interval of the suffix array, and an FM-index maintains it by backward search — extending the string to the left, one character at a time.

The bound needs to extend to the right: it reads the pattern forwards. Occurrences of $W$ in the text are occurrences of $W$ reversed in the reversed text, so one backward-search step in an index of the reversed text is one forward extension here. The construction therefore needs a second index, over the same text read the other way.

That is not a detail. It is the whole cost of the bound, and the third essay on this ladder is about it: the structure whose small size is the entire argument for walking an index rather than filling a table has just doubled.

The computation itself is cheap. On a pattern of sixteen characters against four thousand characters of four-symbol text it is 72 rank operations and two resets, and it reads no character of the text at all — the same seal the walk itself is under, checked the same way.

How the bound is used #

The walk consumes the pattern from the right: a state with $i$ characters left is a state that has matched $P[i..m-1]$ somehow and still has to deal with $P[0..i-1]$.

$D[i-1]$ is a lower bound on what $P[0..i-1]$ must cost. So a state with budget $b$ remaining can be abandoned whenever $b < D[i-1]$, because no descendant of it can finish inside the budget however the rest of the walk goes.

That is a safe pruning in the same sense the published shift rules are safe: it never removes a state holding an answer, and it is free to keep states that hold none. The whole safety argument is the inequality $D[i-1] \le$ the true cost, and the check for it is a comparison against the quadratic table at every position of the pattern.

How tight it is #

Tighter than expected, on the patterns measured.

On a twenty-character pattern with four planted occurrences, $D$ is 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2 — and the true minimum is the same sequence at every position. No slack at all on that pattern.

That is worth reading carefully, because it is a statement about this pattern and this text rather than about the bound. On a nearby pattern — the same sweep with one fewer planted occurrence — the bound is one under the truth at two of twenty positions, so it is tight here rather than tight in general.

A one-pass greedy decomposition can be arbitrarily loose in principle — a pattern whose pieces all occur, individually, in a text that contains none of them together has $D = 0$ and a true cost as large as the construction allows. What the measurement says is that on a random text with a planted occurrence, the greedy pieces are nearly the pieces an optimal decomposition would choose.

What the resets are counting #

Two, on a sixteen-character pattern over four symbols. That is the number of times the accumulated piece stopped occurring in four thousand characters of text.

The number is a property of the text’s alphabet more than of the pattern’s length, and the arithmetic is the same as the one behind every filter in this collection. A random string of length $\ell$ over $\sigma$ symbols occurs in a text of $n$ characters with probability about $n\sigma^{-\ell}$, so the expected length before a piece stops occurring is about $\log_\sigma n$ — five characters on four-symbol text of three thousand characters, and two and a half on a twenty-six symbol alphabet.

So $D$ climbs about once every $\log_\sigma n$ characters, which means it reaches $m/\log_\sigma n$ by the end of the pattern. On the sweep here that is 16/6 ≈ 3, and the measured top of $D$ is 2 — the same arithmetic that the q-grams an error cannot destroy uses to size a counting filter’s threshold, arriving here as the height of a bound.

The consequence is that the bound is worth most on a wide alphabet and nothing on a narrow one, which is the second essay’s subject and the sharpest thing about it.

The same counting argument, three times in this field #

The bound is a pigeonhole argument and this collection has now built three structures on the same one.

The filter that feeds the table cuts a pattern into $k+1$ pieces and observes that $k$ errors cannot touch all of them, so one piece must match exactly. That is the seed filter, and it uses the argument to propose places.

The q-grams an error cannot destroy counts the $q$-grams an error can destroy — at most $q$ each — and derives a threshold on how many must survive. That is the counting filter, and it uses the argument to reject windows.

This one cuts the pattern into pieces that occur nowhere and observes that each costs an error. It uses the argument to abandon states.

Three uses, one lemma, and the differences are worth naming: the seed filter’s pieces are chosen by position and are equal in length; the counting filter’s are every window of length $q$ and overlap; and these are chosen by where the text runs out, so they are unequal, disjoint, and depend on the text rather than only on the pattern. That last property is what makes this bound tighter than the other two and is why it needs an index to compute.

What it does not prune #

Worth stating, because a bound that prunes on the remaining pattern says nothing about two other sources of waste in the walk.

It does not prune on the interval. A state whose interval holds one row and whose remaining pattern is long will be expanded character by character, spending budget, and every branch of that expansion is explored even though a single verification against the text would settle it. That is what a filter would do and this search is deliberately not a filter — it reads no text at any budget.

It does not order the search. The walk explores the alphabet in a fixed order at every state, so a branch that will be pruned three levels down is expanded before one that will not. A best-first order would find answers sooner without changing what is explored in total, and it needs a priority queue whose cost is not obviously smaller than what it saves.

Both are real and both are unbuilt here, which is the same kind of note the search that spends a budget ends on: the structure is the smallest one that makes the point, and the improvements it does not have are named rather than assumed away.

Two ways to get the bound wrong, both of which return real answers #

Both are checks that must reject and both were found by comparing answers rather than by reading code.

Apply it one character late. $D[i-1]$ bounds the characters that remain; $D[i]$ includes the character the walk is about to match, which the state has not committed to. Since $D$ is non-decreasing, using $D[i]$ prunes strictly more — and it prunes states that hold answers. Measured on a ten-character pattern at a budget of one: four positions found by the correct bound, three by the late one, and all three are genuine occurrences.

Bound the wrong end. The walk runs backwards through the pattern, so “the rest of the pattern” is easy to read as what has been consumed rather than what remains. A bound on the pattern’s suffixes is a perfectly good lower bound on a quantity nobody is bounding; on a twelve-character pattern it finds seven of eight positions, and all seven are real.

Neither failure has a signature. There is no exception, no impossible value, nothing an assertion about the reported occurrences could catch — the answers are correct occurrences and there are fewer of them, which is indistinguishable from a pattern that occurs less often than expected. The fourth essay on this ladder is about that shape.

Where the published version of this came from #

The construction is BWA’s, and it is worth saying so plainly because this collection’s habit is to build things rather than cite them and the habit can obscure what is original.

The read aligner’s calculate_d does exactly the pass above — forward extension in an index of the reversed reference, a counter incremented and the interval reset whenever it empties — and uses the array to prune a bounded-error backward search. It is a decade and a half old, it is in production on every genome sequenced, and it is the reason a bounded-error search over a three-billion-character reference is possible at all.

What this collection adds is the measurement. The published account states that the bound prunes and does not say how much, and the two numbers that matter — how much of the tree goes, and what the second index costs — are not in it. Both are here: 70% of the tree at a budget of three, and an index the same size as the one being walked.

The other thing worth adding is the alphabet dependence, which is invisible in the setting the method was built for. A genome is four symbols, which is the middle column of the sweep here; the two-symbol column, where the bound removes 0.8% of the tree against the twenty-six-symbol column’s 80%, is not a case a read aligner meets and is the case that shows what the bound is actually made of.

Why this is a floor rather than an estimate #

The distinction matters and this collection has a field for it.

An estimate of the errors remaining could be used to order the search — explore the promising branches first — and would be useful even if wrong. A bound is used to discard, and a bound that is ever too high discards an answer.

So $D$ belongs with the floors rather than with the heuristics: it is a statement of the form “no alignment can do better than this”, derived from a counting argument over disjoint pieces, and it has the same shape as the floor under every comparison sort — a quantity nothing can get under, proved by an argument about information rather than about an algorithm. A floor that holds if something else does is the caution that goes with it: every floor here is conditional on a model, and this one’s model is that the pieces are disjoint and that an error inside a piece is an error.

What is different is the direction of use. A floor in this collection is usually a limit on what any algorithm can achieve; this one is a limit on what a particular partial state can achieve, which is what turns it from a result into a pruning rule.

What the bound is worth at each budget #

The pruning does nothing at a budget of zero and more at every budget after it: 48.1% of the tree removed at one error, 68.5% at two, 69.8% at three.

The shape is not an accident and it is worth one paragraph. At $k = 0$ the walk is an ordinary backward search — sixteen interval extensions, no branching, nothing to prune. Every unit of budget added multiplies the tree by an order of magnitude, and the states the bound removes are exactly the ones deep in that multiplication: a state that has already spent most of its budget and still has a long, absent stretch of pattern ahead of it. Those states are common at large budgets and absent at small ones.

So the bound’s value grows with the thing that makes the search expensive, which is the property a pruning has to have to be worth a second index. A pruning that removed a constant share regardless of budget would save a constant factor on a cost that grows by a factor of ten per error, and would be an optimisation rather than the difference between feasible and not.

The share does flatten — 48%, 69%, 70% is not a straight line — and the reason is that what remains after pruning is the part of the tree the bound cannot see: states whose remaining pattern occurs perfectly well and which fail for reasons only the text knows. That residue is what a filter would catch and this search will not.

What is being claimed #

$D[i]$ is a lower bound on the errors in any alignment of $P[0..i]$, checked against the quadratic table at every position of an eighteen-character pattern.

It is computed in one pass over the pattern, at 72 rank operations for a sixteen-character pattern, reading no character of the text.

It requires an index of the reversed text, because the walk extends the pattern rightwards and a backward search extends leftwards.

It is nearly tight on the patterns measured — exact at every position of one twenty-character pattern and one under the truth at two positions of its neighbour — and it is loose by construction in the worst case, since the pieces are chosen greedily and without regard to where an alignment would have to put them.

And it climbs once every $\log_\sigma n$ characters, which is why the whole apparatus is worth a great deal on a wide alphabet and nothing at all on a binary one.

One consequence of that last line is worth making explicit, because it bounds what the pruning can ever do.

If $D$ climbs once every $\log_\sigma n$ characters, then over a pattern of $m$ characters it reaches at most $m/\log_\sigma n$. That is a ceiling on the budget the bound can rule anything out at: a sixteen-character pattern over four symbols in three thousand characters gives $\log_4 3000 = 5.8$, so $D$ tops out near three, and against a budget of three or more the bound at the pattern’s start forbids nothing at all.

So the pruning’s reach is $m/\log_\sigma n$ errors, and a search asking for more than that is a search the bound can only trim in its lower branches — which is exactly where the branch that cannot reach an answer finds the removed share flattening rather than continuing to climb.