Hand Align Benchmark

From Biowiki
Jump to: navigation, search

HandAlign benchmark tests

Hand Align is a software package for statistical alignment. Its capabilities are discussed in this paper:

Westesson et al.: HandAlign: Bayesian multiple sequence alignment, phylogeny and ancestral reconstruction. Bioinformatics 2012;28:1170-1.

This page is a compilation of ongoing efforts to benchmark and compare statistical alignment tools. This is not meant to be a comprehensive benchmark, but rather an informal collection of data guiding the development of these tools.

The Holmes Lab has been developing the Hand Align MCMC alignment sampler intermittently since around 2000. For more info on downloading and using Hand Align is available on its own page. Currently we're running tests against BAli Phy, a similar alignment/tree/parameter sampler developed by Ben Redelings and Marc Suchard. Eventually we hope this benchmark will be expanded to include other datasets and extended to other MCMC programs.

Since the space of possible alignments and trees are very large and not easily visualized, we need to use low-dimensional summary statistics to assess mixing (e.g. how well is the sampler exploring this space). The alignment likelihood, the product of the probabilities of all the evolutionary events implied by the current alignment, is one such (1-dimensional) statistic. In general, different alignment/tree/parameter tuples will have different likelihoods, but it is inevitable that some overlaps will occur (e.g. distinct alignments having the same likelihood). This will underestimate mixing progress, since alignments which are in fact distant in "alignment space" are perceived as close in "likelihood space".

Indel parameter space is easier to visually summarize, since it is a "standard" numerical rate parameter. Summarizing substitution parameters (e.g. a rate matrix), or multiple indel parameters (gap-open, gap-extend, etc) simultaneously is more difficult, and at present our attention is focused on summarizing the single "indel rate" parameter.

Below are plots showing the likelihood and parameter traces of Hand Align and BAli Phy MCMC runs, as well as autocorrelation functions for each. 2000 samples were generated, and the first 1000 were discarded as burn-in. The x-axis is labeled with units of CPU time rather than sampling iterations, a more balanced way to compare mixing across programs (since iterations may take different lengths of time between programs).

The autocorrelation function (ACF) measures the correlation between samples of the sampling chain. The slower the 'decay', the longer it will take to generate independent samples from the posterior distribution of interest. In both likelihood and parameter traces, the BAli Phy chains appear to mix better, both by visual inspection of the trace and the autocorrelation function.

Likelihood trace and ACF

HandAlignBenchmark.likelihoods.png

Parameter trace and ACF

HandAlignBenchmark.indelRates.png

Other benchmarks

The results reported here supplement our benchmarks of earlier versions of this software, e.g.

-- Oscar Westesson - 17 Jan 2012