## Abstract

Constructing evolutionary trees for species sets is a fundamental problem in biology. Unfortunately, there is no single agreed upon method for this task, and many methods are in use. Current practice dictates that trees be constructed using different methods and that the resulting trees then be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study the Unrooted Maximum Agreement Subtree Problem (UMAST) and its rooted variant (RMAST). The UMAST problem is as follows: given a set A and two trees T_{0} and T_{1} leaf-labeled by the elements of A, find a maximum cardinality subset B of A such that the restrictions of T_{0} and T_{1} to B are topologically isomorphic. Our main result is an O(n^{2 + o(1)}) time algorithm for the UMAST problem. We also derive an O(n^{2}) time algorithm for the RMAST problem. The previous best algorithm for both these problems has running time O(n^{4.5 + o(1)}).

Original language | English (US) |
---|---|

Pages (from-to) | 29-37 |

Number of pages | 9 |

Journal | Information and Computation |

Volume | 123 |

Issue number | 1 |

DOIs | |

State | Published - Nov 15 1995 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics