File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Memory efficient algorithms for structural alignment of RNAs with pseudoknots

TitleMemory efficient algorithms for structural alignment of RNAs with pseudoknots
Authors
KeywordsMemory Efficient Algorithm
Noncoding Rnas
Pseudoknot
Structural Alignment
Issue Date2012
Citation
IEEE/ACM Transactions On Computational Biology And Bioinformatics, 2012, v. 9 n. 1, p. 161-168 How to Cite?
AbstractIn this paper, we consider the problem of structural alignment of a target RNA sequence of length n and a query RNA sequence of length m with known secondary structure that may contain simple pseudoknots or embedded simple pseudoknots. The best known algorithm for solving this problem runs in O(mn 3) time for simple pseudoknot or O(mn4) time for embedded simple pseudoknot with space complexity of O(mn3) for both structures, which require too much memory making it infeasible for comparing noncoding RNAs (ncRNAs) with length several hundreds or more. We propose memory efficient algorithms to solve the same problem. We reduce the space complexity to O(n3) for simple pseudoknot and O(mn2 + n3) for embedded simple pseudoknot while maintaining the same time complexity. We also show how to modify our algorithm to handle a restricted class of recursive simple pseudoknot which is found abundant in real data with space complexity of O(mn2 + n3) and time complexity of O(mn4). Experimental results show that our algorithms are feasible for comparing ncRNAs of length more than 500. © 2012 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/152478
ISSN
2015 Impact Factor: 1.609
2015 SCImago Journal Rankings: 0.706
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorWong, TKFen_US
dc.contributor.authorChiu, YSen_US
dc.contributor.authorLam, TWen_US
dc.contributor.authorYiu, SMen_US
dc.date.accessioned2012-06-26T06:39:30Z-
dc.date.available2012-06-26T06:39:30Z-
dc.date.issued2012en_US
dc.identifier.citationIEEE/ACM Transactions On Computational Biology And Bioinformatics, 2012, v. 9 n. 1, p. 161-168en_US
dc.identifier.issn1545-5963en_US
dc.identifier.urihttp://hdl.handle.net/10722/152478-
dc.description.abstractIn this paper, we consider the problem of structural alignment of a target RNA sequence of length n and a query RNA sequence of length m with known secondary structure that may contain simple pseudoknots or embedded simple pseudoknots. The best known algorithm for solving this problem runs in O(mn 3) time for simple pseudoknot or O(mn4) time for embedded simple pseudoknot with space complexity of O(mn3) for both structures, which require too much memory making it infeasible for comparing noncoding RNAs (ncRNAs) with length several hundreds or more. We propose memory efficient algorithms to solve the same problem. We reduce the space complexity to O(n3) for simple pseudoknot and O(mn2 + n3) for embedded simple pseudoknot while maintaining the same time complexity. We also show how to modify our algorithm to handle a restricted class of recursive simple pseudoknot which is found abundant in real data with space complexity of O(mn2 + n3) and time complexity of O(mn4). Experimental results show that our algorithms are feasible for comparing ncRNAs of length more than 500. © 2012 IEEE.en_US
dc.languageengen_US
dc.relation.ispartofIEEE/ACM Transactions on Computational Biology and Bioinformaticsen_US
dc.subjectMemory Efficient Algorithmen_US
dc.subjectNoncoding Rnasen_US
dc.subjectPseudoknoten_US
dc.subjectStructural Alignmenten_US
dc.titleMemory efficient algorithms for structural alignment of RNAs with pseudoknotsen_US
dc.typeArticleen_US
dc.identifier.emailLam, TW:twlam@cs.hku.hken_US
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_US
dc.identifier.authorityLam, TW=rp00135en_US
dc.identifier.authorityYiu, SM=rp00207en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/TCBB.2011.66en_US
dc.identifier.pmid21464506-
dc.identifier.scopuseid_2-s2.0-81455142798en_US
dc.identifier.hkuros208100-
dc.identifier.hkuros192232-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-81455142798&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume9en_US
dc.identifier.issue1en_US
dc.identifier.spage161en_US
dc.identifier.epage168en_US
dc.identifier.isiWOS:000296782200014-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridWong, TKF=25423289800en_US
dc.identifier.scopusauthoridChiu, YS=54396933700en_US
dc.identifier.scopusauthoridLam, TW=7202523165en_US
dc.identifier.scopusauthoridYiu, SM=7003282240en_US
dc.identifier.citeulike9111347-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats