TY - GEN
T1 - Computing the local consensus of trees
AU - Kannan, Sampath
AU - Warnow, Tandy
AU - Yooseph, Shibu
N1 - Funding Information:
in part by NSF grant CCR-9108969. in part by AR0 grant DAAL03-89-0031PRI in part by AR0 grant DAAL03-89-0031PRI
Funding Information:
Supported in part by NSF grant CCR-9108969 Supported in part by ARO grant DAAL03-89-0031PRI Supported in part by ARO grant DAAL03-89-0031PRI
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
T2 - 6th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1995
Y2 - 22 January 1995 through 24 January 1995
ER -