## 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 should be compared for consensus. It has become necessary to automate this process as the number of species under consideration has grown. We study one formalisation of the problem: the maximum agreement-subtree (MAST) problem. The MAST problem is as follows: given a set A and two rooted trees T_{0} and T_{1} leaf-labeled by the elements of A, find a maximum-cardinality subset B of A such that the topological restrictions of T_{0} and T_{1} to B are isomorphic. In this paper, we will show that this problem reduces to unary weighted bipartite matching (UWBM) with an O(n^{1+o(1)}) additive overhead. We also show that UWBM reduces linearly to MAST. Thus our algorithm is optimal unless UWBM can be solved in near linear time. The overall running time of our algorithm is O(n^{1.5} log n), improving on the previous best algorithm, which runs in O(n^{2}). We also derive an O(nc^{√log n})-time algorithm for the case of bounded degrees, whereas the previously best algorithm runs in O(n^{2}), as in the unbounded case.

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

Pages (from-to) | 210-230 |

Number of pages | 21 |

Journal | SIAM Journal on Computing |

Volume | 26 |

Issue number | 1 |

DOIs | |

State | Published - Feb 1997 |

## Keywords

- Computational biology
- Evolutionary trees
- Sparse dynamic programming

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics