A Bayesian approach to pairwise RNA Secondary Structure Alignment

In solving the question of alignment of two RNA secondary structures, it is not clear how to choose parameters for the introduction of gaps in the alignment. We introduce a Bayesian approach for aligning two RNA secondary structures. The algorithm can not only compute the optimal alignment itself but also some interesting posteriors such as posteriors of substitution matrix and gap opening penalties. The running time of this algorithm is O(p₁ p₂ nm), where p₁ and p₂ are the number of base pairs in RNA structures A and B, and n and m are the lengths of the two RNA secondary structures respectively