From owner-metabolic-reg@net.bio.net Thu Oct 14 23:00:00 1993 Path: biosci!daresbury!doc.ic.ac.uk!uknet!festival!castle.ed.ac.uk!eanv20 From: eanv20@castle.ed.ac.uk (John Woods) Newsgroups: bionet.metabolic-reg Subject: Universal Method Message-ID: Date: 15 Oct 93 14:12:40 GMT Sender: news@festival.ed.ac.uk (remote news read deamon) Organization: Edinburgh University Lines: 109 Newsgroups: bionet.metabolic-reg Subject: Re: Universal method References: Henrik Kacser writes: > I think what John (Woods) means when he says that he "is not convinced > that a straightforward implementation would be feasable" he probably > means that there is no automatic and foolproof method where you just > press buttons. That's pretty much what I mean, although I'm also concerned about that even totally defined `buttons' may be impractical. A travelling salesman has to visit a number of towns, but may visit them in any order. He naturally prefers to visit them in the order which will involve least travelling. Half a dozen appointments present no problem --- he just digs out his copy of AutoRoute Express (TM). To deal with more cities he writes a computer program which will calculate all the possible distances and record the shortest. This method is both automatic and foolproof. It is easily stated, and indeed the computer program is trivial. But by the time we get to 10 cities, 3.6 million permutations exist. 100 cities take us to 10^158, and 1000 take us the already unimaginably huge 10^2567. (The world's only unbreakable cryptography system, RSA public key, works in exactly this way. `Everybody' knows what must be done to break it, but a code created in 10 minutes on a PC might take millions of supercomputer hours to crack.) >As to his championing mutation/selection as the method of choice, he >should really aqauint himself with the literature on selection limits >(or perhaps talk to a population geneticists and breeders). What kind of >mutation would he envisage that produces a 25 fold (2500%) increase in >the enzyme activity of each and every step of say the tryp pathway? Form: Coming from a genetic rather than biochemical background, I would say that these are the MCA/T papers I understand best. My critique of the `Universal method' was murky and handwaving for good reason --- intended more as a discussion-starter than as a in-the-literature response. The general tone of electronic discussion tends to be somewhat less intense than the scientific literature --- I would have studied the paper an awful lot harder if I had intended a formal criticism. What `expertise' I have tends to lean heavily towards then computational rather than the biochemical, especially at the moment. Hence I was a little taken aback to see Rankin taking me to task for `dismissing it lightly' --- and I apologize for any offence! Substance: The travelling salesman, and other optimization problems, can now be effectively `solved' for large n. If this were not the case, most of us would be working on far less powerful computers --- optimal placement of components on a chip is effectively the travelling salesman problem writ large (might optimal flux improvement be, as well?). Two current exciting methods exist for difficult minimization: 1) Simulated Annealing (SA) and its derivatives (such as Very Fast Simulated Reannealing). These attempt to mock the process whereby crystals form, effortlessly reaching the lowest possible thermodynamic state. A simulated temperature steadily decreases, whilst random alterations to the existing solution are invoked if (a) the current temperatue is sufficient to overcome the energy barrier and (b) the change is favourable. ("I realize that technically that's just one condition, but it was so important I thought I'd mention it twice" --- Kryton, Red Dwarf). The slower the temperature cools, the longer the optimization takes, and the more likely it is to settle into a `good' result. Think of a ball bouncing on a pitted surface, becoming less and less likely to overcome the barriers to other regions. 2) Genetic Algorithms (GA) and derivatives work on the principle of natural selection, with the `fittest' solutions surviving at the expense of suboptimal ones. They are comparable in result to evolution --- very good at complex optimization, but prone to fall into deep local minima, with overwhelming change necessary for further improvements. Just like the mamalian eye --- it's inside out because the chance of inverting it without severe visual disruption is minute, but it's now very well adapted for working inside out. > What kind of mutation would he envisage that produces a 25 fold > (2500%) increase in the enzyme activity of each and every step of say > the tryp pathway? I envisage such an increase being possible only with human and computational intervention. The molecular biologists could use a computerized version of the Universal Method and intervene directly as indicated by the results. But I wouldn't rule out the possibility of the computational approach using a GA (ie: successive rounds of selection and mutation). This was all that my claim contended, albeit stated with somewhat suboptimal clarity. I also beleive that VFSR is a more likely source of fruitful solutions, but think it may have generated rather less discussion. >Watch this space. >HK. I think it's safe to say that we all are! ... John Woods -- " Forsan et haec olim meminisse iuvabit (Virgil) [approx] Tr: The time may come when we will look back on these days and laugh " .