Stem-loop Structure Search

Abstract

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