Computing the local consensus of trees

Sampath Kannan, Tandy Warnow, Shibu Yooseph

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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, called a total local consensus rule, 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 consensus rules 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)
Title of host publicationProceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
PublisherAssociation for Computing Machinery
Pages68-77
Number of pages10
ISBN (Electronic)0898713498
StatePublished - Jan 22 1995
Externally publishedYes
Event6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States
Duration: Jan 22 1995Jan 24 1995

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
CountryUnited States
CitySan Francisco
Period1/22/951/24/95

Fingerprint

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

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Kannan, S., Warnow, T., & Yooseph, S. (1995). Computing the local consensus of trees. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 (pp. 68-77). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.

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

Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery, 1995. p. 68-77 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Kannan, S, Warnow, T & Yooseph, S 1995, Computing the local consensus of trees. in Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 68-77, 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995, San Francisco, United States, 1/22/95.
Kannan S, Warnow T, Yooseph S. Computing the local consensus of trees. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery. 1995. p. 68-77. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
Kannan, Sampath ; Warnow, Tandy ; Yooseph, Shibu. / Computing the local consensus of trees. Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995. Association for Computing Machinery, 1995. pp. 68-77 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{3f9bbeb639f44019a29b305527793573,
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, called a total local consensus rule, 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 consensus rules 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.",
author = "Sampath Kannan and Tandy Warnow and Shibu Yooseph",
year = "1995",
month = "1",
day = "22",
language = "English (US)",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
publisher = "Association for Computing Machinery",
pages = "68--77",
booktitle = "Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995",

}

TY - GEN

T1 - Computing the local consensus of trees

AU - Kannan, Sampath

AU - Warnow, Tandy

AU - Yooseph, Shibu

PY - 1995/1/22

Y1 - 1995/1/22

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, called a total local consensus rule, 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 consensus rules 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, called a total local consensus rule, 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 consensus rules 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.

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

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

M3 - Conference contribution

AN - SCOPUS:84947921814

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 68

EP - 77

BT - Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995

PB - Association for Computing Machinery

ER -