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.".
...
More information:
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.".
...
Recommendation: Please read that document for more information.
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.
