Home
  >  
Section 58
  >  
Chapter 57,028

A Dynamic Programming Algorithm for Finding the Optimal Segmentation of an RNA Sequence in Secondary Structure Predictions

Licon, A.; Taufer, M.; Leung, M-Ying.; Johnson, K.L.

2nd International Conference on Bioinformatics and Computational Biology 2010 Honolulu Hawaii Usa 24-26 March 2010. International Conference on Bioinformatics and Computational Biology 2010: 165-170

2010


PMID: 25705724
Accession: 057027614

In this paper, we present a dynamic programming algorithm that runs in polynomial time and allows us to achieve the optimal, non-overlapping segmentation of a long RNA sequence into segments (chunks). The secondary structure of each chunk is predicted independently, then combined with the structures predicted for the other chunks, to generate a complete secondary structure prediction that is thus a combination of local energy minima. The proposed approach not only is more efficient and accurate than other traditionally used methods that are based on global energy minimizations, but it also allows scientists to overcome computing and storage constraints when trying to predict the secondary structure of long RNA sequences.

PDF emailed within 1 workday: $29.90