Please use this identifier to cite or link to this item:
https://doi.org/10.1007/s00453-006-1207-0
DC Field | Value | |
---|---|---|
dc.title | A faster and more space-efficient algorithm for inferring arc-annotations of RNA sequences through alignment | |
dc.contributor.author | Jansson, J. | |
dc.contributor.author | Ng, S.-K. | |
dc.contributor.author | Sung, W.-K. | |
dc.contributor.author | Willy, H. | |
dc.date.accessioned | 2013-07-04T07:41:57Z | |
dc.date.available | 2013-07-04T07:41:57Z | |
dc.date.issued | 2006 | |
dc.identifier.citation | Jansson, 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.issn | 01784617 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/39453 | |
dc.description.abstract | The 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.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1007/s00453-006-1207-0 | |
dc.source | Scopus | |
dc.subject | Arc annotations | |
dc.subject | RNA secondary structure | |
dc.subject | Sequence structure alignment | |
dc.subject | Sparsification technique | |
dc.type | Article | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1007/s00453-006-1207-0 | |
dc.description.sourcetitle | Algorithmica (New York) | |
dc.description.volume | 46 | |
dc.description.issue | 2 | |
dc.description.page | 223-245 | |
dc.description.coden | ALGOE | |
dc.identifier.isiut | 000240361100004 | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.