TY - GEN
T1 - The asymmetric median tree - A new model for building consensus trees
AU - Phillips, Cynthia
AU - Warnow, Tandy J.
N1 - * Corresponding author. E-mail: [email protected]. Research partly supported by an NSF National Young Investigator Award under contract CCR-9457800, by an NSF grant in Linguistics under contract SBR-9512092, by the Institute for Research in Cognitive Science at the University of Pennsylvania, and by generous financial support from Paul Angello. ’ This work was performed under US Department of Energy under contract DE-ACO4-76AL85000.
PY - 1996
Y1 - 1996
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, 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.
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, 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.
UR - https://www.scopus.com/pages/publications/84857044524
UR - https://www.scopus.com/inward/citedby.url?scp=84857044524&partnerID=8YFLogxK
U2 - 10.1007/3-540-61258-0_18
DO - 10.1007/3-540-61258-0_18
M3 - Conference contribution
AN - SCOPUS:84857044524
SN - 3540612580
SN - 9783540612582
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 234
EP - 252
BT - Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings
A2 - Myers, Gene
A2 - Hirschberg, Dan
PB - Springer
T2 - 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996
Y2 - 10 June 1996 through 12 June 1996
ER -