A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment

Jesper Andreas Jansson, See Kiong Ng, Wing Kin Sung, Hugo Willy

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)


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.
Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics: 4th International Workshop, WABI 2004, Proceedings
EditorsInge Jonassen , Junhyong Kim
Number of pages12
Publication statusPublished - 2004
Externally publishedYes
Event4th International Workshop on Algorithms in Bioinformatics, WABI 2004 - Bergen, Norway
Duration: 17 Sep 200421 Sep 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
VolumeLNBI 3240
ISSN (Print)0302-9743


Conference4th International Workshop on Algorithms in Bioinformatics, WABI 2004

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this