Your browser doesn't support javascript.
loading
Fast local search for unrooted Robinson-Foulds supertrees.
Artigo em Inglês | MEDLINE | ID: mdl-22431553
ABSTRACT
A Robinson-Foulds (RF) supertree for a collection of input trees is a tree containing all the species in the input trees that is at minimum total RF distance to the input trees. Thus, an RF supertree is consistent with the maximum number of splits in the input trees. Constructing RF supertrees for rooted and unrooted data is NP-hard. Nevertheless, effective local search heuristics have been developed for the restricted case where the input trees and the supertree are rooted. We describe new heuristics, based on the Edge Contract and Refine (ECR) operation, that remove this restriction, thereby expanding the utility of RF supertrees. Our experimental results on simulated and empirical data sets show that our unrooted local search algorithms yield better supertrees than those obtained from MRP and rooted RF heuristics in terms of total RF distance to the input trees and, for simulated data, in terms of RF distance to the true tree.
Assuntos

Similares

MEDLINE

...
LILACS

LIS

Texto completo: Disponível Coleções: Bases de dados internacionais Base de dados: MEDLINE Assunto principal: Filogenia / Algoritmos / Biologia Computacional Idioma: Inglês Revista: ACM Trans Comput Biol Bioinform Assunto da revista: Biologia / Informática Médica Ano de publicação: 2012 Tipo de documento: Artigo País de afiliação: Estados Unidos