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

Log odds — where it appears

The logarithm of how much more often an event occurs than chance would predict. In alignment it prices a substitution from counts of aligned pairs, so a pair seen less often than chance becomes expensive and the matrix becomes a statement about its corpus.

Named by 2 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 stay 0.9, 400 pairsacgtacgt0525505225045240stay 0.5, 400 pairsacgtacgt0212202112022120cost of aligning the row letter with the column letterpseudocount 1

The matrix a corpus wrote

A substitution matrix is not a property of an alphabet. Fit one to four hundred pairs of sequences that rarely change and the dearest substitution costs five; fit the same model to four hundred pairs that often change and it costs two. Two hundred test pairs aligned under each matrix give different alignments in 115 cases — and a matrix fitted to eight pairs of the first kind moves 79 of them, from sampling alone.

tables · Cost

Named alongside it

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

AlignmentCost modelEdit distanceSubstitution matrixAffine gapCorpusDynamic programmingEstimatorFittingHonest limitMeasurementModel

All concepts