A robust model for finding optimal evolutionary trees extended abstract

Martin Farach, Sampath Kannan, Tandy Warnow

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

Abstract

Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species and seeks to find an edge-weighted tree T in which the distance dijT in the tree between the leaves of T corresponding to the species i and j fits the observed distance, dij. Sometimes the desired tree is ultrametric, so that the tree can be rooted with the root equidistant to each leaf. Many measures for evaluating the `fit' between a distance function d and the path-distance dT have been proposed, and most such measures have resulted in NP-hard optimization problems. In this paper we propose a measure of fit which models the inaccuracy in the data, and present several problems for constructing additive and ultrametric trees using this measure. Many of the resultant optimization problems are NP-hard, and one (finding a minimum size ultrametric tree which increments from an input matrix) is hard to approximate. Specifically, there is a constant c>0 such that unless P = NP, no polynomial time algorithm can exist which finds an approximate solution within the ratio of nc. However, we also present tight upper and lower bounds for the L-Minimum Increment to Ultrametric. Thus, we present perhaps the first algorithm for constructing phylogenetic trees from distance matrices which finds optimal trees for a reasonable criterion in polynomial time.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993
PublisherAssociation for Computing Machinery
Pages137-145
Number of pages9
ISBN (Electronic)0897915917
DOIs
StatePublished - Jun 1 1993
Event25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States
Duration: May 16 1993May 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129585
ISSN (Print)0737-8017

Other

Other25th Annual ACM Symposium on Theory of Computing, STOC 1993
CountryUnited States
CitySan Diego
Period5/16/935/18/93

Fingerprint

Polynomials
Computational complexity

ASJC Scopus subject areas

  • Software

Cite this

Farach, M., Kannan, S., & Warnow, T. (1993). A robust model for finding optimal evolutionary trees extended abstract. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993 (pp. 137-145). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129585). Association for Computing Machinery. https://doi.org/10.1145/167088.167132

A robust model for finding optimal evolutionary trees extended abstract. / Farach, Martin; Kannan, Sampath; Warnow, Tandy.

Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, 1993. p. 137-145 (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129585).

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

Farach, M, Kannan, S & Warnow, T 1993, A robust model for finding optimal evolutionary trees extended abstract. in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Proceedings of the Annual ACM Symposium on Theory of Computing, vol. Part F129585, Association for Computing Machinery, pp. 137-145, 25th Annual ACM Symposium on Theory of Computing, STOC 1993, San Diego, United States, 5/16/93. https://doi.org/10.1145/167088.167132
Farach M, Kannan S, Warnow T. A robust model for finding optimal evolutionary trees extended abstract. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery. 1993. p. 137-145. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/167088.167132
Farach, Martin ; Kannan, Sampath ; Warnow, Tandy. / A robust model for finding optimal evolutionary trees extended abstract. Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993. Association for Computing Machinery, 1993. pp. 137-145 (Proceedings of the Annual ACM Symposium on Theory of Computing).
@inproceedings{9ae1587e2a7041679624f197124a0305,
title = "A robust model for finding optimal evolutionary trees extended abstract",
abstract = "Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species and seeks to find an edge-weighted tree T in which the distance dijT in the tree between the leaves of T corresponding to the species i and j fits the observed distance, dij. Sometimes the desired tree is ultrametric, so that the tree can be rooted with the root equidistant to each leaf. Many measures for evaluating the `fit' between a distance function d and the path-distance dT have been proposed, and most such measures have resulted in NP-hard optimization problems. In this paper we propose a measure of fit which models the inaccuracy in the data, and present several problems for constructing additive and ultrametric trees using this measure. Many of the resultant optimization problems are NP-hard, and one (finding a minimum size ultrametric tree which increments from an input matrix) is hard to approximate. Specifically, there is a constant c>0 such that unless P = NP, no polynomial time algorithm can exist which finds an approximate solution within the ratio of nc. However, we also present tight upper and lower bounds for the L∞-Minimum Increment to Ultrametric. Thus, we present perhaps the first algorithm for constructing phylogenetic trees from distance matrices which finds optimal trees for a reasonable criterion in polynomial time.",
author = "Martin Farach and Sampath Kannan and Tandy Warnow",
year = "1993",
month = "6",
day = "1",
doi = "10.1145/167088.167132",
language = "English (US)",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "137--145",
booktitle = "Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993",

}

TY - GEN

T1 - A robust model for finding optimal evolutionary trees extended abstract

AU - Farach, Martin

AU - Kannan, Sampath

AU - Warnow, Tandy

PY - 1993/6/1

Y1 - 1993/6/1

N2 - Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species and seeks to find an edge-weighted tree T in which the distance dijT in the tree between the leaves of T corresponding to the species i and j fits the observed distance, dij. Sometimes the desired tree is ultrametric, so that the tree can be rooted with the root equidistant to each leaf. Many measures for evaluating the `fit' between a distance function d and the path-distance dT have been proposed, and most such measures have resulted in NP-hard optimization problems. In this paper we propose a measure of fit which models the inaccuracy in the data, and present several problems for constructing additive and ultrametric trees using this measure. Many of the resultant optimization problems are NP-hard, and one (finding a minimum size ultrametric tree which increments from an input matrix) is hard to approximate. Specifically, there is a constant c>0 such that unless P = NP, no polynomial time algorithm can exist which finds an approximate solution within the ratio of nc. However, we also present tight upper and lower bounds for the L∞-Minimum Increment to Ultrametric. Thus, we present perhaps the first algorithm for constructing phylogenetic trees from distance matrices which finds optimal trees for a reasonable criterion in polynomial time.

AB - Constructing evolutionary trees for species sets is a fundamental problem in computational biology. One of the standard models assumes the ability to compute distances between every pair of species and seeks to find an edge-weighted tree T in which the distance dijT in the tree between the leaves of T corresponding to the species i and j fits the observed distance, dij. Sometimes the desired tree is ultrametric, so that the tree can be rooted with the root equidistant to each leaf. Many measures for evaluating the `fit' between a distance function d and the path-distance dT have been proposed, and most such measures have resulted in NP-hard optimization problems. In this paper we propose a measure of fit which models the inaccuracy in the data, and present several problems for constructing additive and ultrametric trees using this measure. Many of the resultant optimization problems are NP-hard, and one (finding a minimum size ultrametric tree which increments from an input matrix) is hard to approximate. Specifically, there is a constant c>0 such that unless P = NP, no polynomial time algorithm can exist which finds an approximate solution within the ratio of nc. However, we also present tight upper and lower bounds for the L∞-Minimum Increment to Ultrametric. Thus, we present perhaps the first algorithm for constructing phylogenetic trees from distance matrices which finds optimal trees for a reasonable criterion in polynomial time.

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

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

U2 - 10.1145/167088.167132

DO - 10.1145/167088.167132

M3 - Conference contribution

AN - SCOPUS:0027307380

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 137

EP - 145

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993

PB - Association for Computing Machinery

ER -