Tree reconstruction from partial orders

Sampath K. Kannan, Tandy Warnow

Research output: Contribution to journalArticle

Abstract

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. We are particularly 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.

Original languageEnglish (US)
Pages (from-to)511-519
Number of pages9
JournalSIAM Journal on Computing
Volume24
Issue number3
StatePublished - Jun 1995
Externally publishedYes

Fingerprint

Partial Order
Distance Matrix
Linguistics
Computational complexity
NP-complete problem
Polynomials
Biology
Pairwise
Polynomial time
Experiments
Optimization Problem
Norm
Experiment

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Applied Mathematics
  • Theoretical Computer Science

Cite this

Tree reconstruction from partial orders. / Kannan, Sampath K.; Warnow, Tandy.

In: SIAM Journal on Computing, Vol. 24, No. 3, 06.1995, p. 511-519.

Research output: Contribution to journalArticle

Kannan, SK & Warnow, T 1995, 'Tree reconstruction from partial orders', SIAM Journal on Computing, vol. 24, no. 3, pp. 511-519.
Kannan, Sampath K. ; Warnow, Tandy. / Tree reconstruction from partial orders. In: SIAM Journal on Computing. 1995 ; Vol. 24, No. 3. pp. 511-519.
@article{5a5c3535e4104f49a9eeab4bc60c598d,
title = "Tree reconstruction from partial orders",
abstract = "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. We are particularly 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.",
author = "Kannan, {Sampath K.} and Tandy Warnow",
year = "1995",
month = "6",
language = "English (US)",
volume = "24",
pages = "511--519",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

TY - JOUR

T1 - Tree reconstruction from partial orders

AU - Kannan, Sampath K.

AU - Warnow, Tandy

PY - 1995/6

Y1 - 1995/6

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. We are particularly 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. We are particularly 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=0029324437&partnerID=8YFLogxK

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

M3 - Article

AN - SCOPUS:0029324437

VL - 24

SP - 511

EP - 519

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 3

ER -