File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A memory efficient algorithm for structural alignment of RNAs with embedded simple pseudoknots

TitleA memory efficient algorithm for structural alignment of RNAs with embedded simple pseudoknots
Authors
Issue Date2008
PublisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscibooks.com/series/abcb_series.shtml
Citation
Series On Advances In Bioinformatics And Computational Biology, 2008, v. 6, p. 89-100 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 embedded simple pseduoknots. The best known algorithm for solving this problem (Dost et al. [13]) runs in O(mn4) time with space complexity of O(mn3), which requires too much memory making it infeasible for comparing ncRNAs (non-coding RNAs) with length several hundreds or more. We propose a memory efficient algorithm to solve the same problem. We reduce the space complexity to O(mn2 + n3) while maintaining the same time complexity of Dost et al.'s algorithm. Experimental reslts show that our algorithm is feasible for comparing ncRNAs of length more than 500. Availability: The source code of our program is available upon request.
Persistent Identifierhttp://hdl.handle.net/10722/93146
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorWong, Ten_HK
dc.contributor.authorChiu, YSen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-25T14:52:17Z-
dc.date.available2010-09-25T14:52:17Z-
dc.date.issued2008en_HK
dc.identifier.citationSeries On Advances In Bioinformatics And Computational Biology, 2008, v. 6, p. 89-100en_HK
dc.identifier.issn1751-6404en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93146-
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 embedded simple pseduoknots. The best known algorithm for solving this problem (Dost et al. [13]) runs in O(mn4) time with space complexity of O(mn3), which requires too much memory making it infeasible for comparing ncRNAs (non-coding RNAs) with length several hundreds or more. We propose a memory efficient algorithm to solve the same problem. We reduce the space complexity to O(mn2 + n3) while maintaining the same time complexity of Dost et al.'s algorithm. Experimental reslts show that our algorithm is feasible for comparing ncRNAs of length more than 500. Availability: The source code of our program is available upon request.en_HK
dc.languageengen_HK
dc.publisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscibooks.com/series/abcb_series.shtmlen_HK
dc.relation.ispartofSeries on Advances in Bioinformatics and Computational Biologyen_HK
dc.titleA memory efficient algorithm for structural alignment of RNAs with embedded simple pseudoknotsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-84856818940en_HK
dc.identifier.hkuros146743en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84856818940&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6en_HK
dc.identifier.spage89en_HK
dc.identifier.epage100en_HK
dc.publisher.placeSingaporeen_HK
dc.identifier.scopusauthoridWong, T=54980738700en_HK
dc.identifier.scopusauthoridChiu, YS=54396933700en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats