This article introduces the physics of information in the context of molecular biology and genomics. Entropy and information, the two central concepts of Shannon's theory of information and communication, are often confused with each other but play transparent roles when applied to statistical ensembles (i.e., identically prepared sets) of symbolic sequences. Such an approach can distinguish between entropy and information in genes, predict the secondary structure of ribozymes, and detect the covariation between residues in folded proteins. We also review applications to molecular sequence and structure analysis, and introduce new tools in the characterization of resistance mutations, and in drug design. In a curious twist of history, the dawn of the age of genomics has both seen the rise of the science of bioinformatics as a tool to cope with the enormous amounts of data being generated daily, and the decline of the theory of information as applied to molecular biology. Hailed as a harbinger of a "new movement" (Quastler 1953) along with Cybernetics, the principles of information theory were thought to be applicable to the higher functions of living organisms, and able to analyze such functions as metabolism, growth, and differentiation (Quastler 1953) . Today, the metaphors and the jargon of information theory are still widely used (Maynard Smith 1999a , 1999b , as opposed to the mathematical formalism, which is too often considered to be inapplicable to biological information. Clearly, looking back it appears that too much hope was laid upon this theory's relevance for biology. However, there was well-founded optimism that information theory ought to be able to address the complex issues associated with the storage of information in the genetic code, only to be repeatedly questioned and rebuked (see, e.g., Vincent 1994 , Sarkar 1996 . In this article, I outline the concepts of entropy and information (as defined by Shannon) in the context of molecular biology. We shall see that not only are these terms well-defined and useful, they also coincide precisely with what we intuitively mean when we speak about information stored in genes, for example. I then present examples of applications of the theory to measuring the information content of biomolecules, the identification of polymorphisms, RNA and protein secondary structure prediction, the prediction and analysis of molecular interactions, and drug design. Entropy and information are often used in conflicting manners in the literature. A precise understanding, both mathematical and intuitive, of the notion of information (and its relationship to entropy) is crucial for applications in molecular biology. Therefore, let us begin by outlining Shannon's original entropy concept (Shannon, 1948). Entropy in Shannon's theory (defined mathematically below) is a measure of uncertainty about the identity of objects in an ensemble. Thus, while "en-1 tropy" and "uncertainty" can be used interchangeably, they can never mean information. There is a simple relationship between the entropy concept in information theory and the Boltzmann-Gibbs entropy concept in thermodynamics, briefly pointed out below. Shannon entropy or uncertainty is usually defined with respect to a particular observer. More precisely, the entropy of a system represents the amount of uncertainty one particular observer has about the state of this system. The simplest example of a system is a random variable, a mathematical object that can be thought of as an N-sided die that is uneven, i.e., the probability of it landing in any of its N states is not equal for all N states. For our purposes, we can conveniently think of a polymer of fixed length (fixed number of monomers), which can take on any one of N possible states, where each possible sequence corresponds to one possible state. Thus, for a sequence made of L monomers taken from an alphabet of size D, we would have N = D L . The uncertainty we calculate below then describes the observer's uncertainty about the true identity of the molecule (among a very large number of identically prepared molecules: an ensemble), given that he only has a certain amount of probabilistic knowledge, as explained below. This hypothetical molecule plays the role of a random variable if we are given its probability distribution: the set of probabilities p 1 , ..., p N to find it in its N possible states. Let us thus call our random variable (random molecule) "X", and give the names x 1 , ..., x N to its N states. If X will be found in state x i with probability p i , then the entropy H of X is given by Shannon's formula I have not here specified the basis of the log to be taken in the above formula. Specifying it assigns units to the uncertainty. It is sometimes convenient to use the number of possible states of X as the base of the logarithm (in which case the entropy is between zero and one), in other cases base 2 is convenient (leading to an entropy in units "bits"). For biomolecular sequences, a convenient unit obtains by taking logarithms to the basis of the alphabet size, leading to an entropy whose units we shall call "mers". Then, the maximal entropy equals the length of the sequence in mers. Let us examine Eq. (1) more closely. If measured in bits, a standard interpretation of H(X) as an uncertainty function connects it to the smallest number of "yes-no" questions necessary, on average, to identify the state of 2 random variable X. Because this series of yes/no questions can be thought of as a description of the random variable, the entropy H(X) can also be viewed as the length of the shortest description of X (Cover and Thomas, 1991) . In case nothing is known about X, this entropy is H(X) = log N, the maximal value that H(X) can take on. This occurs if all states are equally likely: p i = 1/N ; i = 1, ..., N. If something (beyond the possible number of states N) is known about X, this reduces our necessary number of questions, or the length of tape necessary to describe X. If I know that state X = x 7 , for example, is highly unlikely, then my uncertainty about X is going to be smaller. How do we ever learn anything about a system? There are two choices. Either we obtain the probability distribution using prior knowledge (for example, by taking the system apart and predicting its states theoretically) or by making measurements on it, which for example might reveal that not all states, in fact, are taken on with the same probability. In both cases, the difference between the maximal entropy and the remaining entropy after we have either done our measurements or examined the system, is the amount of information we have about the system. Before I write this into a formula, let me remark that, by its very definition, information is a relative quantity. It measures the difference of uncertainty, in the previous case the entropy before and after the measurement, and thus can never be absolute, in the same sense as potential energy in physics is not absolute. In fact, it is not a bad analogy to refer to entropy as "potential information", because potentially all of a system's entropy can be transformed into information (for example by measurement). In the above case, information was the difference between the maximal and the actual entropy of a system. This is not the most general definition as I have alluded to. More generally, information measures the amount of correlation between two systems, and reduces to a difference in entropies in special cases. To define information properly, let me introduce another random variable or molecule (call it "Y "), which can be in states y 1 , ..., y M with probabilities p 1 , ..., p M . We can then, along with the entropy H(Y ), introduce the joint entropy H(XY ), which measures my uncertainty about the joint system XY (which can be in N · M states). If X and Y are independent random variables (like, e.g., two dice that are thrown independently) 3 the joint entropy will be just the sum of the entropy of each of the random variables. Not so if X and Y are somehow connected. Imagine, for example, two coins that are glued together at one face. Then, heads for one of the coins will always imply tails for the other, and vice versa. By gluing them together, the two coins can only take on two states, not four, and the joint entropy is equal to the entropy of one of the coins. The same is true for two molecules that can bind to each other. First, remark that random molecules do not bind. Second, binding is effected by mutual specificity, which requires that part of the sequence of one of the molecules is interacting with the sequence of the other, so that the joint entropy of the pair is much less than the sum of entropies of each. Quite clearly, this binding introduces strong correlations between the states of X and Y : if I know the state of one, I can make strong predictions about the state of the other. The information that one molecule has about the other is given by i.e., it is the difference between the sum of the entropies of each, and the joint entropy. The colon between X and Y in the notation for the information is standard; it is supposed to remind the reader that information is a symmetric quantity: what X knows about Y , Y also knows about X. For later reference, let me introduce some more jargon. When more than one random variable is involved, we can define the concept of conditional entropy. This is straightforward. The entropy of X conditional on Y is the entropy of X given Y , that is, if I know which state Y is in. It is denoted by H(X|Y ) (read "H of X given Y ") and is calculated as This formula is self-explanatory: the uncertainty I have about X if Y is known is the uncertainty about the joint system minus the uncertainty about Y alone. The latter, namely the entropy of Y without regard to X (as opposed to "conditional on X") is sometimes called a marginal entropy. Using the concept of conditional entropy, we can rewrite Eq. (2) as We have seen earlier that for independent variables H(XY ) = H(X) + H(Y ), so information measures the deviation from independence. In fact, it 4 measures exactly the amount by which the entropy of X or Y is reduced by knowing the other, Y or X. If I is non-zero, knowing one of the molecules allows you to make more accurate predictions about the other: quite clearly this is exactly what we mean by information in ordinary language. Note that this definition reduces to the example given earlier (information as difference between entropies), if the only possible correlations are between X and Y , while in the absence of the other each molecule is equiprobable (meaning that any sequence is equally likely). In that case, the marginal entropy H(X) must be maximal (H = log N) and the information is the difference between maximal and actual (i.e., conditional) entropy, as before. I will briefly comment about the relationship between Shannon's theory and thermodynamics (Adami and Cerf 1999). For the present purpose it should suffice to remark that Boltzmann-Gibbs thermodynamic entropy is just like Shannon entropy, only that the probability distribution p i is given by the Boltzmann distribution of the relevant degrees of freedom (position and momentum): and the thermodynamic quantity is made dimensional by multiplying Shannon's dimensionless uncertainty by Boltzmann's constant. It should not worry us that the degrees of freedom in thermodynamics are continuous, because any particular measurement device that is used to measure these quantities will have a finite resolution, rendering these variables effectively discrete through coarse-graining. More importantly, equilibrium thermodynamics assumes that all entropies of isolated systems are at their maximum, so there are no correlations in equilibrium thermodynamic systems, and therefore there is no information. This is important for our purposes, because it implies, a fortiori, that the information stored in biological genomes guarantees that living systems are far away from thermodynamical equilibrium. Information theory can thus be viewed as a type of non-equilibrium thermodynamics. Before exploring the uses of these concepts in molecular biology, let me reiterate the most important points which tend to be obscured when discussing information. Information is defined as the amount of correlation between two systems. It measures the amount of entropy shared between two systems, and 5 this shared entropy is the information that one system has about the other. Perhaps this is the key insight that I would like to convey: Information is always about something. If it cannot be specified what the information is about, then we are dealing with entropy, not information. Indeed, entropy is sometimes called, in what borders on an abuse of language, "useless information". The previous discussion also implies that information is only defined relative to the system it is information about, and is therefore never absolute. This will be particularly clear in the discussion of the information content of genomes, which we now enter. There is a long history of applying information theory to symbolic sequences. Most of this work is concerned with the randomness, or, conversely, regularity, of the sequence. Ascertaining the probabilities with which symbols are found on a sequence or message will allow us to estimate the entropy of the source of symbols, but not what they stand for. In other words, information cannot be accessed in this manner. It should be noted, however, that studying horizontal correlations, i.e., correlations between symbols along a sequence rather than across sequences, can be useful for distinguishing coding from non-coding regions in DNA (Grosse et al., 2000) , and can serve as a distance measure between DNA sequences that can be used to assemble fragments obtained from shotgun-sequencing (Otu and Sayood, 2003) . In terms of the jargon introduced above, measuring the probabilities with which symbols (or groups of symbols) appear anywhere in a sequence will reveal the marginal entropy of the sequence, i.e., the entropy without regard to the environment or context. The entropy with regard to the environment is the entropy given the environment, a conditional entropy, which we shall calculate below. This will involve obtaining the probability to find a symbol at a specific point in the sequence, as opposed to anywhere on it. We sometimes refer to this as obtaining the vertical correlations between symbols. Obtaining the marginal entropy of a genetic sequence can be quite involved (in particular if multi-symbol probabilities are required), but a very good approximative answer can be given without any work at all: This entropy 6 (for DNA sequences) is about two bits per base. There are deviations of interest (for example in GC-rich genes, etc.) but overall this is what the (non-conditional) entropy of most of DNA is (see, e.g., Schmitt and Herzel 1997) . The reason for this is immediately clear: DNA is a code, and codes do not reveal information from sequence alone. Optimal codes, e.g., are such that the encoded sequences cannot be compressed any further (Cover and Thomas, 1991) . While DNA is not optimal (there are some correlations between symbols along the sequence), it is nearly so. The same seems to hold true for proteins: a random protein would have log 2 (20) = 4.32 bits of entropy per site (or 1 mer, the entropy of a random monomer introduced above), while the actual entropy is somewhat lower due to biases in the overall abundance (leucine is over three times as abundant as tyrosine, for example), and due to pair and triplet correlations. Depending on the data set used, the protein entropy per site is between 2.5 (Strait and Dewey, 1996) and 4.17 bits (Weiss et al., 2000) , or between 0.6 and 0.97 mers. Indeed, it seems that protein sequences can only be compressed by about 1% (Weiss et al. 2000) . This is a pretty good code! But this entropy per symbol only allows us to quantify our uncertainty about the sequence identity, but it will not reveal to us the function of the genes. If this is all that information theory could do, we would have to agree with the critics that information theory is nearly useless in molecular biology. Yet, I have promised that information theory is relevant, and I shall presently point out how. First of all, let us return to the concept of information. How should we decide whether or not potential information (a.k.a entropy) is in actuality information, i.e., whether it is shared with another variable? The key to information lies in its use to make predictions about other systems. Only in reference to another ensemble can entropy become information, i.e., be promoted from useless to useful, from potential to actual. Information therefore is clearly not stored within a sequence, but rather in the correlations between the sequence and what it describes, or what it corresponds to. What do biomolecular sequences correspond to? What is the meaning of a genomic sequence, what information does it represent? This depends, quite naturally, on what environment the sequence is to be interpreted within. According to the arguments advanced here, no sequence has an intrinsic meaning, but only a relative (or conditional) one with respect to an environment. So, for example, the genome of Mycoplasma pneumoniae (a bacterium that causes pneumonia-like respiratory illnesses) has an entropy of almost a million base pairs, which is its genome length. Within the soft 7 tissues that it relies on for survival, most of these base pairs (about 89%) are information (Dandekar et al., 2000) . Indeed, Mycoplasmas are obligate parasites in these soft tissues, having shed from 50% to three quarters of the genome of their bacterial ancestors (the Bacillae). Within these soft tissues that make many metabolites readily available, what was information for a Bacillus had become entropy for the Mycoplasma. With respect to other environments, the Mycoplasma information might mean very little, i.e., it might not correspond to anything there. Whether or not a sequence means something in its environment determines whether or not the organism hosting it lives or dies there. This will allow us to find a way to distinguish entropy from information in genomes. In practice, how can we determine whether a particular base's entropy is shared, i.e., whether a nucleotide carries entropy or information? At first glance one might fear that we would have to know a gene's function (i.e., know what it corresponds to within its surrounding) before we can determine the information content; that, for example, we might need to know that a gene codes for an alcoholdehydrogenase before we can ascertain which base pairs code for it. Fortunately, this is not true. What is clear, however, is that we may never distinguish entropy from information if we are only given a single sequence to make this determination, because, in a single sequence, symbols that carry information are indistinguishable from those that do not. The trick lies in studying functionally equivalent sets of sequences, and the substitution patterns at each aligned position. In an equilibrated population, i.e, one where sufficient time has passed since the last evolutionary innovation or bottleneck, we expect a position that codes for information to be nearly uniform across the population (meaning that the same base pair will be found at that position in all sequences of that population), because a mutation at that position would detrimentally affect the fitness of the bearer, and, over time, be purged from the ensemble (this holds in its precise form only for asexual populations). Positions that do not code for information, on the other hand, are selectively neutral, and, with time, will take on all possible symbols at that position. Thus, we may think of each position on the genome as a four-sided die. A priori, the uncertainty (entropy) at each position is 8 two bits, the maximal entropy:
On the other hand, there is the question of what if anything a given portion of genetic entropy is 'about' -that is to say, not just whether it varies, but whether it has information about variations that exist within the environment or context of the organism REF .
Information theory in molecular biology
Physics of Life Reviews 1 (2004) 3-22
Computer Science Biology