GASP: Gapped Ancestral Sequence Prediction for proteins

Abstract

Background: The prediction of ancestral protein sequences from multiple sequence alignments is useful for many bioinformatics analyses. Predicting ancestral sequences is not a simple procedure and relies on accurate alignments and phylogenies. Several algorithms exist based on Maximum Parsimony or Maximum Likelihood methods but many current implementations are unable to process residues with gaps, which may represent insertion/deletion (indel) events or sequence fragments.

Results: Here we present a new algorithm, GASP (Gapped Ancestral Sequence Prediction), for predicting ancestral sequences from phylogenetic trees and the corresponding multiple sequence alignments. Alignments may be of any size and contain gaps. GASP first assigns the positions of gaps in the phylogeny before using a likelihood-based approach centred on amino acid substitution matrices to assign ancestral amino acids. Important outgroup information is used by first working down from the tips of the tree to the root, using descendant data only to assign probabilities, and then working back up from the root to the tips using descendant and outgroup data to make predictions. GASP was tested on a number of simulated datasets based on real phylogenies. Prediction accuracy for ungapped data was similar to three alternative algorithms tested, with GASP performing better in some cases and worse in others. Adding simple insertions and deletions to the simulated data did not have a detrimental effect on GASP accuracy.

Conclusions: GASP (Gapped Ancestral Sequence Prediction) will predict ancestral sequences from multiple protein alignments of any size. Although not as accurate in all cases as some of the more sophisticated maximum likelihood approaches, it can process a wide range of input phylogenies and will predict ancestral sequences for gapped and ungapped residues alike.

Figure 1

Sample output from GASP. (a) The first 100 columns of a typical GASP ancestral sequence prediction output. Sequence order matches the default vertical ordering in the tree files produced by GASP. (b) A rooted version of the input tree. Lengths of branches are those defined in the input file. (c) A new version of the input tree with nodes labelled and branch lengths recalculated based on ancestral sequence prediction. Note. Data is output in (a) fasta format and (b & c) Newick format but for visual clarity the file has been shown using (a) BioEdit [14] and (b & c) TreeExporer [12].

Figure 2

Mean accuracies of methods using the 'PAM Variable Rates' Model. Error Bars are Standard Errors. Percentage Accuracies are calculated for variable sites only (see text for details). The Percentage Accuracy for all sites is higher in all cases (Data not shown). The 'PAM Equal Rates' and 'Random Equal Rates' Models gave very similar results (Data Not Shown). Data shown includes only those phylogenies that did not crash CODEML (see text).

Figure 3

Difference in prediction accuracies between GASP and three alternative algorithms. (a) Yang et al. 1995 ML [6], (b) Pupko et al. 2000 [7] and (c) PAMP [9]. Percentage Accuracies are calculated for variable sites only and only those phylogenies that did not crash CODEML are shown (see text for details). Positive values indicate GASP is better than the other algorithm and negative values the reverse. Results for each tree depth are calculated separately. Values shown are for 'PAM Variable Rates' simulations only but the other evolutionary models give very similar results (Data not shown).

Figure 4

Difference in GASP prediction accuracies of methods using gapped and ungapped 'PAM Equal Rates' simulations. Percentage Accuracies are calculated for variable sites only (see text for details). Positive figures indicate that accuracies for the gapped dataset are higher than for the corresponding ungapped dataset. Results for each tree depth are calculated separately.