### 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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 |

Publisher | Association for Computing Machinery |

Pages | 68-77 |

Number of pages | 10 |

ISBN (Electronic) | 0898713498 |

State | Published - Jan 22 1995 |

Event | 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 - San Francisco, United States Duration: Jan 22 1995 → Jan 24 1995 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995 |
---|---|

Country | United States |

City | San Francisco |

Period | 1/22/95 → 1/24/95 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

}

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 -