# Publication details

##
Dynamic Programming based RNA Pseudoknot Alignment

Mathias Möhl

Doctoral Dissertation, Saarland University, October 2009

Pseudoknots are certain structural motifs of RNA molecules. In this
thesis we consider the problem of RNA pseudoknot alignment. Most
current approaches either discard pseudoknots in order to be efficient
or rely on heuristics generating only approximate solutions. This work
focuses on dynamic programming based alignment methods and proposes
two new approaches for an exact solution of the alignment problem in
the presence of pseudoknot structures. The first approach is able to
handle arbitrary pseudoknots, however, does not guarantee a polynomial
runtime for all instances, due to the NP-hardness of the
problem. Nevertheless, an analysis in terms of parameterized
complexity shows that the algorithm is fixed parameter tractable for a
parameter that is small in practice. The second approach is a general
scheme for the alignment of restricted classes of pseudoknots in
polynomial time. It is motivated by existing RNA pseudoknot prediction
algorithms. We show how to embed seven of those algorithms in a common
scheme and present an analogous scheme for the alignment problem,
which yields for each of the structure prediction algorithms a
corresponding alignment algorithm. The alignment algorithms handle the
same class of pseudoknots as the corresponding prediction algorithms
and the time and space complexity is only increased by a linear
factor, compared to the respective prediction algorithm. Both
approaches have been implemented to evaluate their applicability in
practice.

Download PDF
Show BibTeX

@PHDTHESIS{Moehl:2009:Dynamic,
title = {Dynamic Programming based RNA Pseudoknot Alignment},
author = {Mathias M{\"o}hl},
year = {2009},
month = {Oct},
type = {Doctoral Dissertation},
address = {Saarbr{\"u}cken, Germany},
school = {Saarland University},
}

Login to edit

Legal notice, Privacy policy