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 language | English (US) |
|---|---|
| Title of host publication | Algorithms and Data Structures - 3rd Workshop, WADS 1993, Proceedings |
| Editors | Frank Dehne, Jorg-Rudiger Sack, Nicola Santoro, Sue Whitesides |
| Publisher | Springer-Verlag |
| Pages | 397-408 |
| Number of pages | 12 |
| ISBN (Print) | 9783540571551 |
| State | Published - Jan 1 1993 |
| Event | 3rd Workshop on Algorithms and Data Structures, WADS 1993 - Montreal, Canada Duration: Aug 11 1993 → Aug 13 1993 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 709 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Other
| Other | 3rd Workshop on Algorithms and Data Structures, WADS 1993 |
|---|---|
| Country | Canada |
| City | Montreal |
| Period | 8/11/93 → 8/13/93 |
Fingerprint
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)
Cite this
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 proceeding › Conference contribution
}
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 -