Ejemplo Algoritmo Viterbi - Example of a Viterbi algorithm applied to a hidden Markov model on DNA sequence

Overview

Ejemplo Algoritmo Viterbi

Ejemplo de un algoritmo Viterbi aplicado a modelo oculto de Márkov sobre secuencia de ADN

Introducción.

En los diferentes campos existen fenómenos estocásticos cuyas variables de estudio presentan una evolución temporal, de tal forma, que el valor futuro de las variables de estudio depende únicamente de su valor presente, siendo independiente del histórico de la variable. Cuando el proceso de estudio presenta esta característica, se dice que cumple con la propiedad de Márkov y por tanto se pueden modelar en procesos de Márkov.

Un proceso de Márkov es una serie de experimentos en el que cada uno tiene m posibles resultados (E1, E2.....Em), y la probabilidad de cada resultado depende exclusivamente del que se haya obtenido en los experimentos previos, o lo que es lo mismo, el valor futuro depende de su valor presente. Adicionalmente, cuando los parámetros no se conocen, se dice que el problema está expresado en un modelo oculto de Márkov (HMM por sus siglas en ingles)

Mediante un simple ejemplo, se pretende resolver un problema de secuenciación de ADN expresado en un HMM usando un algoritmo de Viterbi programado en lenguaje Python.

Problema propuesto.

Considere un problema de bioinformática de 2 estados: Alto y Bajo. El estado alto caracteriza ADN codificado (Alto contenido de Guanina y Citosina) y el estado bajo caracteriza ADN no codificado (Bajo contenido de Guanina y citosina). El problema tiene las siguientes probabilidades:

  • Inicio.
    • Estado alto: 0.5
    • Estado bajo: 0.5
  • Transición:
    • Alto a bajo: 0.5
    • Alto a alto: 0.5
    • Bajo a alto: 0.4
    • Bajo a bajo: 0.6
  • Emisión estado alto:
    • Adenina: 0.2
    • Citosina: 0.3
    • Guanina: 0.3
    • Timina: 0.2
  • Emisión estado bajo:
    • Adenina: 0.3
    • Citosina: 0.2
    • Guanina: 0.2
    • Timina: 0.3

Conociendo las probabilidades de inicio, transición y emisión, es posible modelar en un HMM, tal como se muestra a continuación:

modelo HMM

El modelo puede ser usado para predecir la región de ADN codificado dada una secuencia:

  • GGCACTGAA

Metodología y algoritmo

