Why would perfectly similar data have 0 mutual information?

I'm not a statistic major, so my knowledge of statistics is quite limited but I've found myself in need of learning about and using mutual information. I believe I understand the concept and formula, but it seems counter-intuitive that perfectly similar data would have 0 mutual information. I would expect two sets of data with perfect similarity to have mutual information of 1.

I'm writing a program which calculates Mutual Information between two columns (i and j) in a pairwise protein sequence, and I'm not sure if I should manually fix the MI to be 1 if the columns are exactly the same. For example, if the two columns (written as lines) were:

CLLYFFDTTQGILMIGCL
IILLIIIIFLIVILVIFV


Then I've calculated the MI by hand to be equal to 0.8384. However, if the two columns (written as lines) were:

GGGGGGGGGG
GGGGGGGGGG


The mutual information will be equal to 0 because the formula will result in:

$$\sum \left( p(1) \times \log \left( \frac{p(1)}{p(1) p(1)} \right) \right) = 1 \times \log \left( \frac{1}{1} \right) = 0$$

In my program I have it check if the columns are identical (i = j) and just manually assign Mi = 1. So I'm wondering: Is this bad practice? Does it only consider one possible case of many? Should I not do this at all? The professor I'm working with suggested I incorporate a pseudo-count for every other non-existing amino acid and ignoring a manual fix for when i = j.

Would a pseudo-count fix this? Counting each existing amino acid as 1.1 and everything else as 0.1, or would it result in the same mutual information? Again, I'm far from a statistics major so if you can explain simply, that would be best. Thanks.

Mutual information $I(X, Y)$ can be thought as a measure of reduction in uncertainty about $X$ after observing $Y$:

$$I(X, Y) = H(X) - H(X|Y)$$

where $H(X)$ is entropy of $X$ and $H(X|Y)$ is conditional entropy of $X$ given $Y$. By symmetry it follows that

$$I(X, Y) = H(Y) - H(Y|X)$$

However mutual information of a variable with itself is equal to entropy of this variable

$$I(X, X) = H(X)$$

and is called self-information. This is true since $H(X|Y) = 0$ if values of $X$ are completely determined by $Y$ and this is true for $H(X|X)$. It is so because entropy is a measure of uncertainty and there is no uncertainty in reasoning on values of $X$ given the values of $X$, so

$$X(X) - X(X|X) = X(X) - 0 = H(X)$$

This is immediately obvious if you think of it in terms of Venn diagrams as illustrated below.

You can also show this using the formula for mutual information and substituting the conditional entropy part, i.e.

$$H(X|Y) = \sum_{x \in X, y \in Y} p(x, y) \log \frac{p(x,y)}{p(x)}$$

by changing $y$'s into $x$'s and with recalling that $X \cap X = X$, so $p(x, x) = p(x)$. [Notice that this is an informal argumentation, since for continuous variables $p(x, x)$ would not have a density function, while having cumulative distribution function.]

So yes, if you know something about $X$, then learning again about $X$ gives you no more information.

Check Chapter 2 of Elements of Information Theory by Cover and Thomas, or Shanon's original 1948 paper itself for learning more.

As about your second question, this is a common problem that in your data you do observe some values that possibly can occur. In this case the classical estimator for probability, i.e.

$$\hat p = \frac{n_i}{\sum_i n_i}$$

where $n_i$ is a number of occurrences of $i$th value (out of $d$ categories), gives you $\hat p = 0$ if $n_i = 0$. This is called zero-frequency problem. The easy and commonly applied fix is, as your professor told you, to add some constant $\beta$ to your counts, so that

$$\hat p = \frac{n_i + \beta}{(\sum_i n_i) + d\beta}$$

The common choice for $\beta$ is $1$, i.e. applying uniform prior based on Laplace's rule of succession, $1/2$ for Krichevsky-Trofimov estimate, or $1/d$ for Schurmann-Grassberger (1996) estimator. Notice however that what you do here is you apply out-of-data (prior) information in your model, so it gets subjective, Bayesian flavor. With using this approach you have to remember of assumptions you made and take them into consideration.

