Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-00727-9_10
Title: The 2-interval pattern matching problems and its application to ncRNA scanning
Authors: Wong, T.K.F.
YiuT, S.M.
Lam, W.
Sung, W.-K. 
Issue Date: 2009
Source: Wong, T.K.F.,YiuT, S.M.,Lam, W.,Sung, W.-K. (2009). The 2-interval pattern matching problems and its application to ncRNA scanning. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 5462 LNBI : 79-89. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-00727-9_10
Abstract: This paper focuses on the 2-Interval pattern matching problem for{<, ⊂}-structured pattern and applies it on scanning for the ncRNAs without pseudoknots. Vialette [6] gave an O(mn 3 log n) time solution to the problem, where ,n are the number of intervals in the pattern and the given 2-interval set.This solution however is not practical for scanning the secondary structure in a genome- wide or chromosome-wide scale. In this paper, we propose an efficient algorithm to solve the problem in O(mn log n) time. In order to capture morecharacteristics of the secondary structures of ncRNA families, we define a new problem by considering the distance constraints between the intervals and we can still solve it without increasing the time complexity. Experiment showed that the method to the new defined problem can result in much fewer false positives. Moreover, if we assume the only possible base pairs are {(A,U),(C,G),U,G)} which are the case for RNA molecule, we can further improve the ime complexity to O(mq), where q is the length of the input RNA sequences. From the experiment, our new method requires a reasonable time (2.5 min) to scan the whole chromosome for an ncRNA family. © Springer-Verlag Berlin Heidelberg 2009.
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/40084
ISBN: 3642007260
ISSN: 03029743
DOI: 10.1007/978-3-642-00727-9_10
Appears in Collections:Staff Publications

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

Page view(s)

45
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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