|
Vol 46(2012) N 1 p. 161-167; K.Y. Gorbunov*, V.A. Lyubetsky** Fast Algorithm to Reconstruct a Species Supertree from a Set of Protein Trees Kharkevich Institute of Information Transmission Problems, Russian Academy of Sciences, Moscow, 127994 Russia*lyubetsk@iitp.ru Received - 2011-07-29; Accepted - 2011-08-16 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 n3' species tree, species supertree, new formulation of the problem of supertree reconstruction, fast algorithm to reconstruct a supertree, generation of a gene set from a supertree, modeling the gene evolution along a species tree |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
