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

Owner
Mateo Velásquez Molina
Mateo Velásquez Molina
Code for "Learning Structural Edits via Incremental Tree Transformations" (ICLR'21)

Learning Structural Edits via Incremental Tree Transformations Code for "Learning Structural Edits via Incremental Tree Transformations" (ICLR'21) 1.

NeuLab 40 Dec 23, 2022
State of the Art Neural Networks for Generative Deep Learning

pyradox-generative State of the Art Neural Networks for Generative Deep Learning Table of Contents pyradox-generative Table of Contents Installation U

Ritvik Rastogi 8 Sep 29, 2022
Rest API Written In Python To Classify NSFW Images.

Rest API Written In Python To Classify NSFW Images.

Wahyusaputra 2 Dec 23, 2021
Automatic self-diagnosis program (python required)Automatic self-diagnosis program (python required)

auto-self-checker 자동으로 자가진단 해주는 프로그램(python 필요) 중요 이 프로그램이 실행될때에는 절대로 마우스포인터를 움직이거나 키보드를 건드리면 안된다(화면인식, 마우스포인터로 직접 클릭) 사용법 프로그램을 구동할 폴더 내의 cmd창에서 pip

1 Dec 30, 2021
This repository contains the code used for the implementation of the paper "Probabilistic Regression with HuberDistributions"

Public_prob_regression_with_huber_distributions This repository contains the code used for the implementation of the paper "Probabilistic Regression w

David Mohlin 1 Dec 04, 2021
Non-Homogeneous Poisson Process Intensity Modeling and Estimation using Measure Transport

Non-Homogeneous Poisson Process Intensity Modeling and Estimation using Measure Transport This GitHub page provides code for reproducing the results i

Andrew Zammit Mangion 1 Nov 08, 2021
SurvITE: Learning Heterogeneous Treatment Effects from Time-to-Event Data

SurvITE: Learning Heterogeneous Treatment Effects from Time-to-Event Data SurvITE: Learning Heterogeneous Treatment Effects from Time-to-Event Data Au

14 Nov 28, 2022
Code for the SIGGRAPH 2021 paper "Consistent Depth of Moving Objects in Video".

Consistent Depth of Moving Objects in Video This repository contains training code for the SIGGRAPH 2021 paper "Consistent Depth of Moving Objects in

Google 203 Jan 05, 2023
This repository contains the implementation of the paper Contrastive Instance Association for 4D Panoptic Segmentation using Sequences of 3D LiDAR Scans

Contrastive Instance Association for 4D Panoptic Segmentation using Sequences of 3D LiDAR Scans This repository contains the implementation of the pap

Photogrammetry & Robotics Bonn 40 Dec 01, 2022
🤖 A Python library for learning and evaluating knowledge graph embeddings

PyKEEN PyKEEN (Python KnowlEdge EmbeddiNgs) is a Python package designed to train and evaluate knowledge graph embedding models (incorporating multi-m

PyKEEN 1.1k Jan 09, 2023
Contrastive Learning Inverts the Data Generating Process

Official code to reproduce the results and data presented in the paper Contrastive Learning Inverts the Data Generating Process.

71 Nov 25, 2022
Quickly and easily create / train a custom DeepDream model

Dream-Creator This project aims to simplify the process of creating a custom DeepDream model by using pretrained GoogleNet models and custom image dat

55 Dec 27, 2022
Sionna: An Open-Source Library for Next-Generation Physical Layer Research

Sionna: An Open-Source Library for Next-Generation Physical Layer Research Sionna™ is an open-source Python library for link-level simulations of digi

NVIDIA Research Projects 313 Dec 22, 2022
[ICLR 2021] Heteroskedastic and Imbalanced Deep Learning with Adaptive Regularization

Heteroskedastic and Imbalanced Deep Learning with Adaptive Regularization Kaidi Cao, Yining Chen, Junwei Lu, Nikos Arechiga, Adrien Gaidon, Tengyu Ma

Kaidi Cao 29 Oct 20, 2022
A C implementation for creating 2D voronoi diagrams

Branch OSX/Linux Windows master dev jc_voronoi A fast C/C++ header only implementation for creating 2D Voronoi diagrams from a point set Uses Fortune'

Mathias Westerdahl 481 Dec 29, 2022
Code for Motion Representations for Articulated Animation paper

Motion Representations for Articulated Animation This repository contains the source code for the CVPR'2021 paper Motion Representations for Articulat

Snap Research 851 Jan 09, 2023
This repository contains the code for our fast polygonal building extraction from overhead images pipeline.

Polygonal Building Segmentation by Frame Field Learning We add a frame field output to an image segmentation neural network to improve segmentation qu

Nicolas Girard 186 Jan 04, 2023
Training Structured Neural Networks Through Manifold Identification and Variance Reduction

Training Structured Neural Networks Through Manifold Identification and Variance Reduction This repository is a pytorch implementation of the Regulari

0 Dec 23, 2021
[ICCV'21] Pri3D: Can 3D Priors Help 2D Representation Learning?

Pri3D: Can 3D Priors Help 2D Representation Learning? [ICCV 2021] Pri3D leverages 3D priors for downstream 2D image understanding tasks: during pre-tr

Ji Hou 124 Jan 06, 2023
Official code for "Decoupling Zero-Shot Semantic Segmentation"

Decoupling Zero-Shot Semantic Segmentation This is the official code for the arxiv. ZegFormer is the first framework that decouple the zero-shot seman

Jian Ding 108 Dec 30, 2022