Please use this identifier to cite or link to this item: https://doi.org/10.1089/cmb.2006.13.702
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
Source: 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. https://doi.org/10.1089/cmb.2006.13.702
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 www.comp.nus.edu.sg/~bioinfo/LGSFAligner/. Its running time is significantly faster than the original lssa program. © Mary Ann Liebert, Inc.
Source Title: Journal of Computational Biology
URI: http://scholarbank.nus.edu.sg/handle/10635/40391
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.

SCOPUSTM   
Citations

7
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

6
checked on Nov 18, 2017

Page view(s)

52
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


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