Publications - Published papers

Please find below publications of our group. Currently, we list 496 papers. Some of the publications are in collaboration with the group of Sonja Prohaska and are also listed in the publication list for her individual group. Access to published papers (access) is restricted to our local network and chosen collaborators. If you have problems accessing electronic information, please let us know:

©NOTICE: All papers are copyrighted by the authors; If you would like to use all or a portion of any paper, please contact the author.

The Partition Function Variant of Sankoff's Algorithm

Ivo L. Hofacker, Peter F. Stadler


PREPRINT 03-030: [ PDF ]  [ PS ]
[ Publishers's page ]  paperID


Marian Bubak, Geert Dick van Albada, Peter M. A. Sloot, and Jack J. Dongarra (Eds.): <i>Computational Science - ICCS 2004, Part IV</i>, Lecture Notes in Computer Science LNCS 3039, Springer Verlag, Heidelberg, 2004, pp 728-735.


Many classes of functional RNA molcules are characterized by highly conserved secondary structures but little detectable sequence similarity. Reliable multiple alignments can therefore be constructed only when the shared structural features are taken into account. Sankoff's algorithm can be used to construct such structure-based alignments of RNA sequences in polynomial time. Here we extend the approach to a probabilistic one by explicitly computing the partition function of all pairwisely aligned sequences with a common set of base pairs. Stochastic backtracking can then be used to compute e.g.\ the probability that a prescribed sequence-structure pattern is conserved between two RNA sequences. The reliability of the alignment itself can be assessed in terms of the probabilities of each possible match. Keywords: Sankoff algorithm, partition function, structure-based RNA alignments