DIMACS Seminar on Math and CS in Biology


Numerical Taxonomy: a new method and experimental results


Jaime Cohen
Rutgers University


Seminar Room 431, CoRE Building
Rutgers University.


3:00 p.m.
Tuesday, December 3, 1996

We consider the problem of fitting an n by n distance matrix D by a tree metric T. This problem is NP-hard for most reasonable distance functions between D and T. Recently, an approximation algorithm was discovered which achieves a factor of 3 approximation to the L-infinity best fitting tree. We call this method the Single Pivot (SP) heuristic. We will describe an extension of the SP heuristic, the Double Pivot (DP) heuristic, and show that DP achieve good results compared with the Neighbor Joining heuristic both on biological and random data.

(Joint work with Prof. Martin Farach.)

Document last modified on November 27, 1996