Please use this identifier to cite or link to this item:
Title: Local gapped subforest alignment and its application in finding RNA structural motifs
Authors: Jansson, J. 
Hieu, N.T.
Sung, W.-K. 
Keywords: Dynamic programming
Gapped subforest
Local forest alignment
Local sequence-structure motif
RNA secondary structure
Issue Date: 2006
Citation: Jansson, J., Hieu, N.T., Sung, W.-K. (2006). Local gapped subforest alignment and its application in finding RNA structural motifs. Journal of Computational Biology 13 (3) : 702-718. ScholarBank@NUS Repository.
Abstract: RNA molecules whose secondary structures contain similar substructures often have similar functions. Therefore, an important task in the study of RNA is to develop methods for discovering substructures in RNA secondary structures that occur frequently (also referred to as motifs). In this paper, we consider the problem of computing an optimal local alignment of two given labeled ordered forests F1 and F2. This problem asks for a substructure of F1 and a substructure of F2 that exhibit a high similarity. Since an RNA molecule's secondary structure can be represented as a labeled ordered forest, the problem we study has a direct application to finding potential motifs. We generalize the previously studied concept of a closed subforest to a gapped subforest and present the first algorithm for computing the optimal local gapped subforest alignment of F1 and F2. We also show that our technique can improve the time and space complexity of the previously most efficient algorithm for optimal local closed subforest alignment. 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) and modify our main algorithm to obtain a much faster algorithm for lssa than the one previously proposed. An implementation of our algorithm is available at Its running time is significantly faster than the original lssa program. © Mary Ann Liebert, Inc.
Source Title: Journal of Computational Biology
ISSN: 10665277
DOI: 10.1089/cmb.2006.13.702
Appears in Collections:Staff Publications

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

Google ScholarTM



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