Algoritmos de programação dinâmica usados em modelos markovianos ocultos (HMMs) / Dynamic programming algorithms used in hidden markov models (HMMs)

AUTOR(ES)
DATA DE PUBLICAÇÃO

2004

RESUMO

Esta tese trata dos algoritmos de programação dinâmica que são usados nos Modelos Markovianos Ocultos (HMMs), perfis-HMMs, aplicados no estudo de seqüências biológicas no campo da Bioinformática. O foco é a investigação de técnicas (métodos ou paradigmas) de economia de espaço que proporcionem a melhor economia de tempo, e que sejam adequadas para a utilização no cálculo de medidas de interesse dos HMMs. Explorou-se a hipótese da utilização da estratégia de checkpoints em conjunto com o princípio D&C como solução consistente para o problema de complexidade de espaço versus complexidade de tempo dos algoritmos de programação dinâmica utilizados no cálculo de medidas de interesse em perfis-HMMs. Propõe-se um algoritmo denominado algoritmo de programação dinâmica com L-níveis de checkpoints bidimensionais que pode ser usado em conjunto com procedimentos de retrocedimento parcial ou completo, sobre a matriz de programação dinâmica. A versão com retrocedimento parcial desse algoritmo proposto, denominada algoritmo de Viterbi com L-níveis de checkpoints bidimensionais, com partição fixa de memória e retrocedimento restrito, foi superior em desempenho, tanto na análise teórica, quanto nos testes de desempenho a posteriori, ao algoritmo de Viterbi com L-níveis de checkpoints por diagonais, com partição móvel de memória e retrocedimento restrito, considerado o estado da arte entre esses algoritmos de programação dinâmica com a técnica de checkpoints. O desempenho desse algoritmo proposto foi superior, nos testes a posteriori, inclusive ao próprio algoritmo de Viterbi básico. Na simulação dos requerimentos de memória, verificou-se que os requerimentos de memória desse algoritmo proposto são uma fração decrescente dos requerimentos de memória do algorimo de Viterbi básico, para instâncias crescentes do problema, indicando um comportamento assintótico dos requerimentos de memória muito favorável para a computação de instâncias do problema que são intratáveis pelo algoritmo de Viterbi básico.

ASSUNTO(S)

processos estocásticos modelos markovianos programação dinâmica modelos markovianos ocultos (hmms) biologia computação computer science stochastic processes markovian models dynamic programming hiden markov models (hmms) computation biology

ACESSO AO ARTIGO

Documentos Relacionados