USO DE PROGRAMAÇÃO DINÂMICA EM DOBRAMENTO DE RNA

Autores

  • Luiz Carlos da Silva Rozante

DOI:

https://doi.org/10.13037/ria.vol1n1.909

Palavras-chave:

Dobramento de RNA, Estrutura Secundária, Programação Dinâmica, Minimização de Energia Livre

Resumo

Os métodos laboratoriais para determinação da estrutura do RNA são onerosos. A estrutura secundária do RNA, além de fonecer 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. Situado no contexto da genômica estrutural e da bioinformática, este 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.

Downloads

Referências

PERITZ, A. E.; KIERZEK, R.; SUGIMOTO, N.; TURNER, D. Thermodynamic study of internal loops in oligonucleotides: symmetric loops are more stable than asymmetric loops. Biochemistry, (30):6428–6436, 1991.

PAPANICOLAOU, C.; GOUY, M.; NINIO, J. An energy model that predicts the correct folding of both the tRNAs and the 5S RNA molecules. Nucleic Acids Res., (21):31–44, 1984.

KNUTH, D. E.; LEVY, S. The CWEB System of Structured Documentation. Reading, Massachusetts: Addison-Wesley, 1993.

EPPSTEIN, D.; GALLI, Z.; GIANCARLO, R. Speeding up dynamic programming. In 28th Symposium on the Foundations of Computer Science, pages 488–495, 1988.

SANKOFF, D. Simultaneous solution of the mRNA folding, alignment and protosequense problems. SIAM J. Appl. Math., (5):1–35, 1985.

RIVAS, E.; EDDY, S. A dynamic programming algorithm for RNA structure prediction including pseudoknots. Journal of Molecular Biology, (285):2053–2068, 1999.

SETUBAL, J. C.; MEIDANIS, J. Introduction to Computational Molecular Biology. ICUNICAMP/PWS, 1997.

LAMORE, L.; SCHIEBER, B. On-line dynamic programming with applications to the prediction of RNA secondary structure. In First ACM-SIAM Symposium on Discrete Algorithms, pages 503–512, 1990.

KLAWE, M. M.; KLEITMAN, D. J. An almost linear time algorithm for generalizedmatrix searching. In Technical Report RJ 6275, IBM - Research Division, Almaden Research Center, 1988.

ZUKER, M.; TURNER, C. D. H. Algorithms and thermodynamics for RNA secondary structure prediction: A practical guide. (333):333–344, 1999.

ZUKER, M. On finding all suboptimal foldings of an RNA molecule. Science, (244):48–52, 1989.

ZUKER, M.; SANKOFF, D. RNA secondary structures and their prediction. Bull. Math. Biol., (46):591–621, 1984.

WATERMAN, M. S.; SMITH, T. F. Rapid dynamic programming algorithms for RNA secondary structure. Advances in Applied Mathematics, (7):455–464, 1986.

LYNGS, R. B.; PEDERSEN, C. N. S. Pseudoknots in RNA secondary structure. In Proc. 4rd Int. Conf. Computational Molecular Biology (RECOMB’00). ACM, Apr 2000.

NUSSINOV, R.; PIECZENIK, G.; GRIGGS, J. R.; KLEITMAN, D. J. Algorithms for loop matchings. SIAM J. Appl. Math., (35):68–82, 1978.

LYNGS, R. B.; ZUKER, M.; PEDERSEN, C. N. S. Internal loops in RNA secondary structure prediction. In PROC. 3rd Int. Conf. Computational Molecular Biology (RECOMB’99). ACM, Apr 1999.

WUCHTY, S.; FONTANA, W.; HOFACKEER, I. L.; SCHUSTER, P. Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers, (49):145–165, 1999.

Downloads

Publicado

2010-08-03

Como Citar

Rozante, L. C. da S. (2010). USO DE PROGRAMAÇÃO DINÂMICA EM DOBRAMENTO DE RNA. Revista De Informática Aplicada, 1(1). https://doi.org/10.13037/ria.vol1n1.909

Edição

Seção

Artigos Originais

Artigos mais lidos pelo mesmo(s) autor(es)