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
) 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:
Except where otherwise noted, content on this site is licensed under a Creative Commons 2.5 Italy License