SPRIT: Identifying horizontal gene transfer in rooted phylogenetic treesReportar como inadecuado

SPRIT: Identifying horizontal gene transfer in rooted phylogenetic trees - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

BMC Evolutionary Biology

, 10:42

First Online: 13 February 2010Received: 23 April 2009Accepted: 13 February 2010


BackgroundPhylogenetic trees based on sequences from a set of taxa can be incongruent due to horizontal gene transfer HGT. By identifying the HGT events, we can reconcile the gene trees and derive a taxon tree that adequately represents the species- evolutionary history. One HGT can be represented by a rooted Subtree Prune and Regraft RSPR operation and the number of RSPRs separating two trees corresponds to the minimum number of HGT events. Identifying the minimum number of RSPRs separating two trees is NP-hard, but the problem can be reduced to fixed parameter tractable. A number of heuristic and two exact approaches to identifying the minimum number of RSPRs have been proposed. This is the first implementation delivering an exact solution as well as the intermediate trees connecting the input trees.

ResultsWe present the SPR Identification Tool SPRIT, a novel algorithm that solves the fixed parameter tractable minimum RSPR problem and its GPL licensed Java implementation. The algorithm can be used in two ways, exhaustive search that guarantees the minimum RSPR distance and a heuristic approach that guarantees finding a solution, but not necessarily the minimum one. We benchmarked SPRIT against other software in two different settings, small to medium sized trees i.e. five to one hundred taxa and large trees i.e. thousands of taxa. In the small to medium tree size setting with random artificial incongruence, SPRIT-s heuristic mode outperforms the other software by always delivering a solution with a low overestimation of the RSPR distance. In the large tree setting SPRIT compares well to the alternatives when benchmarked on finding a minimum solution within a reasonable time. SPRIT presents both the minimum RSPR distance and the intermediate trees.

ConclusionsWhen used in exhaustive search mode, SPRIT identifies the minimum number of RSPRs needed to reconcile two incongruent rooted trees. SPRIT also performs quick approximations of the minimum RSPR distance, which are comparable to, and often better than, purely heuristic solutions. Put together, SPRIT is an excellent tool for identification of HGT events and pinpointing which taxa have been involved in HGT.

AbbreviationsRSPRRooted subtrees prune and regraft

dRSPRminimum RSPR distance

SPRITSPR Identification Tool

EEEPEfficient Evaluation of Edit Paths

HGTHorizontal Gene Transfer

NPNondeterministic Polynomial

MCCMinimal Common Cluster

SCCSolvable Common Cluster.

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

Download fulltext PDF

Autor: Tobias Hill - Karl JV Nordström - Mikael Thollesson - Tommy M Säfström - Andreas KE Vernersson - Robert Fredriksson -

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

Documentos relacionados