Abstract
An evolutionary tree is a rooted, leaf-labeled tree. Each internal node of the tree has at least two children. Constructing evolutionary trees for the given species is a fundamental work in computational biology. Unfortunately, different algorithms usually produce different evolutionary trees and different research may have different evolutionary trees even on the same set of the species. It becomes more necessary to know the consensus between those trees recently. We focus on one of the consensus problems and agreement problems: the maximum agreement subtree (MAST) problem. The MAST problem is as follow : given a set a set T = { T1, T2, T3, …, Tk } of leaf-labeled trees on leaf-labeled set L where T1 is a binary tree, find a maximum cardinality subset X of L such that the topological restrictions of T1, T2, T3, …, Tk are isomorphic. In this paper, we introduce Bryant’s algorithm first and use domination to improve Bryant’s algorithm and implement by bridged range search tree method. Although the time cost is O( (n^2)(logn)^k ), the same to original paper, but the implementation is quicker than before.