Local gapped subforest alignment and its application in finding RNA structural motifs

Jesper Andreas Jansson, Ngo Trung Hieu, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

5 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationAlgorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004. Proceedings
EditorsRudolf Fleischer, Gerhard Trippen
Pages569-580
Number of pages12
Publication statusPublished - 1 Dec 2004
Externally publishedYes
Event15th International Symposium on Algorithms and Computation, ISAAC 2004 - Hong Kong, China
Duration: 20 Dec 200422 Dec 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Verlag
ISSN (Print)0302-9743
Name
VolumeLNCS 3341

Conference

Conference15th International Symposium on Algorithms and Computation, ISAAC 2004
CountryChina
CityHong Kong
Period20/12/0422/12/04

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this