Computing the local consensus of trees

Sampath Kannan, Tandy Warnow, Shibu Yooseph

Research output: Contribution to journalArticle

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

Fingerprint

Computing
Linguistics
Polynomials
Evolutionary Tree
Tie
Linear-time Algorithm
Model
Biology
Linear Time
Polynomial time
Optimization Problem
Partial

Keywords

  • Algorithms
  • Evolutionary trees
  • Graphs

ASJC Scopus subject areas

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

Cite this

Computing the local consensus of trees. / Kannan, Sampath; Warnow, Tandy; Yooseph, Shibu.

In: SIAM Journal on Computing, Vol. 27, No. 6, 12.1998, p. 1695-1724.

Research output: Contribution to journalArticle

Kannan, Sampath ; Warnow, Tandy ; Yooseph, Shibu. / Computing the local consensus of trees. In: SIAM Journal on Computing. 1998 ; Vol. 27, No. 6. pp. 1695-1724.
@article{cfb3287fed5e4fbfbc9d0e8dd36c47e7,
title = "Computing the local consensus of trees",
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.",
keywords = "Algorithms, Evolutionary trees, Graphs",
author = "Sampath Kannan and Tandy Warnow and Shibu Yooseph",
year = "1998",
month = "12",
doi = "10.1137/S0097539795287642",
language = "English (US)",
volume = "27",
pages = "1695--1724",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "6",

}

TY - JOUR

T1 - Computing the local consensus of trees

AU - Kannan, Sampath

AU - Warnow, Tandy

AU - Yooseph, Shibu

PY - 1998/12

Y1 - 1998/12

N2 - 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.

AB - 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.

KW - Algorithms

KW - Evolutionary trees

KW - Graphs

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

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

U2 - 10.1137/S0097539795287642

DO - 10.1137/S0097539795287642

M3 - Article

AN - SCOPUS:0032315457

VL - 27

SP - 1695

EP - 1724

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 6

ER -