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 dTij in the tree between the leaves of T corresponding to the species i and j fits the observed distance, 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 T have been prposed, and most such measures have resulted in NP-hard optimization problems. T 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 ;VP-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 ne. However, we also present tight upper and lower bounds for the L∞-Minimum Increment to Ultrametric. Thus, wc present perhaps the first algorithm for constructing phylogcnctic 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

    Conference

    Conference25th Annual ACM Symposium on Theory of Computing, STOC 1993
    Country/TerritoryUnited States
    CitySan Diego
    Period5/16/935/18/93

    ASJC Scopus subject areas

    • Software

    Fingerprint

    Dive into the research topics of 'A robust model for finding optimal evolutionary trees extended abstract'. Together they form a unique fingerprint.

    Cite this