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

Cynthia Phillips, Tandy Warnow

Research output: Contribution to journalArticle

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, (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 in use (strict consensus, majority tree, Nelson tree). Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use.

Original languageEnglish (US)
Pages (from-to)311-335
Number of pages25
JournalDiscrete Applied Mathematics
Volume71
Issue number1-3
DOIs
StatePublished - Dec 5 1996
Externally publishedYes

Fingerprint

Trees (mathematics)
Approximation algorithms
Computational complexity
Polynomials
Model
Evolutionary Tree
K-tree
Colored Graph
Maximum Independent Set
Approximate Algorithm
Phylogenetics
Exact Algorithms
Polynomial-time Algorithm
Standard Model
Approximation Algorithms
NP-complete problem
Equivalence
Optimization Problem

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this

The asymmetric median tree - A new model for building consensus trees. / Phillips, Cynthia; Warnow, Tandy.

In: Discrete Applied Mathematics, Vol. 71, No. 1-3, 05.12.1996, p. 311-335.

Research output: Contribution to journalArticle

@article{d63aa682f6a84823be44087f46dec7d5,
title = "The asymmetric median tree - A new model for building consensus trees",
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, (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 in use (strict consensus, majority tree, Nelson tree). Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use.",
author = "Cynthia Phillips and Tandy Warnow",
year = "1996",
month = "12",
day = "5",
doi = "10.1016/S0166-218X(96)00071-6",
language = "English (US)",
volume = "71",
pages = "311--335",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "1-3",

}

TY - JOUR

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

AU - Phillips, Cynthia

AU - Warnow, Tandy

PY - 1996/12/5

Y1 - 1996/12/5

N2 - 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, (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 in use (strict consensus, majority tree, Nelson tree). Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use.

AB - 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, (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 in use (strict consensus, majority tree, Nelson tree). Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use.

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

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

U2 - 10.1016/S0166-218X(96)00071-6

DO - 10.1016/S0166-218X(96)00071-6

M3 - Article

AN - SCOPUS:0042014724

VL - 71

SP - 311

EP - 335

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 1-3

ER -