Skip to content

Entropy and its correction

At every position DiMA summarises the distribution of variants by its Shannon entropy (Shannon 1948): 0 bits when every sequence carries the same k-mer, more as variants become more numerous and more even. This page derives the observed entropy, the paper’s correction for small samples (Tharanga et al. 2025), the way DiMA evaluates that correction exactly, the optional alternative estimators, and the sample coverage reported next to them.

Notation: a position has support N (sequences with a valid k-mer) and D distinct variants with counts c 1 , … , c D ; f c is the number of variants seen exactly c times (so f 1 counts singletons and f 2 doubletons); T is the support threshold.

With the observed frequencies p ^ i = c i / N , the plug-in entropy in bits is

(1) H ^ = − ∑ i = 1 D p ^ i log 2 ⁡ p ^ i = − ∑ c f c c N log 2 ⁡ c N .

It is reported for every position with support as observed_entropy. It is biased downwards: variants that are present in the population but absent from the sample contribute nothing, and to first order the expected value falls short of the true entropy by about ( D − 1 ) / ( 2 N ln ⁡ 2 ) bits (Miller 1955; Paninski 2003). The bias grows with diversity and shrinks with support, so positions with different support are not directly comparable without a correction.

DiMA’s correction (Tharanga et al. 2025, Fig. 2) belongs to the family of extrapolation methods used in information estimation: compute the entropy of subsamples of decreasing size and extrapolate to infinite sample size, where 1 / n → 0 (Strong et al. 1998; Panzeri et al. 2007). For a position with N > T :

  1. Grid of subsample percentages. Let

    (2) x = ⌈ 100 T N ⌉ .

    The grid starts at R 0 = 50 if x < 50 , otherwise at x rounded up to a multiple of 5, and runs R ∈ { R 0 , R 0 + 5 , … , 95 } , plus 100%. Fig. 2 gives the grid as { x % , … , 90 , 95 , 100 % } , or { 50 % , … , 90 , 95 , 100 % } when x ≤ 50 ; the step of 5 throughout and the rounding of x up to a multiple of 5 are those of the authors’ implementation, DiMA v5.0.9 (calculate_entropy in src/lib.rs).

  2. Subsample sizes. For each R < 100 , the subsample size is

    (3) n R = ⌈ R N 100 ⌉ .
  3. Subsample entropies. The paper draws one subsample of n R k-mers with replacement from the position’s k-mers and computes its plug-in entropy H ^ n R . The 100% point is the full data set itself: ( 1 / N , H ^ ) , not resampled.

  4. Regression. The points ( 1 / n R , H ^ n R ) are fitted by ordinary least squares, H ^ n ≈ β 0 + β 1 / n , and the intercept β 0 — the entropy extrapolated to n → ∞ — is the corrected entropy.

  5. Fallbacks. The observed entropy H ^ is reported instead when N ≤ T , when there are fewer than five points, when all subsample sizes are equal (no line is defined), or when the intercept is negative (which never happens to the exact expectation DiMA computes; see the negative-intercept rule).

Rounding x up in (2) guarantees that every subsample has at least T k-mers: R ≥ x ≥ 100 T / N , so n R ≥ R N / 100 ≥ T . Rounding it down would not: for T = 100 , ten values of N between 110 and 198 would give subsamples of 99. The ceiling is what the original implementation adopted in its commit “Fixed algorithm after discussion with Dr. Asif” (February 2022) and the glyph printed in Fig. 2, although the figure’s note beside it, “Lower-bound or minorant, nearest whole number”, reads like rounding down; the subsample sizes (3) are rounded up too (Fig. 2, “Upperbound”). DiMA computes (2) in exact integer arithmetic. DiMA v5.0.9 computed it in floating point, where for example T = 55 , N = 100 gives 56 instead of 55; for the usual thresholds T = 30 and T = 100 the two agree for every N up to two million (the range checked).

With fewer than five points the correction is not applied — a minimum the paper does not state, taken from DiMA v5.0.9 — which happens when x > 80 , that is for N below about 1.25 T (for T = 100 : N = 101 to 124). Duplicate subsample sizes are kept, as in DiMA v5.0.9 (the paper does not say).

Example. At MERS-CoV spike position 25 ( N = 170 ) with T = 100 : x = ⌈ 58.8 ⌉ = 59 , so the grid is 60, 65, …, 95 and 100%, nine points, with subsample sizes 102, 111, 119, 128, 136, 145, 153, 162 and 170. With T = 30 : x = 18 < 50 , so the grid starts at 50: eleven points, from 85 to 170 k-mers.

The paper’s procedure is random: run twice, it gives two different answers, because each H ^ n R comes from one random subsample. DiMA reports the expected value of the procedure instead, which it computes exactly. This changes no part of the method; it removes the noise of one random draw (the paper’s negative-intercept rule, applied to that expected value, then never applies: see below).

The intercept is linear in the responses. For fixed design points u j = 1 / n j (they depend only on N and T ), the least-squares intercept is a weighted sum of the responses,

(4) β ^ 0 = ∑ j w j y j , w j = 1 m − u ¯ u j − u ¯ ∑ l ( u l − u ¯ ) 2 ,

with m points and mean design point u ¯ . Its expectation over the random subsamples is therefore the intercept of the line fitted to the expected subsample entropies, E [ β ^ 0 ] = ∑ j w j E [ y j ] .

The expected subsample entropy has a closed form. A with-replacement sample of size n from the observed k-mers is a draw from the empirical distribution — a nonparametric bootstrap sample (Efron 1979) — so its counts are multinomial, ( X 1 , … , X D ) ∼ Multinomial ( n ; p ^ 1 , … , p ^ D ) , and each count is binomial, X i ∼ Binomial ( n , p ^ i ) . The plug-in entropy is a sum of one term per variant, so by linearity of expectation

(5) E [ H ^ n ] = ∑ c f c ∑ x = 1 n ( n x ) p c x ( 1 − p c ) n − x ( − x n log 2 ⁡ x n ) , p c = c N .

Variants with the same count contribute equally, which is why only the counts of counts f c are needed. DiMA evaluates each binomial sum by starting at its mode and walking outwards with the ratio of consecutive probabilities, n − x x + 1 ⋅ p 1 − p , stopping when a term falls below 10 − 18 of the running total. No factorials or powers are formed, nothing overflows, and the cost is proportional to n p ( 1 − p ) per distinct count. The 100% point stays ( 1 / N , H ^ ) , and the fallbacks of the paper apply to the expected intercept.

Same mean, no larger variance. The exact estimator is the conditional expectation, given the data, of the intercept the paper’s procedure fits from one random draw per grid point: it averages out the resampling noise and nothing else. By the Rao–Blackwell theorem it has the same expected value as that random intercept and a variance that is never larger (Rao 1945; Blackwell 1947). It is also what the original method gives when many random subsets are averaged before extrapolating, as DiMA’s predecessors did: Khan et al. regressed the entropies of repeatedly drawn random sub-alignments on 1 / N (Khan et al. 2008), with averaging over several random subsets the 1 / N relation held for sets as small as 20 sequences (Miotto et al. 2008), and the AVANA tool extrapolated from 100 random sub-alignments by default (Khan et al. 2017).

Consequences.

  • Results are reproducible bit for bit; no random seed is involved.
  • On the paper’s HIV-1 pol dataset the mean corrected entropy is 5.3504 bits; the paper reports about 5.35, and repeated runs of the random procedure give 5.350–5.353 (see Comparison with the paper).
  • Fig. 1C. At MERS-CoV spike position 25 the paper shows 1.38 bits ( T = 30 ). The exact expectation is 1.4451 bits. A simulation of the paper’s random procedure at that position (20,000 runs) has a standard deviation of 0.22 bits, and 1.38 lies at about its 39th percentile: an ordinary draw of the random procedure, not a different method. With T = 100 the expectation is 1.4617 bits (standard deviation of the random procedure 0.30 bits).

The paper reports the observed entropy when the regression “may potentially result in a negative entropy value due to small number of resamples” (Tharanga et al. 2025). DiMA applies this rule to the expected intercept, and that intercept is never negative, so the rule never applies:

  1. The expected entropy of a subsample never decreases with its size n : the frequencies of n + 1 draws are the average of the frequencies of their n + 1 subsets of n draws, each distributed as n draws, and entropy is concave.
  2. It never exceeds the observed entropy H ^ : a subsample drawn with replacement has the observed frequencies as its expected frequencies, and entropy is concave (Jensen’s inequality).
  3. So the points never rise as 1 / n grows, the least-squares slope is at most 0, and the intercept β 0 = y ¯ − β 1 u ¯ (with u ¯ the mean of 1 / n ) is at least the mean of the points y ¯ , which is at least 0. It is 0 only at a fully conserved position.

