Bioinformatics Preprint 03-030

**Download:**

[PostScript]
[PDF]

**Titel:**

**
The Partition Function Variant of Sankoff's Algorithm
**

**Author(s):**

Ivo L. Hofacker,
Peter F. Stadler

**Submitted to:**

*ICCS 2004*

**Abstract:**

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

**Alternative Numbers:**

Return to 2003 working papers list.

Last modified: 2003-12-23 23:02:36 studla