Fast algorithm to reconstruct a species supertree from a set of protein trees

The problem of reconstructing a species supertree from a given set of protein, gene, and regulatorysite trees is the subject of this study. Under the traditional formulation, this problem is proven to be NP-hard. We propose a reformulation: to seek for a supertree, most of the clades of which contribute to the original protein trees. In such a variant, the problem seems to be biologically natural and a fast algorithm can be developed for its solution. The algorithm was tested on artificial and biological sets of protein trees, and it proved to be efficient even under the assumption of horizontal gene transfer. When horizontal transfer is not allowed, the algorithm correctness is proved mathematically; the time necessary for repeating the algorithm is assessed, and, in the worst case scenario, it is of the order n 3 · |V 0|3, where n is the number of gene trees and |V 0| is the number of tree species. Our software for supertree construction, examples of computations, and instructions can be freely accessed at http://lab6.iitp.ru/ru/super3gl/ . Events associated with horizontal gene transfer are not included either in this study or in any variant of the software. A general case is described in the authors’ report (journal Problems of Information Transmission, 2011).