This approach is commonly used, e.g. in R enthropy package. You can find some further information in the following paper:

Schurmann, T., and P. Grassberger. (1996). Entropy estimation of symbol sequences. Chaos, 6, 41-427.

• I do not think that it is true to say $p(x,x)=p(x)$. The random variable $(X,X)$ does not have a probability density function with respect to Lebesgue since its support is in the diagonal which has 0 Lebesgue measure.
– Sina
Commented Aug 29, 2017 at 12:47
• @Sina it does not have density function, but it exists and has CDF, see e.g. math.stackexchange.com/questions/1749370/… [Edited to comment on that.]
– Tim
Commented Aug 29, 2017 at 13:10
• I agree and it puzzles me because how do you define (differential) entropy in terms of cumulative distribution function? I think it is not straight forward and there are papers written on the topic: cise.ufl.edu/~fewang/SamplePub/JIT2004.pdf
– Sina
Commented Aug 29, 2017 at 13:37
• @Sina you can't, as I noted in my edit, this is an informal argument.
– Tim
Commented Aug 29, 2017 at 13:39
• Entropy for $p(x_i)=0$ is 0 using the limit. No need to add arbitrary constants.
– user289381
Commented Jul 7, 2020 at 10:12

To complement Tim's answer with a short and direct answer to your original question: No, similar data do not necessarily have 0 Mutual Information. They only do if they are constant..

Indeed if they are fully identical, their mutual information will be equal to the entropy of any of the two: $$I(X, X) = H(X)$$. This entropy is only zero in case of constant data, otherwise it may have other values.

Why would perfectly similar data have 0 mutual information?

The amount of 'alignment information' the algorithm can offer is zero. Nothing to align.

... and I'm not sure if I should manually fix the MI to be 1 if the columns are exactly the same.

No.

MI is an unreliable predictor of spatial proximity in proteins.

See: "Multilevel functional genomics data integration as a tool for understanding physiology: a network biology perspective", (Feb 1 2016), by Peter K. Davidsen, Nil Turan, Stuart Egginton, and Francesco Falciani

"An MI value of zero means that there is no dependency (i.e., no information flow) between two variables, whereas an MI value of 1 indicates a perfect association between them, and, therefore, a likely strong regulatory interaction between them.".

See: Correction for phylogeny, small number of observations and data redundancy improves the identification of coevolving amino acid pairs using mutual information", (Mar 10 2009), by Cristina Marino Buslje, Javier Santos, Jose Maria Delfino, and Morten Nielsen

"From Equation (1) — that defines the MI between two sites in a Multiple Sequence Alignment (MSA) — it is apparent that diversity is essential to achieve high MI values. Only if all amino acids are present in equal frequencies between two perfectly coevolving pairs will the MI achieve its maximum value. This leads to the observation that fast evolving sites tend to have high values of MI albeit being non-coevolving (Gouveia-Oliveira and Pedersen, 2007). Likewise, slowly evolving sites will only occupy a small fraction of the amino acid space, and hence tend to have low MI values. The extreme case is perfectly conserved amino acids that will always have a MI value of zero. By introducing a correction for low count this behavior is altered.

...

2.2 The algorithm

The MI between two positions in an MSA is given by the relationship:

$$MI(i,j)=\sum_{a,b}P(a_i,b_j)\cdot\log \left(\!\frac{P(a_i,b_j)}{P(a_i)\!\cdot\!P(b_j)}\!\right)\tag{1}$$

where $$P(ai, bj)$$ is the frequency of amino acid $$a$$ occurring at position $$i$$ and amino acid $$b$$ occurring at position $$j$$ in the same sequence, $$P(ai)$$ is the frequency of amino acid $$a$$ at position $$i$$ and $$P(bj)$$ is the frequency of amino acid $$b$$ at position $$j$$. We introduced a very simple correction for low number of sequences. The amino acid frequencies, $$P(a, b)$$, are normalized from $$N(a,b)$$, the number of times an amino acid pair $$(a, b)$$ is observed at positions $$i$$ and $$j$$ in the MSA. From $$N(ai, bi)$$, $$P(ai, bj)$$ is calculated as $$(\lambda + N(ai, bj))/N$$, where:

