|
Author
|
Topic: Some comments on Strachan's article
|
Erik
Member
Member # 160
|
posted 23. July 2003 07:48
In the thread "I.G.D. Strachan: An Evaluation of 'Ev'" an article criticizing Schneider's Ev paper was announced. The subsequent discussions focused only on some very restricted aspects of Strachan's critcism, so I start this new thread with my comments on the merits and flaws of Strachan's critcism.
----------------------------------------------
Before getting to my first criticism of Strachan's conclusions, I will, for completeness, briefly review some concepts from statistics and information theory.
When we first encounter statistics in mathematics studies we learn about quantities like expectation value and variance. Such quantities are meant to describe different properties of stochastic variables (s.v.). The variance measures how spread out the probable values of a s.v. are. A central concept in Shannon's information theory is, in a qualitative sense, very much like variance. It is called Shannon entropy and it measures, roughly speaking, how many of the possible values of a s.v. that are probable. Note that it is meaningless to talk about entropy without having made clear which s.v. one is talking about, just as it is meaningless to talk about variance without first having identified a s.v.
Shannon information is the decrease in the entropy of some s.v. that occurs when we learn the value of some particular s.v. In simple versions of information theory the information about the s.v. X that results from learning that Y = y is given by
R = H(X) - H(X | Y = y),
where H(X) is the entropy of X and H(X | Y = y) is the entropy when all probabilities are conditioned on the event Y = y. Schneider uses this simple version, and writes Hbefore for H(X) and Hafter for H(X | Y = y). More mathematical treatments measure information as the mutual information between X and Y, given by
I(X; Y) = H(X) - H(X | Y),
where H(X | Y) is the average of H(X | Y = y), averaged over all y. See section 2.5 of this free book for details.
The main point here is that entropy is only meaningful when we have a specific s.v. in mind. And information, in Shannon's sense, is only meaningful when we have an additional s.v. in mind. I encourage the reader to think about entropy as "a kind of variance" and information as "a kind of decrease in variance". The analogy is far from perfect, but it has a reasonable qualitative accuracy and serves to demystify Shannon information. It is virtually impossible to disagree about a decrease in variance once it has been made clear exactly which s.v. one is talking about and what the probability distribution is. The same is true for (Shannon) information. Thus, the good news is that disagreements about (Shannon) information can always be resolved by precisely specifying the s.v. and probability distribution. The bad news is that virtually no one writing popular or semi-popular texts bothers to make it clear which s.v. that is being discussed. The result is typically confusion.
Shannon information about what? Strachan argued:
quote:
"Hence we argue that in fact there is external intervention; the sitelocations array has to be set up prior to the simulation, and in doing so, the precise amount of information that is claimed to have evolved from scratch has in fact been pre-specified in the setting up of this array (to specify 16 locations out of 256 requires 4 bits of information per location)."
When we read that Schneider claims that information has evolved, we should ask "information about what"? That is, "which stochastic variable has had its entropy decreased"? Strachan failed to ask this question. Consider the following s.v.
X = the exact nucleotide sequence at the current site that the binding site recognizer has bumped into,
Y = a variable taking the value 1 if the current site is a binding site and 0 otherwise.
Schneider claims to have shown that the quantity
Rseq = H(X) - H(X | Y = 1)
evolves up to the value of Rfreq. The quoted comments by Strachan does not address Schneider's real claim (specifying the locations of the binding sites does not fix Rseq). Instead he confuses Rseq with some other kind of information. I'm not sure that Strachan is even thinking in terms of s.v., but if he is thinking about s.v. he is definitely thinking about the wrong s.v.. This is yet another example of equivocation, where someone makes a claim about "information" and someone else replies using the term "information" in a different sense.
What is a target? My next criticism of the paper concerns the concept of a "target". It is unclear both what is meant by "target" and why it is interesting to partition the sequence space into "target" and "not target". Strachan states that the goal of Dawkins's WEASEL simulation is reach a particular sequence t in the sequence space. But in what sense is that the goal? Is it the goal because Dawkins wanted his GA to reach t? Is it the goal because Dawkins found t to be of special interest? Is it the goal because Strachan finds t to be of special interest?
Strachan goes on to write that there is a sequence t in Schneider's simulation, such that the "goal" is to find a sequence g satisfying
f(g) = t.
Here, f is apparently a mapping from the sequence space to itself. Two sentences later, Strachan contradicts himself by writing that, in the case of Ev, f is the perceptron output function. But the perceptron output function is not a mapping from the sequence space to itself, rather it is a mapping from the set of all sequences of length six to the real numbers. f(g) = t can never hold in this case, because the left hand side is a real number and the right hand side is a nucleotide sequence. (How evil of the PCID reviewer to not point out that mistake before it was officially published!)
Preserving exons. Parts of section 2.3 seems like a valid concern to me. Schneider's simulation is an idealization which does not take into account the fact that some parts of the genome are exons. It is perfectly legitimate to wonder if the conclusion would be different if exons are taken into account. I do not know the answer.
The simulation described in the section seems dubious. For instance, if the intent is to model exons then this should be reflected in the fitness function. Exon sequences that are stipulated to be well-functioning proteins should confer a high fitness contribution and sequences that are stipulated to be poorly functioning should confer a low fitness contribution. All references to "information" in the section are examples of equivocation, because neither corresponds to Rfreq (information about binding site locations) or Rseq (information about binding site sequences).
Statistically independent nucleotides and small samples. Section 3 is another valid concern. It is an approximation to compute H(X | Y = 1), or Hafter in Schneider's notation, as if the nucleotides in the binding sites were statistically independent. It is hardly possible to reliably estimate the joint probability distribution for all the nucleotides in a binding site without a substantially larger sample. The independence assumption is made for pragmatic reasons, and it is interesting to wonder if things would be different in a genome that is long enough to include really many binding sites, so that the joint probability distribution could be estimated accurately. However, if I understand things correctly, the independence assumption is also made when calculating Rseq in real, biological sequence data. So, given that empirical data is analyzed under the assumption of independence, it is appropriate for Schneider to analyze his simulation under the same assumption. But it would undoubtably be better if the data could be consistently analyzed using fewer, or smaller, a priori assumptions.
I have few comments on the small sample correction. A minor comment is that Strachan claims in a footnote to be doing a Bayesian derivation with a uniform prior, yet I don't think Strachan's entropy estimator (given by Eq. (20)) looks like the Bayesian estimator derived from a uniform prior (see Wolpert D. & Wolf D. Phys. Rev. E 52:6841-6854, and Samengo I. Phys. Rev. E 65:046124). I have not seen Schneider's derivation of the small sample correction, but it seems to me that Strachan is correct that Stirling's approximation should not be used for the parameter values used in the simulation.
Erik
IP: Logged
|
|
Iain Strachan
Member
Member # 96
|
posted 23. July 2003 15:55
Erik,
Thanks for the comments. I don't have a large amount of time to address them in full, as I'm soon off on holiday. But I'll try and clarify some issues. You said:
quote:
Schneider claims to have shown that the quantity
Rseq = H(X) - H(X | Y = 1)
evolves up to the value of Rfreq. The quoted comments by Strachan does not address Schneider's real claim (specifying the locations of the binding sites does not fix Rseq). Instead he confuses Rseq with some other kind of information. I'm not sure that Strachan is even thinking in terms of s.v., but if he is thinking about s.v. he is definitely thinking about the wrong s.v.. This is yet another example of equivocation, where someone makes a claim about "information" and someone else replies using the term "information" in a different sense.
Yes, Rseq is a measure of the information about X, the distribution of bases at the binding sites. Naturally I was thinking in terms of this s.v. (Though it turns out that Rseq is not a good estimator as it uses the wrong probabilistic model). But the key to the argument is the statement "Given Y=1". Thus you have to specify where Y has the value 1 for the simulation to work. Think of it this way. If I said "I'm thinking of one particular binding site that evolves during an Ev simulation run; guess what it is - no further hints as to where they are". Then you will have a 1/256 chance of getting it right. But if I also passed you a bit of paper where it said "By the way, it's one of these 16 values ...", then you'd have a 1/16 chance of getting it right. Your uncertainty has decreased by 4 bits; previously your idea of the probability distribution of the binding sites was a uniform one with a probability of 1/256 everywhere, after you get the piece of paper, it's 1/16 at the 16 locations specified on the paper and zero elsewhere. That is what has happened in the simulation, and what enables the mistake count to be evaluated. But starting from a random population of genomes, without any external intervention as Schneider claims, then there is no way that the list of locations can be specified; the binding sites could develop anywhere. To specify where they are to appear right at the start isn't a "blind watchmaker", it's one with 20-20 vision.
You also wrote:
quote:
Strachan goes on to write that there is a sequence t in Schneider's simulation, such that the "goal" is to find a sequence g satisfying
f(g) = t.
Here, f is apparently a mapping from the sequence space to itself. Two sentences later, Strachan contradicts himself by writing that, in the case of Ev, f is the perceptron output function. But the perceptron output function is not a mapping from the sequence space to itself, rather it is a mapping from the set of all sequences of length six to the real numbers. f(g) = t can never hold in this case, because the left hand side is a real number and the right hand side is a nucleotide sequence. (How evil of the PCID reviewer to not point out that mistake before it was officially published!)
No, I didn't mean that f(g) was a mapping of sequence space to itself, though the statement that t was a "sequence" was perhaps misleading. I meant it to represent a general mapping of genome sequence space to a sequence of output symbols which may have a different length and cardinality. In the Ev simulation it is a mapping of a sequence of 261 symbols each having 4 discrete values (A,C,G,T) to a sequence of 256 output symbols each having two discrete values (0 or 1). In the Dawkins simulation it is a mapping of sequence space onto itself. In the VETE simulation it maps a sequence of symbols having 27 discrete values of length (textLen + keyLen) onto a sequence of length (textLen).
Concerning the preservation of Exons, you wrote:
quote:
All references to "information" in the section are examples of equivocation, because neither corresponds to Rfreq (information about binding site locations) or Rseq (information about binding site sequences).
Agreed; they do not refer to information about binding site sequences or about binding site locations; they refer to information about the coding sequence in the exons. That such "information" would exist if there were exons present is undoubtedly true; the protein coded for is highly specific; only a small subset of code sequences will do the job properly (i.e. those that all code up for the same sequence of amino acids - or possibly with some variations that are not harmful to the protein's function). I do not attempt to model how such information would be encoded in a real protein, I simply supplied a toy model (restricting the allowed codon "values"). I understand that in real analysis of exon data, that Hidden Markov Models are used). However, no attempt is made in the Ev simulation to preserve such information - as you say, and I agree, the preservation of such information should be reflected in the fitness function. I think it would be an interesting exercise to see what would happen if one did this - I even considered running this simulation while preparing the paper; It would be interesting in particular to see if Rseq still evolved up to Rfreq, which is what Schneider wants to show. But in the end, I didn't consider it worth including - the central claim of Schneider's paper is that the information arises from a completely random genome - hence no exons are present; instead the exon location data is artificially supplied as a "target" for the neural network function to match to. No such target would exist in a sea of random genomes competing with each other.
If one wants to refer to a "target" in sequence space, then note that it is a multi-valued target (just as the bullseye on an archer's target expands over a finite area). Although specifying the site locations does not fix Rsequence, it does fix the (multi-valued) target for the genomic sequence to reach if there are no "mistakes". This is a fixed subset of the entire set of possible sequences, and it is unique to the particular set of sitelocations specified (though the values of Rseq for each member of the subset will of course vary). It is trivial to see why the "zero mistakes" sequence space subset is entirely fixed by the site locations. All the sequences in this subset output the same sequence of 0's and 1's from the perceptron algorithm, which matches that stored in the sitelocations array. If you were then to change the location of one of the sites to what was previously a non-site, then every single member of the original subset will produce two mistakes.
quote:
A minor comment is that Strachan claims in a footnote to be doing a Bayesian derivation with a uniform prior, yet I don't think Strachan's entropy estimator (given by Eq. (20)) looks like the Bayesian estimator derived from a uniform prior (see Wolpert D. & Wolf D. Phys. Rev. E 52:6841-6854, and Samengo I. Phys. Rev. E 65:046124).
No, I wasn't claiming that I was doing a Bayesian derivation; the entropy estimator given by Eq. (20) is a simple counting argument on the number of ways of arranging the system, and is derived from Bishop's book ( Reference Bishop C. (1995) "Neural Networks for Pattern Recognition" OUP, Oxford UK ). It was probably a little irrelevant to introduce this comment without further expansion in the article. The point I was wanting to make was that if one did this in a Bayesian framework (which we are not doing at the moment), then the information gained would be the difference in Entropy between the prior and posterior distributions. If one makes a probabilistic inference, then, provided one uses the appropriate probabilistic model, the posterior distribution should be more sharply peaked than the prior (or as you say the variance has been reduced). But herein lies one of my big problems with the Scheider approach in general, in saying that the amount of information "in" (about) the binding site sequences is exactly the amount needed to locate them (Rfreq). The problem is that in the expression:
H(X | Y=1)
we don't have the full picture; we have an assumed probability model (call it M). Hence we should really write:
H(X | Y=1, M)
and this value will vary with different choices of the model M. As I demonstrated, Schneider's choice of M (compting the base-by-base frequencies of the four nucleotides) was in fact an inappropriate probability model. But the key problem is that you don't know at the beginning what sort of model to choose, and each will give different values of the entropy. For example, if you took English text, then you could compute the letter frequencies and get a histogram form of the probability distribution. But this would have a higher entropy than a probability model that took into account sequential correlations between the letters, such as a Hidden Markov Model, which would capture the fact that a Q is invariably followed by a U and so forth. Now in the HMM, the "prior" would be pretty much the same as the static letter distributions, but the posterior distribution would be more sharply peaked, (lower variance) and hence apparently would show more information for the same sequence than the static distribution. So you can't really say what the information content is except with respect to a probability model, which may or may not be an appropriate one for the data. The best you can do is to give a lower bound on the amount of information. With Schneider's Perceptron model, with 256 bases and 16 binding sites, the lower bound estimated by the true value of Rseq is around 3 bits.
Now my understanding (from the few papers that I cited on analysis of the Human Genome Project) is that Hidden Markov Models are in common use to enable detection of various sites on DNA sites, and in the location of exons, binding sites and so forth. So does this not imply that Rseq does not capture all the information about the binding site sequences, and that therefore it makes no sense to say that the fact Rseq =approx Rfreq because that's all the information you need? It only makes sense if the way the binding happens can be modelled by the probability model implicit in Rseq; which is certainly not so for the Perceptron, which puts a separating hyperplane through input space, and introduces depencencies between the variables.
IP: Logged
|
|
Pim van Meurs
Member
Member # 541
|
posted 23. July 2003 23:21
Iain,
I think that what Erik was refering to was what I tried to address as well namely the claim that the selection of the binding sites is what preloads the information. Identification of the binding sites however does not increase the information in the genome. In fact it is mutation AND selection which are necessary for the information to increase. Hence the use of the term equivocation when discussing information. It would be helpful if you could show that the information increase were somehow preloaded via the selection of the binding sites. If there was any link, one would not expect the Rseq to vary between runs.
The information increase is still contingent making the claim that information was preloaded hard to press.
IP: Logged
|
|
Erik
Member
Member # 160
|
posted 31. July 2003 20:26
Iain Strachan, enjoy your vacation. This thread will probably still be here when you get back, so there's no hurry.
quote:
Iain Strachan: Yes, Rseq is a measure of the information about X, the distribution of bases at the binding sites. Naturally I was thinking in terms of this s.v. (Though it turns out that Rseq is not a good estimator as it uses the wrong probabilistic model). But the key to the argument is the statement "Given Y=1". Thus you have to specify where Y has the value 1 for the simulation to work. Think of it this way. If I said "I'm thinking of one particular binding site that evolves during an Ev simulation run; guess what it is - no further hints as to where they are". Then you will have a 1/256 chance of getting it right. But if I also passed you a bit of paper where it said "By the way, it's one of these 16 values ...", then you'd have a 1/16 chance of getting it right. Your uncertainty has decreased by 4 bits; previously your idea of the probability distribution of the binding sites was a uniform one with a probability of 1/256 everywhere, after you get the piece of paper, it's 1/16 at the 16 locations specified on the paper and zero elsewhere. That is what has happened in the simulation, and what enables the mistake count to be evaluated. But starting from a random population of genomes, without any external intervention as Schneider claims, then there is no way that the list of locations can be specified; the binding sites could develop anywhere. To specify where they are to appear right at the start isn't a "blind watchmaker", it's one with 20-20 vision.
The "information" that Schneider claims increases during the simulation is the Shannon information about the binding site sequences, not the Shannon information about the binding site locations. At the beginning of the simulation, the simulation program "learns" the locations of the binding sites, but the simulation program does not tell the binding site recognizer where locations are. It goes without saying that the performance of a binding site recognizer can only be evaluated by a program that "knows" the locations of the binding sites. To evaluate the performance in any other way would be wrong, so Schneider did the only correct thing here.
Perhaps you think that once the locations of the binding sites are known that will enable the binding site recognizer to infer the value of X with probability 1. If that's what you are suggesting, you are wrong. The binding site recognizer is neither able nor allowed to learn the value of the binding site locations. The binding site recognizer evolves the ability to recognize nucleotide patterns, not nucleotide locations. Furthermore, even if the binding site recognizer would know the exact location of all binding sites, that would tell it literally nothing about X (= the nucleotide sequence at the site currently evaluated by the binding site recognizer). You claim above to be thinking about the s.v. X, but you nevertheless seem to have confused this s.v. with the binding site locations.
Your reply about "goals" and "targets" clarifies your notation, but not the significance of goals and targets. So far you've told me that f can be a mapping from sequence space to anything and that the "target" is an element of this anything. That's exceedingly vague. Of all the possible mappings f and of all the possible t's, why did you pick the ones you did for the WEASEL and Ev cases? Which criteria did you use to single out precisely the f's and t's you described in your paper?
quote:
Iain Strachan: Agreed; they do not refer to information about binding site sequences or about binding site locations; they refer to information about the coding sequence in the exons. That such "information" would exist if there were exons present is undoubtedly true; the protein coded for is highly specific; only a small subset of code sequences will do the job properly (i.e. those that all code up for the same sequence of amino acids - or possibly with some variations that are not harmful to the protein's function). I do not attempt to model how such information would be encoded in a real protein, I simply supplied a toy model (restricting the allowed codon "values"). I understand that in real analysis of exon data, that Hidden Markov Models are used). However, no attempt is made in the Ev simulation to preserve such information - as you say, and I agree, the preservation of such information should be reflected in the fitness function.
Given the choice of, say, the following alternatives:
(i) Study the same quantity as Schneider studied, but in an extended model that takes into account that exons can be functional and non-functional (or even something in between) depending on the sequence.
(ii) Give a different quantity the same name as the quantity studied by Schneider, and study this new quantity in a model whose initial conditions (but not dynamics!) takes into account that not all exon sequences are functional. Study the dynamics of the new quantity in this model and imply that Schneider is mistaken, in spite of the fact that dynamics of the model is unsuitable and that a different quantity was studied.
(iii) Excise that section from the paper.
Why would you choose alternative (ii)? While I think it is legitimate and interesting to ask "but what about exons?", your way of raising the question (i.e. alternative (ii)) serves mostly to confuse the issue.
quote:
Iain Strachan: But in the end, I didn't consider it worth including - the central claim of Schneider's paper is that the information arises from a completely random genome - hence no exons are present; instead the exon location data is artificially supplied as a "target" for the neural network function to match to. No such target would exist in a sea of random genomes competing with each other.
That's a distortion of Schneider's claim. The central claim of Schneider's paper is that (i) binding site sequences and binding site recognizers coevolve so that the binding sites stand out enough from the rest of the genome to allow the recognizer to reliably identify it, (ii) the equilibrium state can be described by Rseq ~ Rfreq, and (iii) all this happens regardless of locations of the binding sites and the initial sequences at those sites. The reason the binding site locations are fixed is simply that Schneider wanted idealize away other phenomena than the one he was interested in. This is a common procedure in science. Instead of trying to model all of the complicated relations and interactions that determines which locations are (not) exons, which sequences that are beneficial and which are not, etc., Schneider chose to only try to model the relation between binding sites and the binding site recognizer.
The proper interpretation of Schneider's model is that all the complicated things determining what is a binding site and what is not is black-boxed into sitelocations. The sitelocations array models some aspects of exons, but not all. In practice, Schneider's simplifications amounts the assumptions that the appearance and disappearance of new binding sites is a much slower process than the evolution of binding site recognition and that the parts of the genome that don’t belong to any binding sites can be treated as if the nucleotides are statistically independent.
quote:
Iain Strachan: If one wants to refer to a "target" in sequence space, then note that it is a multi-valued target (just as the bullseye on an archer's target expands over a finite area). Although specifying the site locations does not fix Rsequence, it does fix the (multi-valued) target for the genomic sequence to reach if there are no "mistakes". This is a fixed subset of the entire set of possible sequences, and it is unique to the particular set of sitelocations specified (though the values of Rseq for each member of the subset will of course vary). It is trivial to see why the "zero mistakes" sequence space subset is entirely fixed by the site locations. All the sequences in this subset output the same sequence of 0's and 1's from the perceptron algorithm, which matches that stored in the sitelocations array. If you were then to change the location of one of the sites to what was previously a non-site, then every single member of the original subset will produce two mistakes.
1. I actually don't want to refer to a "target". While I recognize that "target" can be a convenient name in optimization theory for the set of points having a satisfactorily high objective value (or satisfactorily low cost value), I wouldn't use the term in the way ID advocates do. ID advocates seem to think that "targets" have ontological or dynamical significance. I think it is just another case of vague terminology.
2. I agree that the set of maximum fitness sequences (maximum of all possible sequences, not necessarily maximum in the actual population) is fixed throughout the entire simulation. Why do you consider this fact more significant than, say, the colour of the keyboard used to type Schneider's Ev program?
3. What happens when we change the location of a binding site depends on what we mean by changing the location. If we leave the entire genome sequence unchanged, but change the sitelocations array, then the result will be as you describe. On the other hand, if we move the binding site sequence together with the binding site location, then there will be no additional mistakes. The binding site recognizer does not adapt in any way to the binding site locations; it only adapts to binding site sequences (as it should be).
quote:
Iain Strachan: Now my understanding (from the few papers that I cited on analysis of the Human Genome Project) is that Hidden Markov Models are in common use to enable detection of various sites on DNA sites, and in the location of exons, binding sites and so forth. So does this not imply that Rseq does not capture all the information about the binding site sequences, and that therefore it makes no sense to say that the fact Rseq =approx Rfreq because that's all the information you need? It only makes sense if the way the binding happens can be modelled by the probability model implicit in Rseq; which is certainly not so for the Perceptron, which puts a separating hyperplane through input space, and introduces depencencies between the variables.
Here's where I got my impression from:
quote:
"Empirically, the probability P_{b,i} can be estimated by the frequency with which base b is observed at position i at a binding site (Berg & von Hippel, 1987). As direct estimations of the P_w are usually not possible since not enough data are available, eqn (3) assuming independency in the word positions is used in empirical studies."
From section 3 of Kim J., Martinetz T. & Polani D. (2003) "Bioinformatic Principles Underlying the Information Content of Trascription Factor Binding Sites", Journal of Theoretical Biology, 220:529-544
Eqn (3) mentioned in the quote is Schneider's formula for Rseq. I have little doubt that lots of different models, including hidden Markov models, have been used for the analysis of DNA sequences. But the question is if such models have been used to model the sequences of binding sites, or if this particular kind of analysis has only been done with a model assuming statistical independence.
By the way, the entire paper by Kim et al. is relevant to our discussion. It is an exploration of all mathematically possible models similar to Schneider's. The conclusion is that Rseq = Rfreq does not hold in general. Rather, it is suggested that Rseq ~ Rfreq is "valid for all biological systems that are autonomous in the sense that they encode their gene regulatory logic within their own genomes".
Erik
Edit: Corrected a typo.
[ 01. August 2003, 11:14: Message edited by: Erik ]
IP: Logged
|
|
|
Printer-friendly view of this topic