Pattern-based phylogenetic distance estimation and tree reconstruction

Abstract

We have developed an alignment-free method that calculates phylogenetic distances using a maximum-likelihood approach for a model of sequence change on patterns that are discovered in unaligned sequences. To evaluate the phylogenetic accuracy of our method, and to conduct a comprehensive comparison of existing alignment-free methods (freely available as Python package decaf + py at http://www.bioinformatics.org.au), we have created a data set of reference trees covering a wide range of phylogenetic distances. Amino acid sequences were evolved along the trees and input to the tested methods; from their calculated distances we infered trees whose topologies we compared to the reference trees.We find our pattern-based method statistically superior to all other tested alignment-free methods. We also demonstrate the general advantage of alignment-free methods over an approach based on automated alignments when sequences violate the assumption of collinearity. Similarly, we compare methods on empirical data from an existing alignment benchmark set that we used to derive reference distances and trees. Our pattern-based approach yields distances that show a linear relationship to reference distances over a substantially longer range than other alignment-free methods. The pattern-based approach outperforms alignment-free methods and its phylogenetic accuracy is statistically indistinguishable from alignment-based distances.

Keywords: alignment-free methods; distance estimation; pattern discovery; phylogenetics.

Figure 1

Average Robinson-Foulds distance (Y-axis) for two methods (a,c,e: d^E; b,d,f: d^C) on three reference sets (top to bottom: small, medium and large phylogenetic distances). Each subfigure shows the behaviour as a function of word length k (X-axis) under two alphabets (AA: original amino acids, CE: chemical equivalence classes). Points are joined for ease of visual inspection only. The expectation of a tree reconstruction method based on random choice is $\frac{2}{3}$, or about 0.67.

Figure 2

Pairwise phylogenetic reference distances (X-axis) plotted against corresponding calculated distances (Y-axis). Methods and parameters are as follows: a) d^PB with L = 4, W = 16, CE, b) d^PB with L = 4, W = 16, AA, c) d^PBMC with L = 4, W = 16, CE, d) d^E with k = 4, AA, e) d^S with k = 4, AA, f) d^F with k = 4, AA, g) d^P with k = 4, AA, h) d^C with k = 3, AA, i) d^C with k = 5, CE, j) d^W, k) d^LZ with AA, l) d^ACS with A A.

Figure 2

Pairwise phylogenetic reference distances (X-axis) plotted against corresponding calculated distances (Y-axis). Methods and parameters are as follows: a) d^PB with L = 4, W = 16, CE, b) d^PB with L = 4, W = 16, AA, c) d^PBMC with L = 4, W = 16, CE, d) d^E with k = 4, AA, e) d^S with k = 4, AA, f) d^F with k = 4, AA, g) d^P with k = 4, AA, h) d^C with k = 3, AA, i) d^C with k = 5, CE, j) d^W, k) d^LZ with AA, l) d^ACS with A A.

Figure 3

Average Robinson-Foulds distance (Y-axis) for two methods (a,c,e: d^S; b,d,f: d^F) on three reference sets (top to bottom: small, medium and large phylogenetic distances). Each subfigure shows the behaviour as a function of word length k (X-axis) under two alphabets (AA: original amino acids, CE: chemical equivalence classes). Points are joined for ease of visual inspection only. The expectation of a tree reconstruction method based on random choice is $\frac{2}{3}$, or about 0.67.

Figure 4

Average Robinson-Foulds distance (Y-axis) for method d^P on three reference sets (top to bottom: small, medium and large phylogenetic distances). Each subfigure shows the behaviour as a function of word length k (X-axis) under two alphabets (AA: original amino acids, CE: chemical equivalence classes). Points are joined for ease of visual inspection only. The expectation of a tree reconstruction method based on random choice is $\frac{2}{3}$, or about 0.67.