Shannon.codon: An R package for the analysis of codon frequencies

A summary of Claude Shannon Information Theory OCTAVIO MART´ INEZ COMPUTATIONAL BIOLOGY LABORATORY, CINVESTAV - IRAPUATO, M´ EXICO. Abstract. This is a commented summary of Shannon’s Information Theory, which is centered in the definition of entropy (H) for a set of events. It is shown that entropy is an average of uncertainties weighted by the probabilities of observing each element of the set. By considering two sets of events different uncertainty measures can be considered. Entropy formulas are presented in a notation which clarifies the equations meaning, and the correspondence with Shannon’s notation is also given. Following Adami’s concepts, it can be concluded that measures of information are obtained from differences of uncertainties. Final sections presents examples which hopefully will clarify the concepts, helping to the interpretation of numerical results. What’s a message, really? Claude Shannon recognized that the elemental ingredient is surprise. How Shannon Entropy Imposes Fundamental Limits on Communication. Quanta magazine (Hartnett, 2022). Note. This is an Internal Report of the Laboratory of Computational Biology at the Unit of Advanced Genomics (Unidad de Gen´omica Avanzada, UGA, in Spanish) of Cinvestav. Content 1. Shannon’s entropy 1 1.1. Shannon’s entropy as a weighted average of uncertainties 2 2. Considering two sets of events 3 2.1. Conditional entropy 5 2.2. Mutual information 5 2.3. Summarizing main equations 6 3. Examples and interpretation 8 3.1. Climbing the ladder of information 9 3.2. A numerical example in a different context 10 References 12 1. Shannon’s entropy The seminal paper of Claude E. Shannon, (Shannon, 1948), is entitled “A mathematical theory of communication”, and not a “A mathematical theory of information”. The word “information” is found in 25 pages of his paper, while “communication” appears only in 9 pages. Was Shannon intending to use “information” as a synonymous of “communication”? That is dubious. Shannon’s primary goal was to develop a mathematical theory of communication, focusing on the statistical properties of signals and their transmission. He was concerned with the efficiency and reliability of transmitting messages, not with their meaning. In fact, in the second paragraph of his paper introduction he wrote · · · Frequently the messages have meaning; that is they refer to or are correlated according to some system with certain physical or conceptual entities. These semantic aspects of communication are irrelevant to the engineering problem. Date: April 25, 2025. 1 2Shannon’s Information Theory In everyday language “information” generally refers to knowledge or facts, for example, “I need information about the weather in Japan”; the Merriam-Webster dictionary first definition of information is “knowledge obtained from investigation, study, or instruction”, while the Oxford English Dictionary gives many entries for information, being the first of them “The imparting of knowledge in general.”. Clearly those definitions in common parlance have nothing to do with Shannon’s definition of Entropy, H=− n X i=1 pilog2(pi) where p1, p2,· · · , pnare probabilities of occurrences of “choices”1–which can also be interpreted as symbols of an alphabet. Shannon presents the formula for Hin the Theorem 2 of the section “6. CHOICE, UNCERTAINTY AND ENTROPY” of his paper, demonstrating in an appendix that Hsatisfies the properties (1) of being continuous in the pi’s, (2) that if all pi= 1/n then His a monotonic increasing function of nand (3) that if a choice be broken down into two successive choices, the original Hshould be the weighted sum of the individual values of H(see the example in Shannon (1948)). He begins the mentioned section with the question, “Can we define a quantity which will measure, in some sense, how much information is “produced” by (a Markoff process), or better, at what rate information is produced?” The key here is the use of the qualification “in some sense” –meaning that the association of “entropy” with “information” must be clarified. The word “entropy” for Hwas selected by Shannon because in physics the Boltzmann’s entropy formula measures the disorder, uncertainty or randomness of a system. According to some accounts, John von Neumann advised Shannon to use the term “entropy” suggesting that “No one knows what entropy really is, so in a debate you will always have the advantage”. We do not for sure if that anecdote is true, but in essence Shannon chose the word “entropy” because it was a mathematically and conceptually appropriate term that already existed, and provided an accurate description of the measurement that he developed. It is important to underline that in an strict sense entropy, H, is not arandom variable, because given a set of probabilities, {pi}Ppi= 1, His a single, fixed value that quantifies the average uncertainty associated with that specific probability distribution, and, moreover, there is no need at all that the collection of events to which individual probabilities are assigned must be numeric 2. 1.1. Shannon’s entropy as a weighted average of uncertainties. Entropy, H, can be accurately described as a weighted average of uncertainties, reserving the word “information” to differences between H’s –which will be discuss later. In essence, each “choice” (symbol) contribution to the total entropy is its probability, “pi” multiplied by the uncertainty associated with that symbol, which is measured as “−log2(pi)”, completing the formula of Shannon’s Hgiven above. This description avoids the often confusing association between entropy with “information”, which can lead to misinterpretations. Figure 1 presents the plots of uncertainty, −plog2(p) (panel A), and entropy , H(panel B), as function of pin the simplest case where there are only two choices (symbols) with probabilities, pand q= 1−p. In panel A of Figure 1 the limit of the uncertainty, −log2(p), when ptends to 0 by the right hand side diverges to infinite, however we take the limit of the product −plog2(p) to be zero, say lim p→0−plog2(p)=0 The use of a logarithmic scale to measure uncertainty makes sense; an event highly unlikely must have large uncertainty, while an event that occurs with high probability must produce a low level of “surprise”. The use of a particular base for the logarithm simply fixes the scale of measurement; by selecting a base 2 in −log2(p) we agree to measure uncertainty in binary choices, i.e., in bits. 1I omitted the constant Kand used log2to measure the uncertainty in bits. 2In contrast, random variables always assign probabilities to numbers. 3Shannon’s Information Theory 0.0 0.2 0.4 0.6 0.8 1.0 0123456 p −log2(p) (uncertainty) (a) X:p;Y:−log2(p) 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 p H (entropy; weighted average of uncertainties in bits) (b) X:p;Y:H=−plog2(p)−qlog2(q) Figure 1. Line plots of uncertainty, −log2(p) (panel A), and entropy , H(panel B), as function of pin the case of two probabilities, pand q= 1 −p. Panel B as Fig. 7 in Shannon (1948). In panel A of Figure 1 we can see how the continuous function −log2(p), in the Yaxis varies for different values of p, in the Xaxis, diverging to infinity as p→0. Small values of pproduce high uncertainty, and as pincreases that quantity smoothly decreases, reaching its minimum value of 0 for events that are certain, i.e, for the case when p= 1. Weighting uncertainty by the corresponding probabilities –in this case we have only two choices or symbols, thus probabilities are pand q= 1 −p, we obtain the values of H=−plog2(p)−qlog2(q), shown in panel B of Figure 1. The same plot, p×Hwas originally presented as “Fig. 7” in Shannon (1948), underlying the fact that the maximum value of H= 1 bit is reached at the point of maximum uncertainty, p= 0.5 It is worth noticing that plotting the values of Hin the general case where we have n > 2 choices or symbols is impossible, because then H=−Ppilog2(pi) maps points from the n-dimensional space (p1, p2,· · · , pn) to a single value of entropy, say, H(p1, p2,· · · , pn)≥0, in the real line of one dimension. In general we have that the maximum value of H, max(H) = log2(n) bits, is reached at the point of maximum average uncertainty, pi= 1/n for all i= 1,2,· · · , n, while the minimum value H= 0 happens when a single pi= 1 and thus all other values of piare zero, a circumstance where no uncertainty exist. 2. Considering two sets of events Here we adapt the notation employed by Shannon, giving the correspondences in a more explicit way that pretends to avoid misinterpretations –even if the change of notation is more verbose. His defined for a set of events, which Shannon initially call choices and that for the discrete case are, in fact, letters in a given alphabet which constitute the average messages studied by his communication theory. Let’s Xbe a collection of events, which in principle does not need to be in a particular order, 4Shannon’s Information Theory but to simplify we will consider them to be in the order from 1 to m, say (1) X={x1, x2,· · · , xm} In this notation each xiis a particular instance of a set of events, X, which collects all possible results of a random experiment. Associated with Xwe have a probability function, P[X=xi] = pi, i.e., the probability to obtain xias the result of the random experiment, and of course pi≥0 and Pipi= 1. With this notation we can write the average uncertainty associated with X, i.e., its entropy, as (2) H(X) = − i=m X i=1 P[X=xi] log2(P[X=xi]) = − i=m X i=1 pilog2(pi) The use of the capital Xin H(X) stresses the fact that we have a particular collection of results, X, and an associated probability function, P[X=xi]. It is important to note that the use of the subindex iis arbitrary in the sense that its only function is to label all the mpossible instances of the elements of X, but Hdoes not depends on the order in which the elements of Xare listed, for example, X({x1, x2, x3})≡X({x2, x1, x3}), etc. Now let’s consider a different collection of events, say Y, (3) Y={y1, y2,· · · , yn} and assume that we have the joint probability function (4) pij =P[(X=xi)∩(Y=yj)], i = 1,2,· · · , m;j= 1,2,· · · , n which fulfills pij ≥0 and PiPjpij = 1. Now we can define the average join uncertainty of the pair (X, Y ) as (5) H(X, Y ) = − i=m X i=1 j=n X j=1 pij log2(pij ) Shannon refers to equation (5) as the “entropy of the joint event”, and in his notation H(X, Y ) is defined as H(x, y) = −X i,j p(i, j) log p(i, j) which of course is equivalent to equation (5), but we prefer to use capital letters for the collections of events and subindexes in the probabilities. Shannon also shows that (6) H(X, Y )≤H(X) + H(Y) with equality holding only if the collections of events Xand Yare independent, i.e., only when pij =pipj for all pairs i, j. In that particular case we have that equation (5) can be written as H(X, Y ) = −X i X j pipjlog2(pipj) =−X i X j pipj(log2(pi) + log2(pj)) =−X i pilog2(pi)−X j pjlog2(pj) =H(X) + H(Y) 5Shannon’s Information Theory 2.1. Conditional entropy. Independence of Xand Yis of course not granted; there are many situations of interest where the collections of events could be highly dependent. To study such cases we need conditional probabilities, say P[Y=yj|X=xi] = P[Y=yj∩X=xi] PjP[Y=yj∩X=xi] =P[Y=yj∩X=xi] P[X=xi] =pj|i which Shannon writes as pi(j) = p(i, j) Pjp(i, j) Using conditional probabilities Shannon then defines the “conditional entropy of y,Hx(y)as the average of the entropy of yfor each value of x, weighted according to the probability of getting that particular x”. In his notation, Hx(y) = −Pi,j p(i, j) log2(pi(j)) =−Pi,j p(i, j) log2(p(i, j)) + Pi,j p(i, j) log2(Pjp(i, j)) =H(x, y)−H(x) which in our notation we write as (7) H(Y|X) = H(X, Y )−H(X) which implies that H(X, Y ) = H(X) + H(Y|X) and conditioning Xto Ywe symmetrically obtain H(X|Y) = H(X, Y )−H(Y), which implies that H(X, Y ) = H(Y) + H(X|Y). In words, H(Y|X) represents the average uncertainty that remains about the set Ywhen the state of Xis known. If Xand Yare independent then H(X, Y ) = H(X) + H(Y) and in that particular case H(Y|X) = H(X) + H(Y)−H(X) = H(Y), meaning that the average uncertainty of Yis not altered by knowledge of X. 2.2. Mutual information. Mutual information for two sets of events, Xand Y, is defined as (8) I(X;Y) = −PiPjpij log2(pij pipj) =H(X)−H(X|Y) =H(Y)−H(Y|X) =H(X;Y) Mutual information, also known as the Kullback-Leibler divergence, is denoted either as H(X;Y) or I(X;Y) –depending on the source. That is why lines 1 and 4 in equation (8) presents both versions of the notation. Here we prefer to use I(X;Y), because it mnemonically suggest the “Intersection” of entropies and also avoids possible confusion with H(X, Y ) –the join uncertainty of the pair (X, Y ). In words, I(X;Y)≥0 measures the average uncertainties common to the two sets, and the equality, I(X;Y) = 0, occurs only when the joint probabilities are identical to the product of the marginals, pij =pipj, that is, when Xand Yare independent. 6Shannon’s Information Theory 2.3. Summarizing main equations. An important property of measures of uncertainties, H’s, is that they depend from the events Xand Yonly through their join probabilities —which are usually estimated as relative frequencies of occurence. Thus, if we have two sets of events, say Xwith moptions and Ywith npossible values, the only data that we need to calculate H’s are the conjoint probabilities, PX,Y=P[(X=xi)∩(Y=yj)] i= 1,2,· · · , m;j= 1,2,· · · , n and those values, PX,Y, can be arranged into a matrix of mrows by ncolumns, say P[(X=x1)∩(Y=y1)], P[(X=x1)∩(Y=y2)],· · · , P[(X=x1)∩(Y=yn)] P[(X=x2)∩(Y=y1)], P[(X=x2)∩(Y=y2)],· · · , P[(X=x2)∩(Y=yn)] · · · P[(X=xm)∩(Y=y1)], P[(X=xm)∩(Y=y2)],· · · , P[(X=xm)∩(Y=yn)] Note that by adding by columns or by rows the elements of that matrix we can obtain the marginal probabilities, say PX=P[X=xi] = j=n X j=1 P[(X=xi)∩(Y=yj)] and PY=P[Y=yj] = i=m X i=1 P[(X=xi)∩(Y=yj)] In equations (1) and (3) we defined Xand Y, respectively, as sets and not as vectors, i.e., using braces, { }, and not parentheses, ( ). In sets the order in which the elements are presented does not matter; the set X={x1, x2, x3}can also be represented by any permutation of the three elements, for example, X={x1, x2, x3}={x3, x2, x1}, etc. Given that Hmeasures depend on the events only through the probabilities, PX,Y=P[(X=xi)∪(Y=yj)] where xi, yjare events (and not necessarily numbers), in an strict sense we do not have random variables but only collections of events (sets) with well defined probability measures fulfilling P[(X=xi)∩(Y=yj)] ≥0 i=m X i=1 j=n X j=1 P[(X=xi)∩(Y=yj)] = 1 i=m X i=1 P[X=xi]=1 and j=n X j=1 P[Y=yj]=1 Thus, rewriting more explicitly the equation that define the Hvalues we have (9) H(X, Y ) = H(PX,Y) = − i=m X i=1 j=n X j=1 P[(X=xi)∩(Y=yj)] log2(P[(X=xi)∩(Y=yj)]) (10) H(X) = H(PX) = − i=m X i=1 P[X=xi] log2(P[X=xi]) 7Shannon’s Information Theory (11) H(Y) = H(PY) = − j=n X j=1 P[Y=yj] log2(P[Y=yj]) (12) H(X|Y) = H(X, Y )−H(Y) (13) H(Y|X) = H(X, Y )−H(X) (14) I(X;Y) = H(X)−H(X|Y) = H(Y)−H(Y|X) In the summary presented by equations (9) to (14) we see that only three measures, H(X, Y ), H(X) and H(Y) are initially needed; the remaining quantities, H(X|Y), H(Y|X) and I(X;Y) are lineal combinations of the former. Figure 2 presents a Venn diagram of relations between entropies. Figure 2. Venn diagram showing entropy related measures for two collection of sets, X and Y. Source: KonradVoelkel (Own work, Public Domain). Figure 2 schematically shows the relations between H’s. The areas of the two circles represent the relative sizes of H(X) and H(Y) –at the left and right hand sides, respectively. In the figure the two areas are identical, H(X) = H(Y), but of course, both, the sizes and positions of the circles can be varied to produce an accurate description of a particular situation; we must use our imagination for that. By sliding the circles we can vary the areas of the disjoint events. For example, the intersection of H(X) with H(Y) represents mutual information, I(X;Y), and we can make it to be zero by drawing the two circles separately (with no intersection) or make it as large as the largest of the two circles, when one circle is a subset of the other in the Venn diagram, etc. The scheme represents accurately conditional uncertainties, H(X|Y) and H(Y|X), as set differences which map to equation (12) and (13), respectively. 8Shannon’s Information Theory 3. Examples and interpretation “And Trump and his senior officials repeatedly parroted Russian disinformation about the conflict, including by blaming it on Kyiv. Alexander Gabuev, Foreign Affairs, 26 Mar. 2025. It appears reasonable to say that we gain information when we obtain a response to a given query. We will limit the universe of possible queries to the ones that could be answered by a probabilistic statement about a finite set of responses3, noting that probabilistic does not always means indeterminate; a probability of one for an event means that it will surly happen, while a probability of zero means that such event is considered to be impossible. Even in such restricted context we could have definition problems; for example, assume that for a specific case we know that there is a finite number of possible responses to the query, but we do not know (with certainty) which that number is. In that case the number of possible responses, min the set defined by equation (1), is unknown and thus we cannot write or find a vector of probabilities, P[X=xi], because its own dimension (length) is unknown. Technically in that case we will have that the dimensionality of the parameter space is unknown, preventing us to give any measurement to the quantity of information that we have –or more correctly, to the quantity of information that we need to obtain; in that case we will be in a state of full disinformation. Let’s go back to queries where the number of possible responses is known, and consider the following Query 1: Is it going to be a earthquake of intensity >5 in my city tomorrow? That query has only two possible answers, ‘Yes’ or ‘No’, being an example of the simplest set X, say the binary X={Yes, No}, which vector of probabilities can be written as Px= (p, 1−p) where pstands for the probability of the event “a earthquake of intensity >5will happen in my city tomorrow”. Clearly, a single bit of information is enough to answer this binary query and, as shown in panel (B) of Figure 1, the maximum average uncertainty happens when p= 1/2, this is Hmax(X) = log2(2) = 1. In general, when the query can have mdifferent answers we have that Hmax(X) = log2(m) and this value is reached at the point where pi= 1/m, i = 1,2,· · · , m; i.e., when all mprobabilities are identical; an state that is equivalent to maximal disinformation. In panel (A) of Figure 1 we saw that when pis close to zero, the uncertainty, −log2(p), is large; in fact, we can obtain arbitrarily large values of uncertainty by going close enough to p= 0. Going back to the query (Query 1), how much information do I have? Note that by the binary nature of the query at least I know that I need only one bit of information (that is, I am asking for a definite ‘Yes’ or ‘No’ answer). My state of average uncertainty is maximum, numerically Hmax =H(Query 1) = 1 bit. I consult a reliable source of geological data finding that in average in my city there is a earthquake of intensity >5 every 10 years. Thus now I know that p= 1/(365 ×10) ≈0.0003, fortunately a unusual event. the question is how much information I gained by having a reliable estimate of p; we calculate, H(X) = −plog2(p)−(1 −p) log2(1 −p)≈0.0039 This means that my average uncertainty have decreased from the original 1 bit to only a very small fraction of a bit, 0.0039; thus I obtained 1 −0.0039 = 0.9961, i.e., I have now almost a bit of information. In general it is reasonable to define information as a difference of entropies, before and after having estimates of probabilities that are different to the assuming that all options are equally likely (pi= 1/m for every one of the mresults), I(p) = Hmax −H(X) = log2(m)−H(X) where H(X) is the entropy of the vector of probabilities, p. 3This excludes open queries which could have a priory an infinite number of different responses 9Shannon’s Information Theory Christoph Adami has discussed at length the definition of “information”, concluding in general terms that information can be measured as differences of entropies. I do not resist the temptation to quote some phrases from the opinion piece “What is information?” (Adami, 2016), which help to reflect about this topic, “Entropy, in case you have not yet come across the term, is just a word we use to quantify how much is not known.” · · · “I suggest to the reader to give up thinking about the uncertainty of any physical object, and to be concerned only with differences between uncertainties (before and after a measurement, for example). The uncertainties themselves we call entropy.” · · · “Differences between entropies are called information. Information, you see, is real. Entropy on the other hand, is in the eye of the beholder.” · · · “Information is: ‘What you don’t know minus what remains to be known given what you know’.” · · · “people are confused about what to call entropy, and what to call information.” Adami (2016). He has also made important contributions to the application of Shannon’s information theory to Biology; see for example Adami (2004, 2024). 3.1. Climbing the ladder of information. Let’s postulate an artificial example to illustrate how, by changing the source, we can obtain different quantities of information. Assume that I want to obtain information about the following query: Q2: Which is the last DNA base in the gene that codes for the human histone H2A protein? Of course, in this era of information the answer is easy to obtain; just go to the NCB nucleotide database in the address Homo sapiens histone H2A. However, we will take a more twisted pathway to reflect on how we can gain information by consulting different sources (with an increasing knowledge of the context). Assume that I ask the question Q2 to the first person that I find in the street. Apart of risking to be taken by a loony, a likely response is something like “I do not have the slightest idea!” (unless I found a person acquainted with molecular biology). Given the response “I do not have the slightest idea!” to Q2 it appears reasonable to say that such response does not produce any information; we can write I0(Q2) = 0, to denote the fact that at this “step 0” of our inquiry we gained no information at all. Can we justify the assignation “I0(Q2) = 0” in terms of entropies? —of course, this has only theoretical but not practical importance; it does not appear rational to challenge the fact that we do not gained anything by the response (or “not-response” if you like). Let’s go one step further by assuming that we ask Q2 to a person that knows that the DNA is formed by 4 different bases, A, T, G, C. The response of that person to Q2 will be something like “There must be one of the four bases, but I do not know which one”. Now we can write the expression for the average uncertainty associated with Q2 as a function of the probabilities PX= (P[x=A], P[x=T], P[x=G], P[x=C]), i.e., the average uncertainty of interest is H(PX) and we did not needed to put a sub-index in xbecause the response is a single letter. At this point we can argument that the our average uncertainty is the maximum possible when we have a set of 4 letters (events); that is, we know know that the response to Q2 must be one of the 4 DNA bases, thus Hmax(PX) = H(1/4,1/4,1/4,1/4) = log2(4) = 2 That is, by knowing only that the response to Q2 must be one of four possible, we received information, say I1(Q2) = Hmax(PX)−I0(Q2)=2−0=2 Or citing Adami (2016) again, “Information is: ‘What you don’t know minus what remains to be known given what you know’”. In summary, at this step we know that we will need 2 bits of information to fully solve Q2 (at least we know how much do we need to know!).