Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39364
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. 
Issue Date: 2004
Source: Jansson, J.,Ng, S.-K.,Sung, W.-K.,Willy, H. (2004). A faster and more space-efficient algorithm for inferring Arc-annotations of RNA sequences through alignment. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3240 : 302-313. ScholarBank@NUS Repository.
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(nm2 log n), O(nm3)} time and min{O(m2 +mn), O(m2 log 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. © Springer-Verlag 2004.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/39364
ISSN: 03029743
Appears in Collections:Staff Publications

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

Page view(s)

59
checked on Jan 14, 2018

Google ScholarTM

Check


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