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.
Paru en avril 1997 , 23 pages