PUB - Publikationen an der Universität Bielefeld

Phylogeny estimation, that is the inference of the evolutionary history of the various life forms (species) on earth, is a widely studied problem that is not yet solved to satisfaction. Studying the strengths and weaknesses of current methods that work on biosequence data, branch attraction phenomena due to unequal amounts of evolutionary change in different parts of the phylogeny are one major problem, placing the species that evolved fast in one part of the phylogenetic tree, and the species that evolved slowly in the other. We improve the current state of the art by describing a way to avoid the attraction of species that evolved slowly, and hence share old ("symplesiomorphic") character states. These leftover character states have "eroded" away in the other species. They are detected using a calibrated comparison with an outgroup, and contrasted with shared novel ("synapomorphic") character states that testify the exclusive common heritage of a subset of the species. Torn apart, these shared novelties indicate conflict in a split of all species considered, and only the split at the root of the phylogenetic tree cannot have such conflict. Therefore, we can work top-down, by heuristically searching for a minimum-conflict split, and tackling the resulting two subsets in the same way. This application of the divide-and-conquer principle, together with an intelligent search for mininum-conflict splits based on the exchange of species that carry the conflict, results in a fast, simple and transparent phylogeny estimation algorithm. The algorithm, called "minimum conflict phylogeny estimation" (MCOPE), is validated intensively using both real and artificial data.