Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00453-006-1207-0
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
Source: 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. https://doi.org/10.1007/s00453-006-1207-0
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)
URI: http://scholarbank.nus.edu.sg/handle/10635/39453
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.

SCOPUSTM   
Citations

4
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

4
checked on Nov 1, 2017

Page view(s)

58
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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