Computing the local consensus of trees

Sampath Kannan, Tandy Warnow, Shibu Yooseph

Research output: Contribution to journalArticlepeer-review

Abstract

The inference of consensus from a set of evolutionary trees is a fundamental problem in a number of fields such as biology and historical linguistics, and many models for inferring this consensus have been proposed. In this paper we present a model for deriving what we call a local consensus tree T from a set of trees T. The model we propose presumes a function f, called a total local consensus function, which determines for every triple A of species, the form that the local consensus tree should take on A. We show that all local consensus trees, when they exist, can be constructed in polynomial time and that many fundamental problems can be solved in linear time. We also consider partial local consensus functions and study optimization problems under this model. We present linear time algorithms for several variations. Finally we point out that the local consensus approach ties together many previous approaches to constructing consensus trees.

Original languageEnglish (US)
Pages (from-to)1695-1724
Number of pages30
JournalSIAM Journal on Computing
Volume27
Issue number6
DOIs
StatePublished - Dec 1998
Externally publishedYes

Keywords

  • Algorithms
  • Evolutionary trees
  • Graphs

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Applied Mathematics
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Computing the local consensus of trees'. Together they form a unique fingerprint.

Cite this