TY - GEN
T1 - Local gapped subforest alignment and its application in finding RNA structural motifs
AU - Jansson, Jesper Andreas
AU - Hieu, Ngo Trung
AU - Sung, Wing Kin
PY - 2004/12/1
Y1 - 2004/12/1
N2 - We consider the problem of computing an optimal local alignment of two labeled ordered forests F1and F2where niand di, for i ∈{1, 2}, denote the number of nodes in Fi and the degree of Fi, respectively; and its applications in finding RNA structural motifs. A previous result is the local closed subforest alignment problem, which can be solved in O(n1n2d1d2(d1+ d2)) time and O(n1n2d1d2) space. This paper generalizes the concept of a closed subforest to a gapped subforest and then presents an algorithm for computing the optimal local gapped subforest alignment of F1and F2in O(n1n2d1d2(d1+ d2)) time and O(n1n2d1d2) space. We show that our technique can improve the computation of the optimal local closed subforest alignment in O(n1n2(d1+ d2)2) time and O(n1n2(d1+ d2)) space. Furthermore, we prove that a special case of our local gapped subforest alignment problem is equivalent to a problem known in the literature as the local sequence-structure alignment problem (lssa). The previously best algorithm for lssa uses O(n12n22(n1+ n2)) time and O(n1n2) space; here, we show how to modify our main algorithm to obtain an algorithm for lssa running in O(n1n2(d1+ d2)2) time and O(n1n2(d1+ d2)) space.
AB - We consider the problem of computing an optimal local alignment of two labeled ordered forests F1and F2where niand di, for i ∈{1, 2}, denote the number of nodes in Fi and the degree of Fi, respectively; and its applications in finding RNA structural motifs. A previous result is the local closed subforest alignment problem, which can be solved in O(n1n2d1d2(d1+ d2)) time and O(n1n2d1d2) space. This paper generalizes the concept of a closed subforest to a gapped subforest and then presents an algorithm for computing the optimal local gapped subforest alignment of F1and F2in O(n1n2d1d2(d1+ d2)) time and O(n1n2d1d2) space. We show that our technique can improve the computation of the optimal local closed subforest alignment in O(n1n2(d1+ d2)2) time and O(n1n2(d1+ d2)) space. Furthermore, we prove that a special case of our local gapped subforest alignment problem is equivalent to a problem known in the literature as the local sequence-structure alignment problem (lssa). The previously best algorithm for lssa uses O(n12n22(n1+ n2)) time and O(n1n2) space; here, we show how to modify our main algorithm to obtain an algorithm for lssa running in O(n1n2(d1+ d2)2) time and O(n1n2(d1+ d2)) space.
UR - http://www.scopus.com/inward/record.url?scp=26444567117&partnerID=8YFLogxK
M3 - Conference article published in proceeding or book
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 569
EP - 580
BT - Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004. Proceedings
A2 - Fleischer, Rudolf
A2 - Trippen, Gerhard
T2 - 15th International Symposium on Algorithms and Computation, ISAAC 2004
Y2 - 20 December 2004 through 22 December 2004
ER -