The asymmetric median tree - A new model for building consensus trees

Cynthia Phillips, Tandy J. Warnow

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

Abstract

Inferring the consensus of a set of different evolutionary trees for a given species set is a well-studied problem, for which several different models have been proposed. In this paper, we propose a new optimization problem for consensus tree construction, which we call the asymmetric median tree, or AMT. Our main theoretical result is the equivalence between the asymmetric median tree problem on k trees and the maximum independent set (MIS) problem on k-colored graphs. Although the problem is NP-hard for three or more trees, we have polynomial time algorithms to construct the AMT for two trees and an approximation algorithm for three or more trees. We define a measure of phylogenetic resolution and show that our algorithms (both exact and approximate) produce consensus trees that on every input are at least as resolved as the standard models (strict consensus and majority tree) in use. Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use.

Original languageEnglish (US)
Title of host publicationCombinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings
EditorsGene Myers, Dan Hirschberg
PublisherSpringer-Verlag Berlin Heidelberg
Pages234-252
Number of pages19
ISBN (Print)3540612580, 9783540612582
DOIs
StatePublished - Jan 1 1996
Externally publishedYes
Event7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 - Laguna Beach, United States
Duration: Jun 10 1996Jun 12 1996

Publication series

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

Other

Other7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996
CountryUnited States
CityLaguna Beach
Period6/10/966/12/96

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'The asymmetric median tree - A new model for building consensus trees'. Together they form a unique fingerprint.

  • Cite this

    Phillips, C., & Warnow, T. J. (1996). The asymmetric median tree - A new model for building consensus trees. In G. Myers, & D. Hirschberg (Eds.), Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings (pp. 234-252). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1075). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/3-540-61258-0_18