DIMACS Seminar on Math and CS in Biology


Title:

Numerical Taxonomy: a new method and experimental results

Speaker:

Jaime Cohen
Rutgers University

Place:

Seminar Room 431, CoRE Building
Rutgers University.

Time:

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

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.)


dimacs-www@dimacs.rutgers.edu
Document last modified on November 27, 1996