The Performance of a Reversible Jump Markov Chain Monte Carlo Algorithm for DNA Sequences Alignment

Assume that K independent copies are made from a common prototype DNA sequence whose length is considered to be a random variable. In this paper the problem of aligning these copies and therefore the problem of estimating the prototype sequence that produced the copies is addressed. A hidden Markov chain is used to model the copying procedure and a reversible jump Markov chain Monte Carlo algorithm is used to sample the parameters of the model from their posterior distribution. Using the sample obtained, the Bayesian model selection may be made and the prototype sequence may be selected using the maximum a posteriori estimate. A prior distribution for the prototype DNA sequence that incorporates a correlation among neighbouring bases is also considered. Additionally, an analysis of the performance of the algorithm is presented when different scenarios are taken into account.