THE ASYMMETRIC MEDIAN TREE - A NEW MODEL FOR BUILDING CONSENSUS TREES

Inferring the consensus of a set of different evolutionary trees for a given species set is a well-studied problem, for which several differ ent models have been proposed. In this paper, we propose a new optimiz ation problem for consensus tree construction, which we call the asymm etric median tree, (AMT). Our main theoretical result is the equivalen ce between the asymmetric median tree problem on k trees and the maxim um independent set (MIS) problem on k-colored graphs. Although the pro blem is NP-hard for three or more trees, we have polynomial-time algor ithms to construct the AMT for two trees and an approximation algorith m for three or more trees. We define a measure of phylogenetic resolut ion and show that our algorithms (both exact and approximate) produce consensus trees that on every input are at least as resolved as the st andard models in use (strict consensus, majority tree, Nelson tree). F inally, we show that the AMT combines desirable features of many of th e standard consensus tree models in use.