Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00453-006-1207-0
DC FieldValue
dc.titleA faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment
dc.contributor.authorJansson, J.
dc.contributor.authorNg, S.-K.
dc.contributor.authorSung, W.-K.
dc.contributor.authorWilly, H.
dc.date.accessioned2013-07-04T07:41:57Z
dc.date.available2013-07-04T07:41:57Z
dc.date.issued2006
dc.identifier.citationJansson, J., Ng, S.-K., Sung, W.-K., Willy, H. (2006). A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment. Algorithmica (New York) 46 (2) : 223-245. ScholarBank@NUS Repository. https://doi.org/10.1007/s00453-006-1207-0
dc.identifier.issn01784617
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/39453
dc.description.abstractThe nested arc-annotation of a sequence is an important model used to represent structural information for RNA and protein sequences. Given two sequences S1 and S2 and a nested arc-annotation P 1 for S1, this paper considers the problem of inferring the nested arc-annotation P2 for S2 such that (S 1, P1) and (S2, P2) have the largest common substructure. The problem has a direct application in predicting the secondary structure of an RNA sequence given a closely related sequence with known secondary structure. The currently most efficient algorithm for this problem requires O(nm3) time and O(nm2) space where n is the length of the sequence with known arc-annotation and m is the length of the sequence whose arc-annotation is to be inferred. By using sparsification on a new recursive dynamic programming algorithm and applying a Hirschberg-like traceback technique with compression, we obtain an improved algorithm that runs in min{O(nm2 + n2m),O(nm2 log n), O(nm 3) time and min{O(m2 + mn), O(m2 log n + n)} space. © 2006 Springer Science+Business Media, Inc.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/s00453-006-1207-0
dc.sourceScopus
dc.subjectArc annotations
dc.subjectRNA secondary structure
dc.subjectSequence structure alignment
dc.subjectSparsification technique
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1007/s00453-006-1207-0
dc.description.sourcetitleAlgorithmica (New York)
dc.description.volume46
dc.description.issue2
dc.description.page223-245
dc.description.codenALGOE
dc.identifier.isiut000240361100004
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

4
checked on Nov 4, 2019

WEB OF SCIENCETM
Citations

4
checked on Nov 4, 2019

Page view(s)

102
checked on Oct 28, 2019

Google ScholarTM

Check

Altmetric


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