TY - GEN

T1 - Tree reconstruction from partial orders

AU - Kannan, Sampath

AU - Warnow, Tandy

N1 - Funding Information:
However, for many applications, the actual numeric data is quite unreliable (see \[4, 6\] for discussions of how interspecies distances are derived in computational molecular biology and why the data is unreliable). One way of handling * Supported in part by NSF Grant CCR9108969 *~ This work began when this author was visiting DIMACS, and was supported in part by DOE contract number DE-AC04-76DP00789.
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.

PY - 1993

Y1 - 1993

N2 - The problem of constructing trees given a matrix of interleaf distances is motivated by applications in computational evolutionary biology and linguistics. The general problem is to find an edge-weighted tree which most closely approximates (under some norm) the distance matrix. Although the construction problem is easy when the tree exactly fits the distance matrix, optimization problems under all popular criteria are either known or conjectured to be NP-complete. In this paper we consider the related problem where we are given a partial order on the pairwise distances, and wish to construct (if possible) an edge-weighted tree realizing the partial order. In particular we are interested in partial orders which arise from experiments on triples of species. We will show that the consistency problem is NP-hard in general, but that for certain special cases the construction problem can be solved in polynomial time.

AB - The problem of constructing trees given a matrix of interleaf distances is motivated by applications in computational evolutionary biology and linguistics. The general problem is to find an edge-weighted tree which most closely approximates (under some norm) the distance matrix. Although the construction problem is easy when the tree exactly fits the distance matrix, optimization problems under all popular criteria are either known or conjectured to be NP-complete. In this paper we consider the related problem where we are given a partial order on the pairwise distances, and wish to construct (if possible) an edge-weighted tree realizing the partial order. In particular we are interested in partial orders which arise from experiments on triples of species. We will show that the consistency problem is NP-hard in general, but that for certain special cases the construction problem can be solved in polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=85029502449&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029502449&partnerID=8YFLogxK

U2 - 10.1007/3-540-57155-8_265

DO - 10.1007/3-540-57155-8_265

M3 - Conference contribution

AN - SCOPUS:85029502449

SN - 9783540571551

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 397

EP - 408

BT - Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings

A2 - Dehne, Frank

A2 - Sack, Jorg-Rudiger

A2 - Santoro, Nicola

A2 - Whitesides, Sue

PB - Springer

T2 - 3rd Workshop on Algorithms and Data Structures, WADS 1993

Y2 - 11 August 1993 through 13 August 1993

ER -