Bioinformatický seminár

Tue 5 Mar. 2013, 17:20

Title: Rinaudo et al. (2012) Tree Decomposition and Parameterized Algorithms for RNA Structure-Sequence Alignment Including Tertiary Interactions and Pseudoknots
Speaker: Martin Králik

We present a general setting for structure-sequence comparison
in a large class of RNA structures, that unifies and generalizes
a number of recent works on specific families of structures.
Our approach is based on a tree decomposition of structures,
and gives rise to a general parameterized algorithm having
complexity in $\mathcal{O}(N\cdot m^t)$ , where N (resp. m)
is the structure (resp. sequence) length, and the exponent t
depends on the family of structures. For each family considered
by previous approaches, our contribution specializes into
an algorithm whose complexity either matches
or outperforms previous solutions.