DiMA therefore has no fallback for a negative intercept. Instead, every reported entropy, from every estimator, is checked to be a finite number of at least 0 bits; a value that is not could only come from a bug, and it stops the run as an internal error (exit 1) instead of being replaced by another value (Wilson et al. 2014, Practice 5a; Hunter-Zinck et al. 2021, Rule 5). A property test confirms the three steps above on random and adversarial count profiles.

DiMA v5.0.9 applies the rule to each random run instead. Where one or a few sequences carry a variant other than the Index, a single run’s intercept is often negative and is then replaced by the larger observed entropy, so v5.0.9’s average over many runs is higher there. With the full eleven-point grid, about 20% of runs fall back when one sequence differs, raising the average by 34–41%; 12–15% with two sequences (17–23%); and 3–5% with five (3–6%), on values of a few hundredths of a bit. With fewer points ( N close to T ) the effect is larger: one sequence differing raises the average by 51% at N = 171 and by 107% at N = 130 ( T = 100 ). On the MERS-CoV spike protein ( T = 100 ) the eligible mean is 0.1261 bits here and about 0.142 bits averaged over v5.0.9 runs; on the HIV-1 pol datasets the two agree. In simulations of two-variant populations with a known entropy ( N from 171 to 3,000, minor-variant frequency 0.05% to 5%), the per-run rule overestimated by up to 19% on average, while the expectation underestimated, by up to 27% when less than one minor-variant sequence was expected and by at most 3% otherwise, with an error close to that of the Miller–Madow correction; neither had the smaller error everywhere.

--estimator selects another estimator for the reported entropy. The paper’s correction (dima) is the default; the alternatives apply at every position with N ≥ 2 , whatever T is, while the summaries still cover eligible positions only. Each position records the method actually used (entropy_method) and, when the requested one could not be used, why (entropy_fallback).

Miller–Madow (miller-madow) adds the first-order bias term (Miller 1955):

(6) H ^ MM = H ^ + D − 1 2 N ln ⁡ 2 .

Chao–Wang–Jost (chao-wang-jost) estimates the entropy from the rate at which new variants are discovered as the sample grows; it was the least biased estimator in its authors’ comparison (Chao et al. 2013). In nats,

(7) H ^ CWJ = ∑ c = 1 N − 1 f c c N ∑ k = c N − 1 1 k + f 1 N ( 1 − A ) 1 − N ( − ln ⁡ A − ∑ r = 1 N − 1 ( 1 − A ) r r ) ,

divided by ln ⁡ 2 for bits, with

