Alai

3 MODELOS DE ESTADO

Se os escores usados são probabilidades de log ou probabilidades de log, então um autômato de estado finito é essencialmente um modelo Markov oculto (HMM), e estes foram introduzidos recentemente na descoberta do gene por vários grupos. A única diferença fundamental dos esquemas de programação dinâmica discutidos acima é que esses modelos são totalmente probabilísticos, o que tem certas vantagens. Uma das vantagens é que o problema de ponderação é mais fácil.

VEIL (Henderson et al., 1997) é uma aplicação de um HMM ao problema de descoberta de genes. Neste modelo, todos os sensores são HMMs. O módulo exon é essencialmente uma cadeia de Markov não homogênea de primeira ordem, que é descrita acima. Esta é a ordem natural de implementação em um HMM, porque então cada uma das probabilidades condicionais da cadeia de Markov não homogênea corresponde à probabilidade de uma transição de um estado para o próximo no HMM. Não é possível evitar os códons de parada no quadro de leitura ao usar um modelo de primeira ordem, mas em VEIL são adicionados mais alguns estados de forma inteligente, o que faz com que a probabilidade de um códon de parada seja zero. Os sensores para locais de emenda são feitos de forma semelhante. Os módulos individuais são então combinados essencialmente como na Figura 11.2 (ou seja, a consistência do quadro não é aplicada). O modelo combinado é um grande HMM, e todas as transições têm probabilidades associadas. Estas probabilidades podem ser estimadas a partir de um conjunto de dados de treinamento por um método de máxima verosimilhança. Para combinar os modelos, isto se resume essencialmente à contagem das ocorrências dos diferentes tipos de transições no conjunto de dados. Portanto, a ponderação implícita dos sensores individuais não é realmente um problema.

Embora a forma como a estrutura genética ótima é encontrada seja similar em espírito à programação dinâmica acima, ela parece bastante diferente na prática. Isto porque a programação dinâmica é feita ao nível dos estados individuais em todos os submodelos; existem mais de 200 estados deste tipo no VEIL. Como o modelo é totalmente probabilístico, pode-se calcular a probabilidade de qualquer sequência de estados para uma dada sequência de ADN. Essa seqüência de estados (chamada de caminho) determina a atribuição de exons e introns. Se o caminho passa pelo modelo exon, essa parte da seqüência é rotulada como exon; se passa pelo modelo intron, é rotulada como intron, e assim por diante. O algoritmo de programação dinâmica, que é chamado algoritmo Viterbi, encontra o caminho mais provável através do modelo para uma dada sequência, e a partir dele a estrutura genética prevista é derivada (ver Rabiner (1989) para uma introdução geral aos HMMs).

Este modelo probabilístico tem a vantagem de resolver o problema da ponderação dos sensores individuais. A estimativa da máxima verosimilhança dos parâmetros pode ser mostrada como ótima se houver dados suficientes de treinamento e se a natureza estatística dos genes puder ser descrita por tal modelo. Uma parte fraca do VEIL é o modelo exon de primeira ordem, que provavelmente não é capaz de capturar as estatísticas das regiões codificadas, e a maioria dos outros métodos usam modelos de quarta ou quinta ordem.

Um localizador de genes baseado em HMM chamado HMMgene está sendo desenvolvido atualmente. O método básico é o mesmo que VEIL, mas inclui várias extensões da metodologia padrão HMM, que são descritas por Krogh (1997). Uma das mais importantes é que as regiões codificadoras são modeladas por uma cadeia de Markov de quarta ordem não homogênea, ao invés de uma cadeia de primeira ordem. Isso é feito por uma extensão quase trivial do formalismo padrão de HMM, que permite uma cadeia de Markov de qualquer ordem em um estado do modelo, enquanto o HMM padrão tem uma simples distribuição de probabilidade incondicional sobre as quatro bases (correspondente à 0ª ordem). O modelo é sensível ao quadro e pode prever qualquer número de genes e genes parciais, então a estrutura geral do modelo é como na Figura 11.4 com transições adicionadas para permitir início e fim em introns, como na Figura 11.3.

