Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Affine gap — where it appears

A gap charged once for opening and once per character, so a run of four costs less than four runs of one — and no single table can express it. No single table can express it, so the method needs three tables and a state that is a cell together with which table it was reached in.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

acgtacgtseen ->0313303113033130a gap of k characters costs 2krows: expected · columns: seen · unit: bitslinear gaps

A cost that is not one

The same eighty-one cells, filled by the same recurrence, return 6, 10, 10 and 15 — in edits, in cost, in bits and in bits again. Only the first is a count of anything, two of them are equal by arithmetic coincidence, and the alignment each one chooses is different.

tables · Cost —agcacacggatcag—ccagggagta09101112131415161718192021229110101212141416171819192122101021011121314151718191920221110113101212141516171920192112121012411131314151718202119131312111351214131416181921211414131312146131413151719202115141514131314714151316181921161614161514141571416141719191717171517161515168151615182018171818151816161617816171519one unit = one subproblem given a value495 cells across three tables, 980 transitions

A cell that has to know where it is

A gap of four characters is usually one event, not four. No recurrence over a single table can charge it that way, because the price of a gap character depends on how the cell above it was reached and a cell holding one number has thrown that away. The repair is three tables, and it costs exactly three times the cells.

tables · Cost 123456123456cost to open a gapcost to extend a gapintentionexecution571 settingsinte---ntion---execution3 settingsinte-ntion-execution1 setting-intentionexec-ution1 settingintention against execution, affine costseach colour is one optimal alignment

The parameter plane has few answers

Sweep the cost of opening a gap against the cost of extending one over five hundred and seventy-six settings, and the optimal alignment of intention against execution takes four values — one of them at 571 of the settings. Under a linear model the plane divides into three wedges through the origin, because doubling every cost changes nothing and only the ratio is a parameter. Tuning an aligner is choosing a region, and most of the plane is one.

tables · Cost

Named alongside it

The objects these essays reach for when they reach for this one.

AlignmentCost modelDynamic programmingEdit distanceHonest limitMeasurementSubproblemTracebackTrade offUnit of costLog oddsOptimality

All concepts