File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: A memory efficient algorithm for structural alignment of RNAs with embedded simple pseudoknots
Title | A memory efficient algorithm for structural alignment of RNAs with embedded simple pseudoknots |
---|---|
Authors | |
Issue Date | 2008 |
Publisher | World 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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/93146 |
ISSN | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Wong, T | en_HK |
dc.contributor.author | Chiu, YS | en_HK |
dc.contributor.author | Lam, TW | en_HK |
dc.contributor.author | Yiu, SM | en_HK |
dc.date.accessioned | 2010-09-25T14:52:17Z | - |
dc.date.available | 2010-09-25T14:52:17Z | - |
dc.date.issued | 2008 | en_HK |
dc.identifier.citation | Series On Advances In Bioinformatics And Computational Biology, 2008, v. 6, p. 89-100 | en_HK |
dc.identifier.issn | 1751-6404 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/93146 | - |
dc.description.abstract | In 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.language | eng | en_HK |
dc.publisher | World Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscibooks.com/series/abcb_series.shtml | en_HK |
dc.relation.ispartof | Series on Advances in Bioinformatics and Computational Biology | en_HK |
dc.title | A memory efficient algorithm for structural alignment of RNAs with embedded simple pseudoknots | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Lam, TW:twlam@cs.hku.hk | en_HK |
dc.identifier.email | Yiu, SM:smyiu@cs.hku.hk | en_HK |
dc.identifier.authority | Lam, TW=rp00135 | en_HK |
dc.identifier.authority | Yiu, SM=rp00207 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.scopus | eid_2-s2.0-84856818940 | en_HK |
dc.identifier.hkuros | 146743 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-84856818940&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 6 | en_HK |
dc.identifier.spage | 89 | en_HK |
dc.identifier.epage | 100 | en_HK |
dc.publisher.place | Singapore | en_HK |
dc.identifier.scopusauthorid | Wong, T=54980738700 | en_HK |
dc.identifier.scopusauthorid | Chiu, YS=54396933700 | en_HK |
dc.identifier.scopusauthorid | Lam, TW=7202523165 | en_HK |
dc.identifier.scopusauthorid | Yiu, SM=7003282240 | en_HK |
dc.identifier.issnl | 1751-6404 | - |