Stem-loop Structure Search

Auteurs

  • Simone Scalabrin
  • Alberto Policriti
  • Michele Morgante

DOI :

https://doi.org/10.1685/

Résumé

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 (S2_ScalabrinPolicriti0.png) preprocessing. We propose an algorithm which exploits matching statistics, is linear on the size of the input S2_ScalabrinPolicriti1.png, does not use S2_ScalabrinPolicriti0.png, builds the suffix tree only for S2_ScalabrinPolicriti1.png and saves a lot of memory. [DOI: 10.1685/CSC06137] About DOI

Téléchargements

Publiée

2007-10-01

Numéro

Vol. 1 (2006)

Rubrique

Articles

Licence

Authors who submit to this journal agree to the following terms: a) Authors retain copyright over their work, while allowing the SIMAI to place this accepted work under a Creative Commons Attribution License (CC license), which allows others to freely access, use, and share the work, with an acknowledgement of the work's authorship. b) Authors are able to waive the terms of the CC license and enter into separate, additional contractual arrangements for the non-exclusive distribution and subsequent publication of this work (e.g., publish a revised version in a journal, post it to an institutional repository or publish it in a book). with an acknowledgement of its initial publication on “Communications to SIMAI Congress”. c) In addition, authors are encouraged to post and share their work online (e.g., in institutional repositories or on their website).