Tree reconstruction from partial orders

Sampath Kannan, Tandy Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationAlgorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings
EditorsFrank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides
PublisherSpringer-Verlag
Pages397-408
Number of pages12
ISBN (Print)9783540571551
StatePublished - Jan 1 1993
Externally publishedYes
Event3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada
Duration: Aug 11 1993Aug 13 1993

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume709 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Workshop on Algorithms and Data Structures, WADS 1993
CountryCanada
CityMontreal
Period8/11/938/13/93

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

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Kannan, S., & Warnow, T. (1993). Tree reconstruction from partial orders. In F. Dehne, J-R. Sack, N. Santoro, & S. Whitesides (Eds.), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings (pp. 397-408). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS). Springer-Verlag.

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

Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. ed. / Frank Dehne; Jorg-Rudiger Sack; Nicola Santoro; Sue Whitesides. Springer-Verlag, 1993. p. 397-408 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 709 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Kannan, S & Warnow, T 1993, Tree reconstruction from partial orders. in F Dehne, J-R Sack, N Santoro & S Whitesides (eds), Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 709 LNCS, Springer-Verlag, pp. 397-408, 3rd Workshop on Algorithms and Data Structures, WADS 1993, Montreal, Canada, 8/11/93.
Kannan S, Warnow T. Tree reconstruction from partial orders. In Dehne F, Sack J-R, Santoro N, Whitesides S, editors, Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. Springer-Verlag. 1993. p. 397-408. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Kannan, Sampath ; Warnow, Tandy. / Tree reconstruction from partial orders. Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings. editor / Frank Dehne ; Jorg-Rudiger Sack ; Nicola Santoro ; Sue Whitesides. Springer-Verlag, 1993. pp. 397-408 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{d8088e8e608b405c8756faba4643ab38,
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. 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.",
author = "Sampath Kannan and Tandy Warnow",
year = "1993",
month = "1",
day = "1",
language = "English (US)",
isbn = "9783540571551",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "397--408",
editor = "Frank Dehne and Jorg-Rudiger Sack and Nicola Santoro and Sue Whitesides",
booktitle = "Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings",

}

TY - GEN

T1 - Tree reconstruction from partial orders

AU - Kannan, Sampath

AU - Warnow, Tandy

PY - 1993/1/1

Y1 - 1993/1/1

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

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-Verlag

ER -