Para resolver este problema de estado oculto de Márkov se aprovechará el algoritmo de Viterbi. El algoritmo de Viterbi es un algoritmo de programación dinámica que permite calcular la ruta de estados mas probable en un modelo de estado oculto HMM, es decir, obtiene la secuencia óptima que mejor explica la secuencia de observaciones. (Para mas información ver https://en.wikipedia.org/wiki/Viterbi_algorithm)

El algoritmo

El algoritmo fue desarrollado en Python sin uso de librerías o módulos extra. [DNA_viterbi.py] En la cabecera del código, se programaron 2 ejemplos de secuencia como tupla de caracteres, siendo la secuencia 1 la requerida en el problema (GGCACTGAA). Posteriormente se programan las probabilidades del problema. Estados como lista de caracteres, y probabilidades como diccionarios anidados. Finalmente, el código contiene dos funciones:

  • viterbi: Algoritmo de interés que procesa el HMM.
  • dptable: Función auxiliar para la impresión de resultados por consola.

Resultados

Al ejecutar el algoritmo anterior se obtienen los siguientes resultados:

G G C A C T G A A
Alto (H) 0.15000 0.02250 0.00337 0.00033 0.00006 0.00000 0.00000 0.00000 0.00000
Bajo (L) 0.10000 0.01500 0.00225 0.00050 0.00006 0.00001 0.00000 0.00000 0.00000

De estos resultados se obtiene que la ruta mas probable de estado es:

H -> H -> H -> L -> L -> L -> L -> L -> L

con una mayor probabilidad de 4.25e-08

Referencias

You might also like...
Sequence to Sequence Models with PyTorch
Sequence to Sequence Models with PyTorch

Sequence to Sequence models with PyTorch This repository contains implementations of Sequence to Sequence (Seq2Seq) models in PyTorch At present it ha

Sequence-to-Sequence learning using PyTorch

Seq2Seq in PyTorch This is a complete suite for training sequence-to-sequence models in PyTorch. It consists of several models and code to both train

Pervasive Attention: 2D Convolutional Networks for Sequence-to-Sequence Prediction

This is a fork of Fairseq(-py) with implementations of the following models: Pervasive Attention - 2D Convolutional Neural Networks for Sequence-to-Se

An implementation of a sequence to sequence neural network using an encoder-decoder
An implementation of a sequence to sequence neural network using an encoder-decoder

Keras implementation of a sequence to sequence model for time series prediction using an encoder-decoder architecture. I created this post to share a

Sequence lineage information extracted from RKI sequence data repo
Sequence lineage information extracted from RKI sequence data repo

Pango lineage information for German SARS-CoV-2 sequences This repository contains a join of the metadata and pango lineage tables of all German SARS-

Official repository of OFA. Paper: Unifying Architectures, Tasks, and Modalities Through a Simple Sequence-to-Sequence Learning Framework
Official repository of OFA. Paper: Unifying Architectures, Tasks, and Modalities Through a Simple Sequence-to-Sequence Learning Framework

Paper | Blog OFA is a unified multimodal pretrained model that unifies modalities (i.e., cross-modality, vision, language) and tasks (e.g., image gene

DNA-RECON { Automatic Web Reconnaissance Tool }
DNA-RECON { Automatic Web Reconnaissance Tool }

ABOUT TOOL : DNA-RECON is an automatic web reconnaissance tool written in python. This tool made for reconnaissance and information gathering with an

Using deep learning to predict gene structures of the coding genes in DNA sequences of Arabidopsis thaliana

DeepGeneAnnotator: A tool to annotate the gene in the genome The master thesis of the "Using deep learning to predict gene structures of the coding ge

A repository with exploration into using transformers to predict DNA ↔ transcription factor binding

Transcription Factor binding predictions with Attention and Transformers A repository with exploration into using transformers to predict DNA ↔ transc

Owner
Mateo Velásquez Molina
Mateo Velásquez Molina
Exploit Camera Raw Data for Video Super-Resolution via Hidden Markov Model Inference

RawVSR This repo contains the official codes for our paper: Exploit Camera Raw Data for Video Super-Resolution via Hidden Markov Model Inference Xiaoh

Xiaohong Liu 23 Oct 8, 2022
A library for hidden semi-Markov models with explicit durations

hsmmlearn hsmmlearn is a library for unsupervised learning of hidden semi-Markov models with explicit durations. It is a port of the hsmm package for

Joris Vankerschaver 69 Dec 20, 2022
HiddenMarkovModel implements hidden Markov models with Gaussian mixtures as distributions on top of TensorFlow

Class HiddenMarkovModel HiddenMarkovModel implements hidden Markov models with Gaussian mixtures as distributions on top of TensorFlow 2.0 Installatio

Susara Thenuwara 2 Nov 3, 2021
Quick program made to generate alpha and delta tables for Hidden Markov Models

HMM_Calc Functions for generating Alpha and Delta tables from a Hidden Markov Model. Parameters: a: Matrix of transition probabilities. a[i][j] = a_{i

Adem Odza 1 Dec 4, 2021
Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Optimization Algorithm,Immune Algorithm, Artificial Fish Swarm Algorithm, Differential Evolution and TSP(Traveling salesman)

scikit-opt Swarm Intelligence in Python (Genetic Algorithm, Particle Swarm Optimization, Simulated Annealing, Ant Colony Algorithm, Immune Algorithm,A

郭飞 3.7k Jan 3, 2023
Implementation of SETR model, Original paper: Rethinking Semantic Segmentation from a Sequence-to-Sequence Perspective with Transformers.

SETR - Pytorch Since the original paper (Rethinking Semantic Segmentation from a Sequence-to-Sequence Perspective with Transformers.) has no official

zhaohu xing 112 Dec 16, 2022
In this project we investigate the performance of the SetCon model on realistic video footage. Therefore, we implemented the model in PyTorch and tested the model on two example videos.

Contrastive Learning of Object Representations Supervisor: Prof. Dr. Gemma Roig Institutions: Goethe University CVAI - Computational Vision & Artifici

Dirk Neuhäuser 6 Dec 8, 2022
Rethinking Semantic Segmentation from a Sequence-to-Sequence Perspective with Transformers

Segmentation Transformer Implementation of Segmentation Transformer in PyTorch, a new model to achieve SOTA in semantic segmentation while using trans

Abhay Gupta 161 Dec 8, 2022
Understanding and Improving Encoder Layer Fusion in Sequence-to-Sequence Learning (ICLR 2021)

Understanding and Improving Encoder Layer Fusion in Sequence-to-Sequence Learning (ICLR 2021) Citation Please cite as: @inproceedings{liu2020understan

Sunbow Liu 22 Nov 25, 2022
[CVPR 2021] Rethinking Semantic Segmentation from a Sequence-to-Sequence Perspective with Transformers

[CVPR 2021] Rethinking Semantic Segmentation from a Sequence-to-Sequence Perspective with Transformers

Fudan Zhang Vision Group 897 Jan 5, 2023