@inproceedings{cf5035e0ed0d473792f53b059502e96e,
title = "A memory efficient algorithm for structural alignment of RNAs with embedded simple pseudoknots",
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.",
author = "Thomas Wong and Chiu, {Y. S.} and Lam, {T. W.} and Yiu, {S. M.}",
year = "2008",
language = "English",
isbn = "9781848161085",
series = "Series on Advances in Bioinformatics and Computational Biology",
pages = "89--100",
booktitle = "Proceedings of 6th Asia-Pacific Bioinformatics Conference, APBC 2008",
note = "6th Asia-Pacific Bioinformatics Conference, APBC 2008 ; Conference date: 14-01-2008 Through 17-01-2008",
}