(8) A = { 2 f 2 ( N − 1 ) f 1 + 2 f 2 f 2 > 0 , 2 ( N − 1 ) ( f 1 − 1 ) + 2 f 2 = 0 , f 1 > 0 , 1 f 1 = f 2 = 0 .

DiMA evaluates the inner sums with exact harmonic numbers for small counts and an asymptotic series for large ones. The second term is computed exactly, in a time independent of N , through an identity with a hypergeometric function, so that ( 1 − A ) 1 − N is never formed and nothing overflows or cancels; Numerical accuracy describes the method, its sources and its measured accuracy. When A = 1 the second term is 0.

Raw (raw) reports the observed entropy (1) unchanged.

Both alternatives fall back to the observed entropy when N = 1 (single_observation), where the observed entropy is 0. Unlike the paper’s estimator, they are applied at every position with N ≥ 2 , LS and ELS positions included; the support classes then only decide which positions enter the summaries.

EstimatorMERS-CoV spike position 25
observed ( H ^ )1.4224 bits
dima, T = 100 1.4617 bits
dima, T = 30 1.4451 bits
miller-madow1.4606 bits
chao-wang-jost1.4901 bits

Next to every entropy, DiMA reports the estimated sample coverage C ^ : the probability that one more sequence would carry a k-mer already seen at that position. It goes back to Turing’s estimate 1 − f 1 / N (Good 1953); DiMA uses the improved estimator of Chao and Jost (Chao & Jost 2012, Eq. 4a):

(9) C ^ = 1 − f 1 N ⋅ ( N − 1 ) f 1 ( N − 1 ) f 1 + 2 f 2 ,

with ( N − 1 ) ( f 1 − 1 ) / ( ( N − 1 ) ( f 1 − 1 ) + 2 ) as the second factor when f 2 = 0 (the same convention as A in (8), so that C ^ = 1 − ( f 1 / N ) ( 1 − A ) ), and C ^ = 1 when f 1 = 0 . It is undefined (null) for N < 2 . Low coverage means that much of the diversity at that position has probably not been sampled: its entropy, corrected or not, rests on an incomplete picture. --min-coverage X flags positions with C ^ < X (below_min_coverage) and adds a warning; coverage is always reported. At MERS-CoV spike position 25, f 1 = 4 and f 2 = 0 , so C ^ = 1 − 4 170 ⋅ 507 509 = 0.9766 .

A position where no sequence has a valid k-mer (NS) has no variants and therefore no distribution: its entropy is not 0 bits, it is undefined. The paper assigns such positions a “pseudo entropy” of 0, tagged NS so that it is not mistaken for conservation, and leaves them out of its summaries (Fig. 2; Methods) (Tharanga et al. 2025). DiMA departs from the paper here, deliberately: it keeps the NS tag but writes null in JSON and NA in the tables, with entropy_method not_estimable, and also leaves NS positions out of the summary statistics. This follows the treatment of missing data in statistics and in the field: a value that was not observed is recorded as missing, not as zero (Rubin 1976; Schafer & Graham 2002); in sequence count data, zeros that arise from absent sampling are not the same as true zeros (Silverman et al. 2020; Lazar et al. 2016); conservation scores leave columns dominated by gaps unscored rather than calling them conserved (Capra & Singh 2007); and tidy data use an explicit missing-value code (Broman & Woo 2018).

A 0 in the output would also be averaged as a real value by any later summary that does not filter on the tag, biasing it towards conservation. On the paper’s HIV-1 pol dataset (680 NS positions) the mean over all positions with NS counted as 0 — DiMA v5.0.9’s rule, still reported as all_positions_summary for comparison — is 3.443 bits, against 5.350 bits over the eligible positions.

Logarithms come from the libm library, so they give the same bits on every platform; sums use compensated (Neumaier) summation; each position is computed by one thread and summaries are reduced in position order. Identical inputs therefore give byte-identical outputs.

Rounding error is present in every value, as in any floating-point program, and grows with the number of sequences at a position. On the bundled datasets it is within about 5 × 10 − 15 of the exact values (relative), and at the 2.2 million sequences per position of the paper’s SARS-CoV-2 analysis within 2.2 × 10 − 12 . That is 10 10 to 10 12 times smaller than the sampling error of the estimate. Numerical accuracy gives the measurements, the one limit (more than 9 × 10 15 sequences at a position) and why a prototyped fix for the last digits is deferred.

  • Blackwell D. Conditional Expectation and Unbiased Sequential Estimation. The Annals of Mathematical Statistics. 1947;18(1):105-110. doi:10.1214/aoms/1177730497 ↩︎
  • Broman KW, Woo KH. Data Organization in Spreadsheets. The American Statistician. 2018;72(1):2-10. doi:10.1080/00031305.2017.1375989 ↩︎
  • Capra JA, Singh M. Predicting functionally important residues from sequence conservation. Bioinformatics. 2007;23(15):1875-1882. doi:10.1093/bioinformatics/btm270 ↩︎
  • Chao A, Jost L. Coverage-based rarefaction and extrapolation: standardizing samples by completeness rather than size. Ecology. 2012;93(12):2533-2547. doi:10.1890/11-1952.1 ↩︎
  • Chao A, Wang YT, Jost L. Entropy and the species accumulation curve: a novel entropy estimator via discovery rates of new species. Methods in Ecology and Evolution. 2013;4(11):1091-1100. doi:10.1111/2041-210X.12108 ↩︎
  • Efron B. Bootstrap Methods: Another Look at the Jackknife. The Annals of Statistics. 1979;7(1):1-26. doi:10.1214/aos/1176344552 ↩︎
  • Good IJ. The Population Frequencies of Species and the Estimation of Population Parameters. Biometrika. 1953;40(3/4):237-264. doi:10.2307/2333344 ↩︎
  • Hunter-Zinck H, de Siqueira AF, Vásquez VN, Barnes R, Martinez CC. Ten simple rules on writing clean and reliable open-source scientific software. PLOS Computational Biology. 2021;17(11):e1009481. doi:10.1371/journal.pcbi.1009481 ↩︎
  • Khan AM, Miotto O, Nascimento EJM, Srinivasan KN, Heiny AT, Zhang GL, Marques ET, Tan TW, Brusic V, Salmon J, August JT. Conservation and Variability of Dengue Virus Proteins: Implications for Vaccine Design. PLoS Neglected Tropical Diseases. 2008;2(8):e272. doi:10.1371/journal.pntd.0000272 ↩︎
  • Khan AM, Hu Y, Miotto O, Thevasagayam NM, Sukumaran R, Abd Raman HS, Brusic V, Tan TW, August JT. Analysis of viral diversity for vaccine target discovery. BMC Medical Genomics. 2017;10(S4):78. doi:10.1186/s12920-017-0301-2 ↩︎
  • Lazar C, Gatto L, Ferro M, Bruley C, Burger T. Accounting for the multiple natures of missing values in label-free quantitative proteomics data sets to compare imputation strategies. Journal of Proteome Research. 2016;15(4):1116-1125. doi:10.1021/acs.jproteome.5b00981 ↩︎
  • Miller GA. Note on the bias of information estimates. In: Information Theory in Psychology: Problems and Methods (Quastler H, ed.), Free Press, Glencoe, IL. 1955. p. 95-100. ↩︎ 1 2
  • Miotto O, Heiny AT, Tan TW, August JT, Brusic V. Identification of human-to-human transmissibility factors in PB2 proteins of influenza A by large-scale mutual information analysis. BMC Bioinformatics. 2008;9(S1):S18. doi:10.1186/1471-2105-9-S1-S18 ↩︎
  • Paninski L. Estimation of Entropy and Mutual Information. Neural Computation. 2003;15(6):1191-1253. doi:10.1162/089976603321780272 ↩︎
  • Panzeri S, Senatore R, Montemurro MA, Petersen RS. Correcting for the Sampling Bias Problem in Spike Train Information Measures. Journal of Neurophysiology. 2007;98(3):1064-1072. doi:10.1152/jn.00559.2007 ↩︎
  • Rao CR. Information and the accuracy attainable in the estimation of statistical parameters. Bulletin of the Calcutta Mathematical Society. 1945;37:81-91. ↩︎
  • Rubin DB. Inference and missing data. Biometrika. 1976;63(3):581-592. doi:10.1093/biomet/63.3.581 ↩︎
  • Schafer JL, Graham JW. Missing data: Our view of the state of the art. Psychological Methods. 2002;7(2):147-177. doi:10.1037/1082-989x.7.2.147 ↩︎
  • Shannon CE. A Mathematical Theory of Communication. Bell System Technical Journal. 1948;27(3):379-423. doi:10.1002/j.1538-7305.1948.tb01338.x ↩︎
  • Silverman JD, Roche K, Mukherjee S, David LA. Naught all zeros in sequence count data are the same. Computational and Structural Biotechnology Journal. 2020;18:2789-2798. doi:10.1016/j.csbj.2020.09.014 ↩︎
  • Strong SP, Koberle R, de Ruyter van Steveninck RR, Bialek W. Entropy and Information in Neural Spike Trains. Physical Review Letters. 1998;80(1):197-200. doi:10.1103/PhysRevLett.80.197 ↩︎
  • Tharanga S, Ünlü ES, Hu Y, Sjaugi MF, Çelik MA, Hekimoğlu H, Miotto O, Öncel MM, Khan AM. DiMA: sequence diversity dynamics analyser for viruses. Briefings in Bioinformatics. 2025;26(1):bbae607. doi:10.1093/bib/bbae607 ↩︎ 1 2 3 4
  • Wilson G, Aruliah DA, Brown CT, Chue Hong NP, Davis M, Guy RT, Haddock SHD, Huff KD, Mitchell IM, Plumbley MD, Waugh B, White EP, Wilson P. Best Practices for Scientific Computing. PLoS Biology. 2014;12(1):e1001745. doi:10.1371/journal.pbio.1001745 ↩︎