@inproceedings{0a56ed9af00b4fbf93ecfdfa7b37d53b,
title = "A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment",
abstract = "This paper considers the problem of inferring the optimal nested arc-annotation of a sequence given another nested arc-annotated sequence by maximizing the weighted alignment between the bases and arcs in the two sequences. The problem has a direct application in predicting the secondary structure of an RNA sequence given a closely related sequence whose secondary structure is already known. The currently most efficient algorithm for this problem requires O(nm3) time and O(nm2) space where n is the length of the sequence with known arc-annotation while m is the length of the sequence to be inferred. We present an improved algorithm which runs in min{O(nm2log n), O(nm3)} time and min{O(m2+mn), O(m2log n)} space. The time improvement is achieved by applying sparsification to the dynamic programming algorithm, while the space is reduced to a more practical quadratic complexity by using a Hirschberg-like traceback technique together with a simple compression.",
author = "Jansson, {Jesper Andreas} and Ng, {See Kiong} and Sung, {Wing Kin} and Hugo Willy",
year = "2004",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "302--313",
editor = "{Jonassen }, {Inge } and Junhyong Kim",
booktitle = "Algorithms in Bioinformatics: 4th International Workshop, WABI 2004, Proceedings",
note = "4th International Workshop on Algorithms in Bioinformatics, WABI 2004 ; Conference date: 17-09-2004 Through 21-09-2004",
}