On Hill et als conjecture for calculating the subtree prune and regraft distance between phylogeniesReportar como inadecuado




On Hill et als conjecture for calculating the subtree prune and regraft distance between phylogenies - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

BMC Evolutionary Biology

, 10:334

First Online: 29 October 2010Received: 21 June 2010Accepted: 29 October 2010

Abstract

BackgroundRecently, Hill et al. 1 implemented a new software package-called SPRIT-which aims at calculating the minimum number of horizontal gene transfer events that is needed to simultaneously explain the evolution of two rooted binary phylogenetic trees on the same set of taxa. To this end, SPRIT computes the closely related so-called rooted subtree prune and regraft distance between two phylogenies. However, calculating this distance is an NP-hard problem and exact algorithms are often only applicable to small- or medium-sized problem instances. Trying to overcome this problem, Hill et al. propose a divide-and-conquer approach to speed up their algorithm and conjecture that this approach can be used to compute the rooted subtree prune and regraft distance exactly.

ResultsIn this note, we present a counterexample to Hill et al-s conjecture and subsequently show that a modified version of their conjecture holds.

ConclusionWhile Hill et al-s conjecture may result in an overestimate of the rooted subtree prune and regraft distance, a slightly more restricted version of their approach gives the desired outcome and can be applied to speed up the exact calculation of this distance between two phylogenies.

Electronic supplementary materialThe online version of this article doi:10.1186-1471-2148-10-334 contains supplementary material, which is available to authorized users.

Download fulltext PDF



Autor: Simone Linz

Fuente: https://link.springer.com/article/10.1186/1471-2148-10-334







Documentos relacionados