Please use this identifier to cite or link to this item:
https://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 | Citation: | 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.
Google ScholarTM
Check
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.