Como já mencionado, o método de estimação de máxima verosimilhança funciona bem se a estrutura do modelo puder descrever a verdadeira estatística dos genes. Esta é uma suposição muito idealizada, e portanto HMMgene usa outro método para estimar os parâmetros chamados de máxima verosimilhança condicional (Juang e Rabiner, 1991; Krogh, 1994). Falando vagamente, a máxima verosimilhança maximiza a probabilidade das seqüências de DNA no conjunto de treinamento, enquanto a máxima verosimilhança condicional maximiza a probabilidade das estruturas gênicas dessas seqüências, que, afinal de contas, é o que nos interessa. Este tipo de optimização é conceptualmente semelhante à utilizada no GeneParser, onde a precisão da predição também é optimizada. HMMgene também usa um algoritmo de programação dinâmico diferente do algoritmo de Viterbi para a predição da estrutura genética. Todos esses métodos contribuíram para um alto desempenho do HMMgene.

Genie é outro exemplo de um modelo de estado probabilístico que é chamado de HMM generalizado (Kulp et al., 1996; Reese et al., 1997). A Figura 11.4 é de fato a estrutura de estado de Genie, e tanto esta figura quanto a Figura 11.2 são essencialmente copiadas de Kulp et al. (1996). No Genie, os sensores de sinal (locais de emenda) e os sensores de conteúdo (potencial de codificação) são redes neurais, e a saída dessas redes é interpretada como probabilidades. Esta interpretação requer a estimativa de parâmetros de probabilidade adicionais que funcionam como pesos nos sensores. Assim, embora seja formulado como um modelo probabilístico, o problema de ponderação ainda aparece disfarçado. O algoritmo de predição é quase idêntico ao algoritmo de programação dinâmica da última seção. Uma versão do Genie também inclui similaridades de banco de dados como parte do sensor exon (Kulp et al., 1997).

Existem duas vantagens principais dos HMMs generalizados em comparação com os HMMs padrão. Primeiro, os sensores individuais podem ser de qualquer tipo, tais como redes neurais, enquanto em um HMM padrão eles são restritos pela estrutura de HMM. Segundo, a distribuição de comprimento (de, por exemplo, regiões codificadoras) pode ser levada em conta explicitamente, enquanto a distribuição de comprimento natural para um HMM é uma distribuição geométrica, que decai exponencialmente com o comprimento. Entretanto, é possível ter uma modelagem de comprimento razoavelmente avançada em um HMM se vários estados forem usados (Durbin et al., 1998). A vantagem de um sistema como o HMMgene, por outro lado, é que ele é um modelo integrado, que pode ser otimizado de uma só vez para máxima precisão de previsão.

Outro buscador de genes baseado em um HMM generalizado é o GENSCAN (Burge and Karlin, 1997). As principais diferenças entre a estrutura de estado do GENSCAN e a do Genie ou HMMgene é que o GENSCAN modela a seqüência em ambas as direções simultaneamente. Em muitos buscadores de genes, como os descritos acima, os genes são primeiramente previstos em uma vertente, e depois na outra. A modelagem simultânea das duas vertentes foi feita com muito sucesso no GeneMark, e um método similar é implementado no GENSCAN. Uma vantagem (e talvez a principal) é que esta construção evita previsões de genes sobrepostos nas duas vertentes, que presumivelmente são muito raros no genoma humano. O GENSCAN modela qualquer número de genes e genes parciais como o HMMgene. Os sensores no GENSCAN são similares aos usados no HMMgene. Por exemplo, o sensor codificador é uma cadeia de Markov não homogênea de quinta ordem. Os sensores de sinal são essencialmente matrizes de peso dependentes da posição, e assim também são muito similares aos do HMMgene, mas existem características mais avançadas nos modelos de locais de emenda. O GENSCAN também é um modelo de promotores e os UTRs de 5′ e 3′.

.