Groupe d’études et de recherche en analyse des décisions


Inferring Evolutionary Trees with Strong Combinatorial Evidence


We consider the problem of inferring evolutionary trees. We propose a quartet reconstruction method which specifically produces trees whose edges have strong combinatorial evidence. For this purpose we use the Q* relation introduced by Bandelt and Dress (1986), which they demonstrated to be definable as the maximum subset of resolved quartets which is equivalent to a tree. We further investigate the properties of this variation of the NP-hard quartet consistency problem, first providing a polynomial time, O(n4), algorithm, where n is the number of species. Moreover, we show that the convergence rate of the method, under the Cavender-Farris model of evolution, is polynomial for realistic conditions. Last, we exemplify the method on a set of mammal DNA sequences.

, 23 pages