Stem-loop Structure Search

Simone Scalabrin, Alberto Policriti, Michele Morgante


The base-pairing of a nucleic acid secondary structure is a sort of biological palindrome. The base pairs of nucleic acid stems nest in a palindromic fashion with complementary base pairings rather than identical letters. In addition, nucleic acid stems are usually separated by a loop, i.e. a non palindromic sequence. At the moment, the problem of finding such a structure is solved through dynamic programming or in linear time with the use of the lowest common ancestor () preprocessing.

We propose an algorithm which exploits matching statistics, is linear on the size of the input , does not use , builds the suffix tree only for and saves a lot of memory.

[DOI: 10.1685/CSC06137] About DOI

Full Text:



Creative Commons License   Except where otherwise noted, content on this site is
  licensed under a Creative Commons 2.5 Italy License