USO DE PROGRAMAÇÃO DINÂMICA EM DOBRAMENTO DE RNA
DOI:
https://doi.org/10.13037/ria.vol1n1.909Palabras clave:
Dobramento de RNA, Estrutura Secundária, Programação Dinâmica, Minimização de Energia LivreResumen
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.Descargas
Referencias
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.
Descargas
Publicado
Número
Sección
Licencia
Derechos de autor 2010 Luiz Carlos da Silva Rozante
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Os autores que publicam trabalhos na RIA estão de acordo com os seguintes termos:
- Autores mantêm seus direitos autorais e concedem à RIA o direito à primeira publicação. Admite-se o compartilhamento do referido trabalho, desde que seja reconhecida sua autoria e publicação inicial nesta revista.
- Autores podem fechar contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicado na RIA, com reconhecimento de sua autoria e publicação inicial nesta revista.
- Autores podem publicar e distribuir seu trabalho online, antes ou durante o processo editorial.
