Please use this identifier to cite or link to this item:
Title: A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment
Authors: Jansson, J. 
Ng, S.-K.
Sung, W.-K. 
Willy, H. 
Keywords: Arc annotations
RNA secondary structure
Sequence structure alignment
Sparsification technique
Issue Date: 2006
Citation: Jansson, J., Ng, S.-K., Sung, W.-K., Willy, H. (2006). A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment. Algorithmica (New York) 46 (2) : 223-245. ScholarBank@NUS Repository.
Abstract: The nested arc-annotation of a sequence is an important model used to represent structural information for RNA and protein sequences. Given two sequences S1 and S2 and a nested arc-annotation P 1 for S1, this paper considers the problem of inferring the nested arc-annotation P2 for S2 such that (S 1, P1) and (S2, P2) have the largest common substructure. The problem has a direct application in predicting the secondary structure of an RNA sequence given a closely related sequence with known secondary structure. 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 and m is the length of the sequence whose arc-annotation is to be inferred. By using sparsification on a new recursive dynamic programming algorithm and applying a Hirschberg-like traceback technique with compression, we obtain an improved algorithm that runs in min{O(nm2 + n2m),O(nm2 log n), O(nm 3) time and min{O(m2 + mn), O(m2 log n + n)} space. © 2006 Springer Science+Business Media, Inc.
Source Title: Algorithmica (New York)
ISSN: 01784617
DOI: 10.1007/s00453-006-1207-0
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Sep 29, 2022


checked on Sep 21, 2022

Page view(s)

checked on Sep 22, 2022

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.