Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/39448
Title: Local gapped subforest alignment and its application in finding RNA structural motifs
Authors: Jansson, J. 
Hieu, N.T.
Sung, W.-K. 
Issue Date: 2004
Source: Jansson, J.,Hieu, N.T.,Sung, W.-K. (2004). Local gapped subforest alignment and its application in finding RNA structural motifs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 3341 : 569-580. ScholarBank@NUS Repository.
Abstract: We consider the problem of computing an optimal local alignment of two labeled ordered forests F1 and F2 where ni and di, for i ∈{1, 2}, denote the number of nodes in Fi and the degree of Fi, respectively; and its applications in finding RNA structural motifs. A previous result is the local closed subforest alignment problem, which can be solved in O(n1n2d1d 2(d1 + d2)) time and O(n1n 2d1d2) space. This paper generalizes the concept of a closed subforest to a gapped subforest and then presents an algorithm for computing the optimal local gapped subforest alignment of F 1 and F2 in O(n1n2d 1d2(d1 + d2)) time and O(n 1n2d1d2) space. We show that our technique can improve the computation of the optimal local closed subforest alignment in O(n1n2(d1 + d2) 2) time and O(n1n2(d1 + d 2)) space. Furthermore, we prove that a special case of our local gapped subforest alignment problem is equivalent to a problem known in the literature as the local sequence-structure alignment problem (lssa). The previously best algorithm for lssa uses O(n1 2n 2 2(n1 + n2)) time and O(n 1n2) space; here, we show how to modify our main algorithm to obtain an algorithm for lssa running in O(n1n2(d 1 + d2)2) time and O(n1n 2(d1 + d2)) space. © 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/39448
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)

46
checked on Dec 8, 2017

Google ScholarTM

Check


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