Speaker:Lei Liu

Testing the Agreement of Trees with Internal Labels

The input to the agreement problem is a collection P = {T1 , T2, . . . , Tk } of phylogenetic trees, called input trees, over partially overlapping sets of taxa. The question is whether there exists a tree T , called an agreement tree, whose taxon set is the union of the taxon sets of the input trees, such that for each i ∈ { 1 , 2, . . . , k }, the restriction of T to the taxon set of Ti is isomorphic to Ti. We give a O (nk ( P i ∈ [ k ] d i + log 2 (nk))) algorithm for a generalization of the agreement problem in which the input trees may have internal labels, where n is the total number of distinct taxa in P , k is the number of trees in P, and d i is the maximum number of children of a node in Ti .

Committee: David Fernández-Baca (major professor), Oliver Eulenstein, Xiaoqiu Huang, Pavan Aduri, and Ryan Martin(Math).