$$N=\sum_{a,b}(\lambda + N(a, b)), \; P(a_i)\!=\!\sum_{b}P(a_i,b_j) \text{ and } P(b_j)\!=\!\sum_{a}P(a_i,b_j)$$

It is clear that for MSAs of limited size, a large fraction of the $$P(a_i, b_j)$$ values will be estimated from a very low number of observations, and their contribution to MI could be highly noisy. To deal with such low counts, a parameter $$\lambda$$ is introduced. The initial value for the variable $$N(a_i, b_j) = \lambda$$ is set for all amino acid pairs. Only for MSAs with a small number of sequences, where a large fraction of amino acid pairs remain unobserved, will $$\lambda$$ influence the amino acids occupancy calculation. For large MSAs, most amino acid pairs will be observed at least once, and the influence of $$\lambda$$ will be minor. We investigated how the performance depended on the values used for $$\lambda$$ on a small independent dataset. We tested a range of values $$0–0.2$$ in steps of $$0.01$$. The maximal performance was achieved for a value of $$\lambda$$ equal to $$0.05$$, but similar results are obtained in the range $$0.025–0.075$$. This value was consistently found to be optimal for all datasets independently of size, evolutionary model, or rate of evolution (data not shown). When dealing with biological data, MSAs will often suffer from a high degree of unnatural sequence redundancy. It is hence expected that the sequence clustering would improve the accuracy of the MI calculation.".

...

4 Discussion and Conclusions

Here, we have compared two recently published approaches to lessen the influence of phylogeny and signal noise into the calculation of MI or coevolution between residues. Furthermore, we have shown how including simple techniques of sequence clustering and low count correction can significantly enhance the estimation of MI between residue pairs. Large-scale benchmarking including both artificial (in silico generated) and biological data demonstrated that this improved method could be applied to achieve accurate prediction of coevolving sites and contacts.

Our results demonstrate that raw MI was the worst predictor of coevolution. The RCW method of Gouveia-Oliveira and Pedersen (2007) outperformed MI. The APC background correction method by Dunn et al. (2008) achieved the highest performance. In this context, the inclusion of low count correction and clustering was shown to improve all three methods. The best performing method for both artificial and natural sequences was the combination of APC correction, clustering and low count correction.

We demonstrated that Z-score transformation calculated from sequence-based permutations significantly improved the prediction accuracy of the method, and allows an interpretation of predictions across different protein families. Further, we demonstrate how the predictive performance of the method depends strongly on the number of sequence clusters rather than the number of sequences in the MSA, and those MSAs with <400 clusters tend to display very low predictive performance values.".

...

Statistical calculations of mutual information for pairwise protein sequences differs from mutual information calculations for probability space statistics. MI is the expected value of the pointwise mutual information (PMI).

The protein primary structure has an alphabet of 20 naturally occurring amino acids and a conformation determined by folding.

From the supporting information of: "Identification of direct residue contacts in protein–protein interaction by message passing" (Jan 6 2009), by Martin Weigt, Robert A. White, Hendrik Szurmant, James A. Hoch, and Terence Hwa:

"MI is a local measure; it encounters only 1 residue pair at a time. MI is intrinsically unable to disentangle direct from indirect coupling. Consequently, prediction of spatial vicinity of interacting residues by MI is restricted. Therefore a global approach is proposed that will lead to the notation of direct information (DI). DI measures the part of MI that results from the direct coupling of residue pairs.".

...

Take for example this answer from John Coleman on Stack Overflow:

def MI(sequences,i,j):
sequences = [s for s in sequences if not '-' in [s[i],s[j]]]
Pi = Counter(s[i] for s in sequences)
Pj = Counter(s[j] for s in sequences)
Pij = Counter((s[i],s[j]) for s in sequences)

return sum(Pij[(x,y)]*log(Pij[(x,y)]/(Pi[x]*Pj[y])) for x,y in Pij)


Notice that it has shortcomings, but is easy to understand.

Mutual information for statistical analysis of pairwise protein sequences neglects the complicated three-dimensional structures of proteins and far-reaching consequences for the design and implementation of alignment algorithms. Consideration of structural constraints is particularly important in the treatment of gaps, a notion fundamental to sequence comparison.

What is Mutual Information?

Multiple Sequence Alignments (MSA) of homologues proteins can provide us with at least two types of information; the first one is given by the conserved amino acids at certain positions, while the other is given by the inter-relationship between two or more positions. Mutual Information (MI) from information theory can be used to estimate the extent of the mutual coevolutionary relationship between two positions in a protein family. Mutual information theory is often applied to predict positional correlations in a MSA to make possible the analysis of those positions structurally or functionally important in a given fold or protein family. For example, mutations of essential residues in a protein sequence may occur, only if a compensatory mutation takes place elsewhere within the protein to preserve or restore activity. Compensatory mutations are highly frequent and involve not only functional but also biophysical properties. Since evolutionary variations in the sequences are constrained by a number of requirements, such as maintenance of favorable interactions in direct residue-residue contacts, using the information contained in MSAs may be possible to predict residue pairs which are likely to be close to each other in the three-dimensional structure (Figure 1).

Figure 1. Representation of a MSA and the alpha-carbon structure of one protein of the alignment. Conserved and variable positions are highlighted in yellow. The positions that coevolved are highlighted in purple and light blue. The residues within these positions where change occurred are shown in pink and green. The arrows (middle) represent the interrelation of coevolution and structural information. This Figure is an adaptation of Figure 1 of (Marks et al., 2011).

Mutual Information is a measurement of the uncertainty reduction for a MSA of homologous proteins. The MI between two positions (two columns in the MSA) reflects the extent to which knowing the amino acid at one position allows us to predict the amino acid identity at the other position.

...

Intuitively, mutual information measures the information that $$X$$ and $$Y$$ share: It measures how much knowing one of these variables reduces uncertainty about the other. For example, if $$X$$ and $$Y$$ are independent, then knowing $$X$$ does not give any information about $$Y$$ and vice versa, so their mutual information is zero. At the other extreme, if $$X$$ is a deterministic function of $$Y$$ and $$Y$$ is a deterministic function of $$X$$ then all information conveyed by $$X$$ is shared with $$Y$$: knowing $$X$$ determines the value of $$Y$$ and vice versa. As a result, in this case the mutual information is the same as the uncertainty contained in $$Y$$ (or $$X$$) alone, namely the entropy of $$Y$$ (or $$X$$). Moreover, this mutual information is the same as the entropy of $$X$$ and as the entropy of $$Y$$. (A very special case of this is when $$X$$ and $$Y$$ are the same random variable).

Mutual information is a measure of the inherent dependence expressed in the joint distribution of $$X$$ and $$Y$$ relative to the joint distribution of $$X$$ and $$Y$$ under the assumption of independence. Mutual information therefore measures dependence in the following sense: $$I ⁡( X ; Y ) = 0$$ if and only if $$X$$ and $$Y$$ are independent random variables. This is easy to see in one direction: if $$X$$ and $$Y$$ are independent, then $$p_{(X,Y)}(x,y)=p_{X}(x)\cdot p_{Y}(y)$$, and therefore:

$$\log {\left({\frac {p_{(X,Y)}(x,y)}{p_{X}(x)\,p_{Y}(y)}}\right)}=\log 1=0.$$

Moreover, mutual information is nonnegative (i.e. $$I ⁡ ( X ; Y ) \ge 0$$ see below) and symmetric (i.e. $$I ⁡ ( X ; Y ) = I ⁡ ( Y ; X )$$ see below).

Nonnegativity

Using Jensen's inequality on the definition of mutual information we can show that $$I ⁡ ( X ; Y )$$ is non-negative, i.e.:

$$I ⁡ ( X ; Y ) ≥ 0$$

Symmetry

$$I ⁡ ( X ; Y ) = I ⁡ ( Y ; X )$$

Pointwise mutual information, Jensen–Shannon divergence, and Statistical coupling analysis are naive methods where the measurements are not independent.

Wikipedia: Direct Coupling Analysis - Direct Couplings and Indirect Correlation:

The central point of DCA is to interpret the $$J_{ij}$$ (which can be represented as a $$q\times q$$ matrix if there are $$q$$ possible symbols) as direct couplings. If two positions are under joint evolutionary pressure (for example to maintain a structural bond), one might expect these couplings to be large because only sequences with fitting pairs of symbols should have a significant probability. On the other hand, a large correlation between two positions does not necessarily mean that the couplings are large, since large couplings between e.g. positions $$i,j$$ and $$j,k$$ might lead to large correlations between positions $$i$$ and $$k$$, mediated by position $$j$$.[1] In fact, such indirect correlations have been implicated in the high false positive rate when inferring protein residue contacts using correlation measures like mutual information.[16]

[1] "Direct-coupling analysis of residue co-evolution captures native contacts across many protein families" (Oct 25 2011), by Faruck Morcos, Andrea Pagnani, Bryan Lunt, Arianna Bertolino, Debora S. Marks, Chris Sander, Riccardo Zecchina, José N. Onuchic, Terence Hwa, and Martin Weigt

[16] "Disentangling Direct from Indirect Co-Evolution of Residues in Protein Alignments", (Jan 1 2010), by Lukas Burger and Erik van Nimwegen

After the shortcomings of raw MI are corrected it can be used to guide other algorithms towards more accurate pairwise protein sequencing.

... Should I not do this at all? The professor I'm working with suggested I incorporate a pseudo-count for every other non-existing amino acid and ignoring a manual fix for when i = j.

That's a great hint.

The problem in the MI you're calculating isn't that the two columns are identical, rather that they're constants (or that you're effectively treating them as constants by estimating the probability of the vectors components with their empirical frequency in a vector that only has one value). Since the probability density of a constant is 0 everywhere but at a single value and 1 at that value, the MI between two constants is 0 (which is what you're seeing).

The mutual information between something and itself is the self-information (which makes sense intuitively as well as mathematically). It's not hard to show from definitions.

I don't really know your problem that well but it sounds like what you could do is estimate your probabilities a little better. Instead of taking $P(x_{i}=k) = \frac{num~of ~elements~ equal~ to ~k in~ your~ vector}{num~ of~ elements~ in ~your~ vector}$ you could take $P(x_{i}=k)= \frac{num~ of~ elements~ equal~ to~ k~ in~ your~ population}{num~ of~ elements~ in~ your~ population}$ . Of course, that's being naive and assuming that observations are independent and similar but if that's true you should be ok.

GGGGGGGGGG
GGGGGGGGGG


a zero Mutual Information (MI) is not caused because two variables are "perfectly similar'. In fact, being perfectly similar maximises the MI.

In that case, the reason for zero MI is something else: entropy of each variable ( H(X) or H(Y) ) is an upper bound for MI. But the entropy of each variable is zero. However, the upper bound of MI (the entropy of each variable) is zero. So, "despite" MI being maximal, under that constraint (zero), MI has to be zero.

In other words, if you look at the first variable, GGGGGGGGGG; it has zero entropy; it is a static works: there is no information. Hence, there is nothing to get shared between the variables.

Hence, the question is framed incorrectly. Your question is a "why" followed by an incorrect statement.

Intuitive summary:

An incorrect understanding:

• Similar variables $$\implies$$ MI is zero.

A correct understanding:

• Similar variables $$\implies$$ MI is maximal.
• No change in variables $$\implies$$ MI is minimal (MI is zero)