A Linear-time Algorithm for Optimal Tree Completion

摘要

A phylogenetic tree, a tree representing evolution among species, is a general tool for bioinformatics. It is increasingly common to have more than one trees for an interested set of species. When there is a one important tree t with missing species, one would like to complete it with a reference tree T that contains all species while ensuring that the resulting tree maintains the structure of t. Christensen, Molloy, Vachaspati and Warnow [Algorithms for Molecular Biology, 2018] addressed this issue by formulating the Optimal Tree Completion Problem. They presented an optimal algorithm called OCTAL that works in O (n²) time where n is the number of species in T. They also proved that OCTAL minimizes the Robinson-Foulds distance between T' and T. We show that this can be done more efficiently by presenting an O(n)-time implementation of their algorithm.