SPRIT: Identifying horizontal gene transfer in rooted phylogenetic trees.

BACKGROUND: Phylogenetic 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. RESULTS: We 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. CONCLUSIONS: When 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.

Genetic algorithm for large-scale maximum parsimony phylogenetic analysis of proteins.

Inferring phylogeny is a difficult computational problem. For example, for only 13 taxa, there are more then 13 billion possible unrooted phylogenetic trees. Heuristics are necessary to minimize the time spent evaluating non-optimal trees. We describe here an approach for heuristic searching, using a genetic algorithm, that can reduce the time required for weighted maximum parsimony phylogenetic inference, especially for data sets involving a large number of taxa. It is the first implementation of a weighted maximum parsimony criterion using amino acid sequences. To validate the weighted criterion, we used an artificial data set and compared it to a number of other phylogenetic methods. Genetic algorithms mimic the natural selection's ability to solve complex problems. We have identified several parameters affecting the genetic algorithm. Methods were developed to validate these parameters, ensuring optimal performance. This approach allows the construction of phylogenetic trees with over 200 taxa in practical time on a regular PC.

Evaluation of EST-data using the genome assembly.

Using expressed sequence tag (EST) data for genomewide studies requires thorough understanding of the nature of the problems that are related to handling these sequences. We investigated how EST clustering performs when the genome is used as guidance as compared to pairwise sequence alignment methods. We show that clustering with the genome as a template outperforms sequence similarity methods used to create other EST clusters, such as the UniGene set, in respect to the extent ESTs originating from the same transcriptional unit are separated into disjunct clusters. Using our approach, approximately 80% of the RefSeq genes were represented by a single EST cluster and 20% comprised of two or more EST clusters. In contrast, approximately 25% of all RefSeq genes were found to be represented by a single cluster for the UniGene clustering method. The approach minimizes the risk for overestimations due to the amount of disjunct clusters originating from the same transcript. We have also investigated the quality of EST-data by aligning ESTs to the genome. The results show how many ESTs are not adequately trimmed in respect of vector sequences and low quality regions. Moreover, we identified important problems related to ESTs aligned to the genome using BLAT, such as inferring splice junctions, and explained this aspect by simulations with synthetic data. EST-clusters created with the method are available upon request from the authors.

Comparison of the current RefSeq, Ensembl and EST databases for counting genes and gene discovery.

Large amounts of refined sequence material in the form of predicted, curated and annotated genes and expressed sequences tags (ESTs) have recently been added to the NCBI databases. We matched the transcript-sequences of RefSeq, Ensembl and dbEST in an attempt to provide an updated overview of how many unique human genes can be found. The results indicate that there are about 25000 unique genes in the union of RefSeq and Ensembl with 12-18% and 8-13% of the genes in each set unique to the other set, respectively. About 20% of all genes had splice variants. There are a considerable number of ESTs (2200000) that do not match the identified genes and we used an in-house pipeline to identify 22 novel genes from Genscan predictions that have considerable EST coverage. The study provides an insight into the current status of human gene catalogues and shows that considerable refinement of methods and datasets is needed to come to a conclusive gene count.