TREE RECONSTRUCTION FROM PARTIAL ORDERS

The problem of constructing trees given a matrix of interleaf distance s is motivated by applications in computational evolutionary biology a nd linguistics. The general problem is to find an edge-weighted tree w hich most closely approximates (under some norm) the distance matrix. Although the construction problem is easy when the tree exactly fits t he distance matrix, optimization problems under all popular criteria a re either known or conjectured to be NP-complete. In this paper we con sider the related problem where we are given a partial order on the pa irwise distances and wish to construct (if possible) an edge-weighted tree realizing the partial order. We are particularly interested in pa rtial orders which arise from experiments on triples of species. We wi ll show that the consistency problem is NP-hard in general, but that f or certain special cases the construction problem can be solved in pol ynomial time.