Bioinformatický seminár

Wed 30 Nov. -0001, 0:00

Title: Ziv-Ukelson et al. A faster algorithm for simultaneous alignment and folding of RNA. Journal of Computational Biology, 2010
Speaker: Jožo Vavro

The current pairwise RNA (secondary) structural alignment algorithms are
based on Sankoff's dynamic programming algorithm from 1985. Sankoff's
algorithm requires O(N(6)) time and O(N(4)) space, where N denotes the
length of the compared sequences, and thus its applicability is very
limited. The current literature offers many heuristics for speeding up
Sankoff's alignment process, some making restrictive assumptions on the
length or the shape of the RNA substructures. We show how to speed up
Sankoff's algorithm in practice via non-heuristic methods, without
compromising optimality. Our analysis shows that the expected time
complexity of the new algorithm is O(N(4)sigma(N)), where sigma(N)
converges to O(N), assuming a standard polymer folding model which was
supported by experimental analysis. Hence, our algorithm speeds up
Sankoff's algorithm by a linear factor on average. In simulations, our
algorithm speeds up computation by a factor of 3-12 for sequences of
length 25-250. Code and data sets are available, upon request.