Similarly to the proteins, the RNA molecules assume a three-dimensional conformation (structure) that has an important role in determining their function. These molecules can develop catalytic activities or be a structural or a regulator element. The experimental methods for deducing RNA structures are costly. The RNA secondary structure gives information about the function of the molecule and serves as an important step in determining its tertiary structure. So, it is important develop fast and accurate computer methods on prediction of secondary structure from primary structure. The two most significant strategies for solving the problem are based on thermodynamic stability criteria (of minimum free-energy) and in the search of the common foldings among homologous molecules. In the first case, the most important algorithms are based on techniques of dynamic programming. In the second, the most important algorithms known are based on models of covariance and perform on a set of aligned sequences. Being situated on genomics and biocomputing areas, this work presents the models proposed for the problem and describes formally the several existing techniques and methods involved in the solution of this problem. We also developed efficient implementations of the most expressive algorithms based on free energy minimization.

De forma similar á que ocorre com as proteínas, as moléculas de RNA assumem uma conformação espacial (estrutura) que desempenha um importante papel na definição de sua função. Além de influenciar os processos de transcrição, tradução e replicação, as moléculas de RNA podem desenvolver atividades catalíticas. Podem ainda desempenhar papel regulador ou estrutural. Os métodos laboratoriais para determinação da estrutura do RNA são onerosos. A estrutura secundária do RNA, além de fornecer informações acerca da função da molécula, serve também como importante etapa na definição de sua estrutura terciária. Daí a importância em se desenvolver métodos computacionais, rápidos e precisos, de predição da estrutura secundária a partir da estrutura primária. As duas mais importantes estratégias de resolução do problema estão baseadas em critérios de estabilidade termodinâmica (de energia livre mínima) e na identificação dos dobramentos comuns entre moléculas homólogas. No primeiro caso, os algoritmos mais importantes são baseados em técnicas de programação dinâmica. No segundo, os mais importantes algoritmos conhecidos são baseados em modelos de covariância e operam sobre um conjunto de sequências homólogas alinhadas. Situado no contexto da genômica estrutural e da bioinformática, o trabalho apresenta os modelos propostos para o problema, além de descrever formalmente as várias técnicas e métodos envolvidos na sua resolução. Desenvolvemos também implementações eficientes dos algoritmos mais expressivos baseados em cálculo de energia livre mínima, tanto do ponto de vista da complexidade computacional (de tempo e espaço), como da representatividade do modelo termodinâmico.