Fwd: Big Math

[Jason de Koning]

>> My puzzle to Taxacomers is more simple:  what is a physical solution
>> to,
>> say, parsimony analysis of a data set?
>
> That's easy. It's called "neighbor-joining". Problem is, it leads to
I actually think the opposite is true: since parsimony analysis is a
minimization/maximization problem, it is much more analogous to the
kinds of "physical" problems that are being addressed this way.
Neighbour-joining isn't NP hard, its just a fast and easy deterministic
algorithm, which accounts for its popularity.

> a different solution than actual parsimony analysis. The reason it
> fails as an analogy is the same reason you can't come up with ANY
> truly analogous physical solution: because - by the very nature of
> the process - a physical approach will lead to a SINGLE solution
> (like neighbor-joining), while parsimony yields *multiple*,
> equally-plausible solutions. You might as well try to anticipate

In general, the metaphor of using nature for "computation for free" is
very appealing.  Take "DNA computing" as an example with some potential
for interesting work beyond toy problems: using biomolecules in
solution for combinatorial search.  If you wanted to solve a phylogeny
problem using DNA computing (like maximum parsimony), the primary
difficulty is how to encode the search space.  In principle, however,
there is no a priori reason why this would be more difficult than any
other combinatorial problem that has been solved this way; it's the
traveling salesman problem writ large.  Having multiple optimal
solutions isn't really a problem either (at least in principle); just
run the experiment multiple times.  Have a look at the DNA computing
literature; papers by Richard Lipman and Leonard Adleman may be of
particular interest.  I wouldn't be surprised if someone is working on
phylogeny problems in the DNA computing field.

Cheers,
- Jason

________________________________________________________________________
__
   A.P. Jason de Koning, Doctoral student        Email: apjdk at albany.edu
     Department of Biological Sciences             Lab:  (518) 442-4347
     University at Albany, SUNY                    FAX:  (518) 442-4767
     1400 Washington Ave., Albany NY 12222, USA  Mobil:  (518) 210-4504
________________________________________________________________________
__