UNIVERSIDAD DE GUADALAJARA

Centro Universitario de Ciencias Exactas e Ingenierías

División de Electrónica y Computación

Análisis de agrupamiento de secuencias de ADN

usando BIRCH
Modalidad
Tesis, tesina e informes

Opción
Tesis

Que para obtener el grado de

Ingeniero en Informática

PRESENTA
Marlon Israel Nuño Rodríguez

Directora: Sulema Torres Ramos

Asesor: Israel Román Godínez

Guadalajara, Jalisco; Agosto de 2021.

Agradecimientos.

Quiero agradecer al Dr. Héctor Montoya Fuentes del Centro de Investigación Biomédica de
Occidente (CIBO) y jefe del Laboratorio de Apoyo a la Vigilancia Epidemiológica del I.M.S.S., por
su tiempo y asesoría.
A la Dra. Sulema Torres Ramos y al Dr. Israel Román Godínez les agradezco por su tiempo,
paciencia y la dirección durante el desarrollo de este trabajo.

Dedicatoria.
Quiero dedicar el presente trabajo al Dr. Luis Casillas Santillán quien fue la primera persona que
me introdujo a la ciencia computacional, por toda su dedicación, paciencia, amistad dentro y
fuera del salón de clases. Que la fuerza esté siempre con usted. En Memoria
 Tabla de contenido

1. Introducción ....................................................................................................................................1
2. Antecedentes ...................................................................................................................................3
3. Justificación.....................................................................................................................................5
4. Objetivo General .............................................................................................................................7
4.1. Objetivos específicos ...............................................................................................................7
5. Hipótesis..........................................................................................................................................8
6. Marco Teórico .................................................................................................................................9
6.1. ADN (Ácido Desoxirribonucleico) .........................................................................................9
6.1.1. Secuencia de ADN ..................................................................................................... 10
6.1.2. Genes y cromosomas.................................................................................................. 10
6.1.3. Genoma ...................................................................................................................... 10
6.2. Filogenia ............................................................................................................................... 11
6.2.1. Árbol filogenético ...................................................................................................... 11
6.2.2. Construcción del árbol filogenético ........................................................................... 12
6.2.3. Métodos de matrices de distancia............................................................................... 12
6.2.4. Anatomía de un árbol filogenético ............................................................................. 13
6.3. Bioinformática ...................................................................................................................... 14
6.3.1. Análisis de secuencias genómicas .............................................................................. 14
6.3.2. Representación digital del ADN ................................................................................ 14
6.3.2.1. Archivo FASTA ............................................................................................ 15
6.3.3. Señal genómica .......................................................................................................... 15
6.3.3.1. Procesamiento de señales genómicas (GSP) ................................................. 16
6.3.4. Métodos de representación numérica ......................................................................... 16
6.3.4.1. Mapeos basados en propiedades fisicoquímicas ........................................... 17
6.3.4.2. Mapeos fijos .................................................................................................. 17
6.3.5. Aprendizaje automático ............................................................................................. 18
6.3.5.1. Caracterización .............................................................................................. 19
6.3.5.1.1. Transformada rápida de Fourier ..................................................... 19
6.3.6. Agrupamiento............................................................................................................. 20
6.3.6.1. Métodos de agrupamiento jerárquico ............................................................ 21
6.3.6.1.1. Algoritmo BIRCH .......................................................................... 21

ii
7. Metodología ................................................................................................................................. 25
7.1. Entendimiento del problema................................................................................................. 25
7.2. Definición de algoritmos y herramientas.............................................................................. 26
7.2.1. Adquisición de datos .................................................................................................. 26
7.2.2. Transformación .......................................................................................................... 26
7.2.3. Caracterización........................................................................................................... 27
7.2.4. Clustering ................................................................................................................... 27
7.3. Implementación .................................................................................................................... 28
8. Resultados .................................................................................................................................... 35
8.1. Datos de experimentación y validación ................................................................................ 35
8.2. Diseño de experimentos y resultados obtenidos ................................................................... 36
9. Conclusiones ................................................................................................................................ 47
Bibliografía........................................................................................................................................ 49

iii
 Índice de figuras
Figura 1. Estructura del ADN ............................................................................................................ 9
Figura 2. Representación gráfica del gen ......................................................................................... 10
Figura 3. Cromosomas del genoma humano ..................................................................................... 11
Figura 4. Ejemplo de árbol filogenético ........................................................................................... 12
Figura 5. Matriz de distancias para construcción de árbol filogenético ............................................ 13
Figura 6. Estructura del árbol filogenético ....................................................................................... 14
Figura 7. Formato de archivo FASTA............................................................................................... 15
Figura 8. Mapeo de secuencia de ADN a señal Genómica ............................................................... 16
Figura 9. Funciones de mapeo fisicoquímicas de ADN .................................................................. 17
Figura 10. Funciones de mapeo fijo de ADN ................................................................................... 18
Figura 11. Representación gráfica de la transformada rápida de Fourier.......................................... 20
Figura 12. Ejemplo de agrupamiento ................................................................................................ 20
Figura 13. Ejemplo de agrupamiento jerárquico ............................................................................... 21
Figura 14. Creación de clúster con BIRCH ...................................................................................... 23
Figura 15. Ejemplo de Cluster Feature Tree .................................................................................... 24
Figura 16. Etapas de la metodología ................................................................................................. 25
Figura 17. Ejemplo de transformación de secuencia de ADN a señal genómica usando Voss ......... 27
Figura 18. Arquitectura del sistema implementado para el agrupamiento de señales genómicas ..... 29
Figura 19. Flujo del programa ........................................................................................................... 29
Figura 20. Archivo de configuración del programa .......................................................................... 31
Figura 21. Objeto Entrez ................................................................................................................... 31
Figura 22. Implementación de la transformada rápida de Fourier .................................................... 33
Figura 23. Implementación de la función Birch ................................................................................ 33
Figura 24. Resultados de salida de la función Birch ......................................................................... 34
Figura 25. Árbol filogenético del Papiloma Humano (HPV) ........................................................... 35
Figura 26. Ploteo del experimento I – variantes de HPV de diferentes grupos ................................. 38
Figura 27. Ploteo del experimento II – variantes de HPV del grupo A7........................................... 40
Figura 28. Ploteo del experimento III - Variantes de HPV del grupo A9 ......................................... 41
Figura 29. Ploteo del experimento IV – variantes de HPV del grupo A5-A6 ................................... 43
Figura 30. Ploteo del experimento V – agrupamiento de HPV de distintos grupos .......................... 45

iv
 Índice de tablas

Tabla 1. Resultados de agrupamiento del experimento I:variantes de HPV de diferentes grupos .... 34
Tabla 2. Resultados de agrupamiento del experimento II: variantes de HPV del grupo A7 ............. 35
Tabla 3. Resultados de agrupamiento del experimento III: variantes de HPV del grupo A9............ 37
Tabla 4. Resultados de agrupamiento del experimento IV: variantes de HPV del grupo A5-A6 ..... 38
Tabla 5. Resultados de agrupamiento del experimento V: HPV de distintos grupos ........................ 40

v
1. Introducción

Estamos entrando en la era del Big Data, donde miles de datos son generados día a día,

ejemplo de esto son los genomas de miles de organismos que han sido secuenciados por

diversos laboratorios. Esta abundancia de datos crea la necesidad de implementar métodos

automatizados para su análisis, lo cual crea un área de oportunidad para el aprendizaje

automático o aprendizaje máquina, el cual puede verse como un conjunto de métodos que

pueden detectar automáticamente patrones, y luego usar estos patrones para llevar a cabo

predicciones o realizar toma de decisiones bajo escenarios de incertidumbre [1]. Un área de

estudio que se ha visto beneficiada recientemente con el uso de métodos de aprendizaje

máquina es la Bioinformática, siendo ésta, el estudio de cómo la información es representada

y analizada en sistemas biológicos, especialmente información derivada a nivel molecular

[2]. Para adentrarnos más en el área de aplicación del aprendizaje máquina dentro de esta

disciplina, abordaremos primero el concepto de la Genómica, área de estudio de la

Bioinformática cuyo término fue acuñado por Thomas Roderick en 1986, definiéndose como

la disciplina científica encargada de la secuenciación y descripción de los genomas completos

[3]. Uno de los campos de aplicación de la Genómica es la Genómica Comparativa, que se

encarga de comparar dos o más genomas con el objetivo de encontrar similitudes y

diferencias de éstos, brindando información de la biología del organismo [4]. Para llevar a

cabo esta tarea comparativa, una de las actividades básicas del análisis computacional en la

biología es el alineamiento de pares de secuencias de Ácido Desoxiribonucleico (ADN), cuya

meta principal es alinear dos secuencias de tal forma que la relación evolutiva de ellos sea

simple de notar, basándose este método en principios de Homología que nos dicen que las

secuencias tienen una historia evolutiva compartida, y por ende se da por hecho que poseen

1
una secuencia ancestral en común [5]. Para realizar estas tareas del descubrimiento de las

relaciones evolutivas, se han implementado herramientas computacionales de aprendizaje no

supervisado como el agrupamiento (clustering, en inglés), que es útil para el reconocimiento

de patrones, el análisis de datos estadísticos y en la minería de datos [6]. Siendo la principal

ventaja de emplear técnicas de agrupamiento, la posibilidad de encontrar una estructura

oculta en los datos sin contar con información previa al respecto. Una tarea de agrupación

consiste en dividir un conjunto de datos en grupos (es decir, agrupaciones) que comparten

propiedades comunes o que están relacionadas de alguna manera, de acuerdo con criterios

dados y métricas de similitud [7]. Algunas herramientas que emplean algoritmos de

agrupamiento en secuencias biológicas son CD-HIT [8] y UCLUS [9], sin embargo, el

número de secuencias que pueden agrupar dichas herramientas puede ser limitado ya que, a

medida que aumenta el número de secuencias, incrementa el tiempo computacional [10]. Por

ello recientemente los investigadores han puesto su atención en un nuevo enfoque para llevar

a cabo el análisis de secuencias de ADN, que es el procesamiento de señales genómicas (GSP,

por sus siglas en inglés) [11], que está basado en el uso de técnicas de procesamiento digital

de señales (DSP, por sus siglas en inglés) [12]. Una de las principales ventajas de los métodos

de GSP es que el análisis de datos genómicos puede realizarse muy rápidamente debido a la

codificación de las secuencias y a los procesos que han sido diseñados específicamente para

esas tareas [13]. Dentro de esta área, primero se busca mapear secuencias de ADN a señales

genómicas, es decir, transformar las secuencias representadas como una cadena de caracteres

(A, T, G y C) a una representación numérica, para posteriormente poder llevar a cabo el

procesamiento y análisis de dichas secuencias vistas como una señal.

2
2. Antecedentes

Existen trabajos en el estado del arte que utilizan procesamiento de señales genómicas y

clustering con el fin de encontrar similitudes en organismos. Como es el caso del trabajo

Genomic signal processing for DNA sequence clustering [14], en donde se utiliza el

algortimo K-means y la función de mapeo Voss para encontrar semejanzas en 141 secuencias

de ADN pertenecientes a 131 especies distintas; en dicho trabajo se demostró que con el

enfoque GSP es posible agrupar organismos vivos sin necesidad de utilizar un alineamiento

múltiple de secuencias genéticas, tomando como referencia el gen codificador Mitochondrial

Cytochrome C Oxidase Subunit I (COXI) para validar los resultados del trabajo, ya que este

gen es relevante para las clasificaciones de organismos brindadas por la filogenia.

Así mismo en el artículo Análisis de representaciones numéricas de secuencias de ADN

usando K-means [15] se trabajó en experimentar los resultados obtenidos al utilizar diferentes

funciones de mapeo (mapeos fijos y mapeos basados en propiedades fisicoquímicas). En

dicho trabajo se utilizaron secuencias genéticas de organismos de los diferentes reinos de la

naturaleza: reino animal, reino vegetal o plantas, reino de los hongos, reino monera (también

llamado bacterias) y reino protista. Dicho trabajo obtuvo como resultado que la función de

mapeo Electron-ion generó buenos resultados en el agrupamiento.

Por otra parte, el trabajo Clustering by phenotype and genome-wide association study in

autism [16] utiliza el algoritmo K-means bajo un enfoque distinto al de GSP para encontrar

relaciones genéticas entre los diferentes casos del Trastorno del Espectro Autista (ASD),

debido a que a un nivel genético sus características son muy heterogéneas por lo que

encontrar la relación común es una tarea difícil. Este trabajo se basa en un estudio de

simulación que validó que se pudiera encontrar la herencia oculta en este trastorno, al agrupar

3
a distintos pacientes en pequeños subgrupos homogéneos basados en que tan complejo fuera

su trastorno. Este trabajo demostró que si el conjunto de datos consta de múltiples subgrupos

genéticamente heterogéneos, incluso un subgrupo que incluye un número mucho menor de

individuos homogéneos, se pudieran llegar a detectar factores genéticos de alto impacto al

utilizar un enfoque de clustering con K-means.

Por otro lado, en el trabajo Clustering of Mitochondrial D-loop Sequences Using Similarity

Matrix, PCA and K-means Algorithm [17] se realizó una aproximación distinta al

implementar una matriz de semejanzas sobre el conjunto de organismos basada en las

distancias de los pares genéticos de éstos con el fin de generar un árbol filogénico con estas

distancias, para después realizar el agrupamiento combinando tanto el algoritmo K-means

como la técnica estadística del Análisis de Componentes Principales (PCA, por sus siglas en

inglés). En dicho trabajo se obtuvieron resultados exitosos de clasificación al combinar estas

tres herramientas.

Finalmente, a pesar de que existen otros trabajos en el estado del arte que llevan a cabo el

agrupamiento de organismos, con o sin el enfoque GSP, se puede observar que dichos

trabajos utilizan en su mayoría K-means, y no se utilizan algoritmos jerárquicos para realizar

el agrupamiento de secuencias genéticas [18][19].

4
3. Justificación

Gracias a los avances de la ciencia computacional en el campo de la inteligencia artificial

y la bioinformática, se han obtenido avances en el desarrollo de métodos y técnicas, tales

como el agrupamiento de señales genómicas mediante algoritmos de agrupamiento; siendo

estos avances una puerta al desarrollo de nuevas herramientas computacionales. En muchos

trabajos se utiliza el algortimo K-means para el análisis de clustering en ADN [14][15],

llegando a ser muy popular su uso, debido a que este algoritmo realiza particiones rápidas en

los grupos de forma iterativa debido a su complejidad lineal, sin embargo su forma de crear

los grupos al posicionar los centroides de forma aleatoria y utilizar algún tipo de distancia

geométrica (como la distancia euclideana) nos deja todo un campo abierto para explorar

nuevos algoritmos de agrupamiento que toman como base otros factores para crear los

grupos.

Debido a lo anterior, el algoritmo jerárquico BIRCH podría ser una buena opción para

probar con el enfoque GSP por las siguientes razones: complejidad computacional y relación

con la filogenia.

Con respecto a la complejidad computacional, el algoritmo BIRCH en su primer paso

construye una estructura de datos llamada Cluster Feature Tree (CFT), la cual es un árbol de

compresión de los datos de entrada que toma como base la media y varianza estadística del

conjunto de entrada, que permite reducir los tiempos del agrupamiento al generar una imagen

estadística de todo el conjunto de entrada, recordando que las secuencias genómicas son de

gran tamaño por lo cual representan una gran complejidad computacional al ser procesadas

por el algoritmo de agrupamiento.

5
 Por otro lado, BIRCH utiliza un algoritmo basado en jerarquías ya que crea grupos con

respecto a la semejanza de los valores generados en el CFT, partiendo de pequeños grupos

individuales, para después ir uniendo de dos en dos cada grupo hasta formar un sólo clúster.

Cabe hacer notar que dichas jerarquías creadas se asemejan a lo observado en la filogenética,

en donde se busca agrupar, en una figura llamada dendograma, las familias de organismos

tomando como base las distancias genéticas entre éstos con respecto sus características.

6
4. Objetivo General

Utilizar el algoritmo de clustering jerárquico BIRCH para agrupar secuencias de ADN y

evaluar su desempeño en los grupos generados.

4.1. Objetivos específicos

1. Estudio del estado del arte sobre los algoritmos de agrupamiento que se utilizan para
formar grupos mediante secuencias genómicas.
2. Estudio del estado del arte sobre los algoritmos de clustering jerárquico.
3. Elegir las representaciones numéricas que se utilizarán en este análisis para mapear
las secuencias de ADN a señales genómicas.
4. Implementar las representaciones numéricas en un lenguaje de programación.
5. Implementar la transformada rápida de Fourier como caracterización de señales
genómicas.
6. Implementar el algoritmo de BIRCH para llevar a cabo el agrupamiento de señales
genómicas.
7. Definir los organismos a ser utilizados para el análisis y obtener su secuencia de
ADN.
8. Transformar las secuencias de ADN de los organismos elegidos utilizando las
representaciones numéricas implementadas en el punto 4.
9. Obtener las características de las señales genómicas de los organismos utilizando la
implementación del punto 5
10. Con base en las características obtenidas del punto anterior, llevar a cabo el
agrupamiento de los organismos utilizando la implementación del punto 6.
11. Comparar los grupos obtenidos contra el gold standar de los organismos
seleccionados del punto 7 y analizar los resultados.

7
5. Hipótesis

BIRCH es un método de agrupamiento jerárquico con el que es posible formar grupos, a

partir de señales genómicas de seres vivos, que se acoplen a la clasificación brindada por la

filogenética, ya que esta clasificación simula una estructura jerárquica basada en las

características genéticas de los seres vivos.

8
6. Marco Teórico

En esta sección se presentan los conceptos fundamentales para entender la metodología

empleada en el análisis computacional a organismos vivos. Este apartado define la

terminología biológica y computacional utilizada en el presente trabajo

6.1. ADN (Ácido Desoxirribonucleico)

El Ácido Desoxirribonucleico (o por sus siglas, ADN) es el nombre químico que se le

da a la molécula, contenida en las células, encargada de preservar la información genética de

todos los organismos vivos (como virus, bacterias, agentes patógenos). El ADN tiene una

forma de doble hélice compuesta por dos cadenas, formadas por azúcares y grupos fosfatos,

que se enrollan entre sí, gracias a la unión de sus cuatro bases nitrogenadas llamadas

nucleótidos: Adenina (A), Citosina (C), Guanina (G) y Timina (T). La doble hélice se

mantiene unida por los enlaces químicos entre las bases de nucleótidos; la adenina se une con

la timina, y la citosina con la guanina (Ver Figura 1) [20].

Figura 1. Estructura del ADN (Imagen tomada de [21])

9
6.1.1. Secuencia de ADN

Se le nombra secuencia de ADN al orden en que se configuran las cuatro bases de

nucleótidos; las técnicas y métodos utilizados para conocerla se le llama secuenciación.

Conocer el orden de los nucleótidos tiene múltiples aplicaciones como en la detección de las

relaciones evolutivas de los organismos; ya que, debido a su estructura, se determinan las

características genéticas que diferencian a los seres vivos [21].

6.1.2. Genes y cromosomas

Un gen es la unidad física elemental en la herencia, un gen contiene toda la

información necesaria para preservar sus rasgos en las próximas generaciones, esto se da al

momento en que los padres transmiten el material genético a sus descendientes. Los genes

están colocados, uno tras otro, en estructuras llamadas cromosomas. Un cromosoma es un

paquete de ADN ordenado que se ubica en el núcleo de la célula, conteniendo una única

molécula grande de ADN [22] (Ver Figura 2).

Figura 2. Representación gráfica del gen (Imagen tomada de [22])

6.1.3. Genoma

Se conoce como genoma al conjunto de instrucciones genéticas que se encuentran

10
dentro de una célula. Ejemplificando, en los seres humanos el genoma consiste en 23 pares

de cromosomas ubicados en el núcleo [23] (ver Figura 3).

Figura 3. Cromosomas del genoma humano (Imagen tomada de [23])

6.2. Filogenia

La filogenia es la representación de los lazos evolutivos entre los grupos de organismos

a través de la historia. Los resultados son mostrados en un árbol filogenético, cuyo análisis

está relacionado en el tipo de datos de entrada, número de especies y el alcance de la

interpretación de los lazos evolutivos [24].

6.2.1. Árbol filogenético

Un árbol filogenético es una representación gráfica de organismos vivos que están

conectados por un ancestro en común, el ancestro puede ser una especie o un grupo

taxonómico de mayor jerarquía a nivel evolutivo [25]. En la actualidad, la mayoría de los

árboles filogenéticos se crean a partir de la información molecular, ADN, ARN (Ácido

Ribonucleico) o proteínas. Cuando se analizan especies cercanamente emparentadas se tiende

11
a utilizar el ADN, porque provee más información debido a que las cadenas de ADN son más

largas que las cadenas de proteínas [26] (Ver Figura 4).

Figura 4. Ejemplo de árbol filogenético (Imagen tomada de [27])

6.2.2. Construcción del árbol filogenético

Los métodos para generar árboles filogenéticos se llegan a dividir en dos tipos: los

métodos basados en matrices de distancia y los basados en datos de caracteres discretos (las

bases de nucleótidos con las secuencias de ADN) [28].

6.2.3. Métodos de matrices de distancia

De los métodos que utilizan las matrices de distancia, el método de unión de vecinos

(Neighbor-Joining, NJ) es uno de los más populares. Este método (al igual que todos los

métodos de distancia), comienza a partir de la formación de una matriz de distancia, que

cuando se trabaja con secuencias de ADN, se genera al contar las diferencias de nucleótidos

de todos los pares de secuencias. Y finalmente, el árbol se crea al unir las secuencias que

12
posean la menor cantidad de diferencias, es decir la menor distancia genética [29] (Ver Figura

5).

Figura 5. Matriz de distancias para construcción de árbol filogenético (Imagen tomada de [30])

6.2.4. Anatomía de un árbol filogenético

Un árbol filogenético se compone de varios elementos. En la parte de la derecha de la

siguiente figura se encuentran los nodos terminales o puntas (A, B, C, D, E), que representan

a los taxones. Estos pueden ser elementos de una especie o grupos taxonómicos mayores.

Cada uno de estos nodos terminales se encuentran unidos mediante ramas a un nodo interno,

el cual representa al ancestro común entre los dos elementos. De tal forma que los nodos

terminales representan el presente, mientras que los nodos internos representan el pasado [29]

(Ver Figura 6).

13
 Figura 6. Estructura del árbol filogenético (Imagen tomada de [29])

6.3. Bioinformática

La bioinformática, de forma general, se puede definir como la disciplina científica que

implementa las herramientas de las tecnologías de la información para organizar, analizar y

distribuir información biológica, con el objetivo de responder a preguntas complejas que se

tienen en la biología. La bioinformática engloba métodos matemáticos, estadísticos y

computacionales para solucionar problemas biológicos usando la información molecular

como el ADN, ARN o las secuencias de aminoácidos [31].

6.3.1. Análisis de secuencias genómicas

El análisis de las secuencias de ADN es el descubrimiento de similitudes y

diferencias, tanto funcionales como estructurales, entre muchas secuencias biológicas. Esto

se logra al comparar las nuevas (desconocidas) con las bien-estudiadas y conocidas

secuencias. Este análisis incluye la alineación de secuencias, la búsqueda en bases de datos

de las secuencias, el descubrimiento de patrones, la reconstrucción de las relaciones

evolutivas, y la formación y la comparación del genoma [32].

6.3.2. Representación digital del ADN

Una representación digital del ADN consiste en una sucesión de las letras A, T, G y

C las cuales representan las bases nucleótidos que componen el ADN y cuyo orden es

14
determinado a partir de la secuenciación. Existen bases de datos biológicas enfocadas a

secuencias de ADN como la NCBI, que trabaja con distintos formatos de secuencia como

FASTA, el formato que se eligió para los archivos de entrada de este sistema [33].

6.3.2.1. Archivo FASTA

El formato FASTA consiste en una secuencia de ADN que empieza con una descripción de

una sola línea, seguida de líneas de datos (es decir, caracteres) de la secuencia de ADN. La

línea de descripción (defline) se diferencia de los datos de secuencia por el símbolo mayor

que (">") al comienzo. La Figura 7 muestra es un extracto de la secuencia de ADN del

organismo H. sapiens mitochondrial en formato FASTA [34].

Figura 7. Formato de archivo FASTA (Imagen tomada de [35])

6.3.3. Señal genómica

Una señal genómica es el resultado final de convertir, o dicho de otra manera, mapear

cada carácter o letra que conforma una secuencia de ADN a una representación numérica. En

15
la Figura 8 se puede ver un ejemplo de fragmento de secuencia mapeado a señal genómica

utilizando la representación numérica Integer.

Figura 8. Mapeo de secuencia de ADN a señal Genómica (Imagen tomada de [35])

6.3.3.1. Procesamiento de señales genómicas (GSP)

El procesamiento de señales genómicas se define como la disciplina de la ingeniería que

estudia el análisis, procesamiento y uso de señales genómicas para obtener información

biológica y utilizar la interpretación de ésta en aplicaciones basadas en sistemas. El objetivo

es unir la teoría y los métodos de procesamiento digital de señales con la comprensión global

de la genómica funcional. Por lo que abarca varias metodologías relacionadas con la

detección, predicción, clasificación, control y modelos estadísticos y dinámicos de redes de

genes [36][37].

6.3.4. Métodos de representación numérica

Para llevar a cabo el análisis de secuencias de ADN mediante el procesamiento de

señales digitales se necesita la conversión de una secuencia de bases (es decir, A, T, G y C)

a una secuencia numérica. Los métodos de representación numérica de secuencias de ADN

pueden clasificarse en dos grupos principales, mapeos fijos y mapeos basados en las

propiedades fisicoquímicas del ADN, los cuales se detallan a continuación [38].

16
6.3.4.1. Mapeos basados en propiedades fisicoquímicas

En este tipo de mapeos, las propiedades biofísicas y bioquímicas de las biomoléculas

de ADN se usan para el mapeo de las secuencias. Las representaciones numéricas de este tipo

de mapeos son Electron-ion Interaction Potential (EIIP), Atomic Number, Paired Numeric,

DNA Walk y Z-curve. (Ver Figura 9).

Figura 9. Funciones de mapeo fisicoquímicas de ADN (Imagen tomada de [38])

6.3.4.2. Mapeos fijos

En los mapeos fijos las bases de nucleótidos A, T, G y C de las secuencias de ADN

se transforman en una serie de secuencias numéricas arbitrarias. Dentro de estos mapeos se

encuentran las representaciones Voss, Tetrahedron, Integer, Real, Complex y Quaternion

(Ver Figura 10).

17
 Figura 10. Funciones de mapeo fijo de ADN (Imagen tomada de [38])

6.3.5. Aprendizaje automático

El aprendizaje automático es una rama en evolución de los algoritmos

computacionales que están diseñados para emular la inteligencia humana aprendiendo del

entorno que los rodea, sin estar esto último explícitamente programado. Las técnicas basadas

18
en el aprendizaje máquina se aplican con éxito en diversos campos que van desde el

reconocimiento de patrones, la visión por computadora, la ingeniería de naves espaciales, las

finanzas, el entretenimiento y la biología computacional [39].

6.3.5.1. Caracterización

En el campo del aprendizaje automático, la caracterización consiste en obtener un conjunto

de datos o características relevantes que componen a un elemento, las cuales sirven para

describir o generalizar a éste, en nuestro caso de estudio, a una señal genómica. Existen

diferentes métodos para la caracterización de señales, como la transformada de Wavelet [39],

la transformada discreta de Fourier [40] y la transformada rápida de Fourier [39], siendo esta

última la empleada en este trabajo.

6.3.5.1.1. Transformada rápida de Fourier

La transformada rápida de Fourier (FFT, por sus siglas en inglés) es un método utilizado para

calcular la transformada discreta de Fourier (DFT, por sus siglas en inglés), que produce el

mismo resultado que otros métodos, pero es más eficiente, ya que a menudo reduce el tiempo

del cálculo.

En el primer paso, la FFT descompone una señal de dominio de tiempo de N puntos

en N señales de dominio de tiempo compuestas de un solo punto. El segundo paso consiste

en calcular los N espectros de frecuencia correspondientes a estas N señales de dominio de

tiempo y los N espectros se sintetizan en un solo espectro de frecuencia. El tercer paso es

encontrar los espectros de frecuencia de las señales de dominio de tiempo de un punto. Y

finalmente se combinan los N espectros de frecuencia en el orden inverso en el que la

descomposición en el dominio del tiempo tuvo lugar de manera exacta [41] (Ver Figura 11).

19
 Figura 11. Representación gráfica de la transformada rápida de Fourier (Imagen tomada de [42])

6.3.6. Agrupamiento

El agrupamiento, o clustering en inglés, se refiere a la agrupación de registros,

observaciones o casos en clases de objetos similares. Un clúster es una colección de registros

que son similares entre sí y diferentes a los registros de otros clústeres. El agrupamiento en

clústeres se diferencia de la clasificación en que no hay una variable objetivo para agrupar.

Al agrupar no se intenta clasificar, estimar o predecir el valor de una variable objetivo. En

lugar de eso, los algoritmos de agrupamiento buscan segmentar todo el conjunto de datos en

subgrupos o grupos relativamente homogéneos, donde se maximiza la similitud de los

registros dentro del grupo y se minimiza la similitud con los registros fuera de este grupo

[43], como se muestra en la Figura 12.

Figura 12. Ejemplo de agrupamiento (Imagen tomada de [43])

20
6.3.6.1. Métodos de agrupamiento jerárquico

En la agrupación jerárquica, se crea una estructura de agrupación en forma de árbol

(dendrograma) mediante particiones recursivas (métodos de división) o combinación

(aglomeración) de agrupaciones existentes. Los métodos de agrupamiento aglomerativo

inicializan cada observación para crear un pequeño grupo propio. Luego, en los pasos

siguientes, los dos grupos más cercanos se agregan en un nuevo grupo combinado. De esta

manera, el número de grupos en el conjunto de datos se reduce en uno en cada paso.

Eventualmente, todos los registros se combinan en un solo grupo enorme [43] (ver Figura

13).

Figura 13. Ejemplo de agrupamiento jerárquico (Imagen tomada de [43])

6.3.6.1.1. Algoritmo BIRCH

El algoritmo Balanced Iterative Reducing and Clustering using Hierarchies o BIRCH por

sus siglas en inglés, fue desarrollado en 1996. BIRCH es eficiente para trabajar con conjuntos

21
de datos muy grandes debido a su capacidad para encontrar una buena solución de

agrupamiento con un solo escaneo de los datos. BIRCH maneja grandes conjuntos de datos

con una complejidad temporal y una eficiencia espacial superior a otros algoritmos, según

los autores [44].

Pasos del algoritmo

1. Construcción del árbol CF (Cluster Feature): Cargue los datos en la memoria construyendo un

árbol de características de clúster (árbol CF, definido a continuación). Opcionalmente, condense

este árbol CF inicial en un CF más pequeño

2. Agrupación global: Aplicar un algoritmo de agrupamiento existente en las hojas del árbol CF.

Cluster feature

El algoritmo de BIRCH logra su alta eficiencia gracias a que solo requiere una única pasada

a través del conjunto de datos para realizar la agrupación, para ello utiliza cluster features

que representan un conjunto de datos de forma resumida.

Un CF es un conjunto de tres valores estadísticos resumidos que representan un conjunto de

puntos de datos en un solo grupo. Estas estadísticas son las siguientes:

• Conteo: Cuántos datos hay en el clúster.

• Suma lineal: Sume las coordenadas individuales (X,Y). Esta es una medida de la

ubicación del clúster.

• Suma de cuadrados: Suma las coordenadas elevadas al cuadrado (X,Y). Esta es una

medida de la dispersión del clúster.

Recalcando que, juntas, la suma lineal y la suma al cuadrado son equivalentes a la media y

la varianza de los datos (ver Figura 14).

22
 Figura 14. Creación de clúster con BIRCH (Imagen tomada de [43])

Cluster feature tree

Un árbol CF es una estructura de árbol compuesta por CFS (ver Figura 15). Un árbol CF

representa una forma comprimida de los datos, preservando cualquier estructura de

agrupamiento en los datos. Un árbol CF tiene los siguientes parámetros:

• Factor de ramificación B: B determina el número máximo de hijos permitidos para

un nodo no hoja.

• Threshold T: T es el límite superior del radio de un grupo en un nodo hoja.

• Número de entradas en un nodo hoja L.

23
Figura 15. Ejemplo de Cluster Feature Tree (Imagen tomada de [43])

24
7. Metodología

Para alcanzar los objetivos específicos de esta tesis, dividimos la metodología en cuatro

etapas (ver Figura 16), mismas que se explican a continuación.

Figura 16. Etapas de la metodología

7.1. Entendimiento del problema

En esta etapa se plantearon las áreas de oportunidad existentes en el campo de la

bioinformática. En la selección del área de oportunidad sobresalió el tópico de la clasificación

filogenética de organismos vivos utilizando el enfoque del procesamiento de señales

genómicas. Por lo que para empezar a comprender este tópico se recurrió a documentación

bibliográfica, teniendo como tareas la lectura de publicaciones científicas y libros que

brindaron información sobre la bioinformática y el análisis de secuencias genómicas. Una

vez comprendidos tópicos como los principios de la biología molecular, la estructura genética

de la célula y el análisis de secuencias genómicas mediante herramientas computacionales se

prosiguió al estudio de lo siguiente:

1. Estado del arte sobre los algoritmos de agrupamiento que se utilizan para formar

grupos mediante secuencias genómicas.

2. Estado del arte sobre los algoritmos de clustering jerárquico.

El resultado de este paso de la metodología se puede ver reflejado en la sección anterior.

Una vez leídos ambos tópicos se decidió abordar el problema del agrupamiento utilizando

25
técnicas de clustering jerárquico. Los motivos para elegir esta aproximación fueron que, con

base en el estado del arte, se demostró que se pueden obtener buenos resultados al utilizar

señales genómicas en algoritmos de clustering, y que los algoritmos de clustering jerárquico

crean un árbol jerárquico similar a los utilizados por la filogenética.

7.2. Definición de algoritmos y herramientas

7.2.1. Adquisición de datos

Para la extracción de las secuencias genómicas de los organismos se decidió utilizar

como proveedor de datos al Centro Nacional para la Información Biotecnológica o por sus

siglas en inglés NCBI, una división de la Biblioteca Nacional de Medicina de Estados Unidos

[45]. Se seleccionó la base de datos de Nucleotide que contiene las secuencias genómicas de

diversos organismos vivos proporcionadas por diferentes laboratorios.

7.2.2. Transformación

Con las secuencias de ADN extraídas desde NCBI se llevó a cabo la conversión de

secuencias de bases a secuencias numéricas. Habiendo múltiples maneras de poder realizar

esta conversión, se decidió por utilizar la representación Voss, una de las funciones de mapeo

más populares. Voss emplea cuatro vectores indicadores binarios, cada uno destinado a

denotar la presencia de un nucleótido de cada tipo en una ubicación específica dentro de la

secuencia de ADN [46].

En la Figura 17 se puede ver un ejemplo a detalle de una secuencia de 15 caracteres,

y su conversión a señal genómica utilizando Voss. En dicha figura podemos observar que

tenemos una lista de entrada llamada “Secuencia” cuyos elementos (T, G, A, C) representan

la secuencia de ADN a convertir, y como salida contamos con la lista de listas llamada

“Señal” donde sus elementos son listas nombradas como Gn, An, Cn, Tn, haciendo referencia

26
a las bases que forman el ADN. Dentro de cada una de estas listas se guardan dos elementos

(1 y 0); cuando se almacena el elemento 1 significa la presencia de un base, de lo contrario

se almacena con el elemento 0. Al final las listas se emparejan al ser almacenadas dentro de

la variable “Señal” formando así un vector que mapea nuestra secuencia de ADN.

Figura 17. Ejemplo de transformación de secuencia de ADN a señal genómica usando Voss

7.2.3. Caracterización

Durante nuestra tarea de caracterización se decidió utilizar la transformada rápida de

Fourier, tomando como base el enfoque del procesamiento de señales genómicas. Esta forma

de caracterizar fue seleccionada porque nos genera un patrón común de la señal genómica en

cuestión, reduciendo así la carga de procesamiento para el agrupamiento [47]. Siendo el

principal motivo de utilizar este enfoque, el gran tamaño del vector obtenido durante nuestra

etapa de mapeo ya que éste al ser representado por una lista de listas podría llegar a dificultar

el procesamiento de nuestro algoritmo de clustering.

7.2.4. Clustering

Para llevar a cabo la parte del agrupamiento se investigaron algoritmos de clustering

que pudieran aplicarse a organismos vivos, encontrando entre ellos K-Means [48]. Sin

embargo, dado el objetivo de la tesis, se optó por utilizar BIRCH [49], ya que éste está

diseñado para agrupar grandes cantidades de datos con una alta escalabilidad al integrar

métodos jerárquicos de agrupamiento en la etapa inicial, y puede reajustar el aprendizaje

27
obtenido en los pasos anteriormente realizados [50].

7.3. Implementación

Para realizar nuestros experimentos se optó por desarrollar una herramienta de software,

la cual fue desarrollada considerando características específicas como la portabilidad y la

independencia de módulos en nuestro código.

La herramienta fue implementada incrementalmente al poner objetivos semanales que

cumplieran con las características deseadas. Entre los objetivos planteados se destacan los

siguientes:

● Obtener la secuencia genómica de cualquier organismo vivo de la base de datos de

NCBI.

● Utilizar la transformación numérica Voss para mapear la secuencia genómica

obtenida de NCBI.

● Implementar la transformada rápida de Fourier para obtener las características de la

señal genómica procesada.

● Clasificar las señales genómicas mediante el algoritmo BIRCH.

Al empezar el desarrollo del software se optó por utilizar el lenguaje de programación

Python, ya que éste cuenta con herramientas prácticas y una amplia variedad de librerías que

permiten hacer el trabajo de desarrollo de forma más rápida, a la vez que nos permite

aprovechar las ventajas del paradigma orientado a objetos y la programación funcional. Entre

las librerías que se utilizan está Scikit Learn, que nos permite acceder a una amplia variedad

de herramientas de Machine Learning y estadística, y Biopython para realizar múltiples tareas

relacionadas con las secuencias genómicas. La arquitectura del sistema desarrollado se

28
muestra en la Figura 18.

Figura 18. Arquitectura del sistema implementado para el agrupamiento de señales genómicas

El flujo de trabajo de la herramienta implementada se muestra en la Figura 19 en donde

podemos observar el orden en el que se implementaron los pasos especificados en la sección

7.2.

Figura 19. Flujo del programa

29
 La lógica del programa comienza con el archivo de configuración, en éste se configura

la forma con la cual el programa operará, permitiendo elegir el algoritmo de clustering, la

fecha para realizar las búsquedas, la opción de extraer secuencias genómicas por región o

completas, el número de secuencias de un mismo tipo de virus a ser recuperadas, entre otras.

En el archivo de configuración (ver Figura 20) contamos con dos secciones Default y Query.

En la sección de Default contamos con las siguientes variables:

• mail: Cuenta de correo con la cual nos registramos en NCBI (este paso es necesario

para poder realizar más transacciones en caso de ser necesario, ya que se maneja un

límite por día).

• api_key: Token del usuario dado por NCBI

• init_date: Fecha a partir de la cual se buscará en las bases de datos de NCBI

• db: Base de datos de NCBI a ser utilizada

• function: Función de mapeo a utilizar (Ejemplo: Atomic Number, Voss).

Y para la sección de Query contamos con los siguientes parámetros:

• max_results: Número de secuencias del mismo tipo de organismo que serán

extraídas de la base de datos

• queries: Arreglo con los nombres de los organismos a buscar en NCBI

• combinations: Arreglo con las regiones genómicas que serán extraídas de nuestro

organismo vivo, en caso de querer utilizar la secuencia completa se llena con el

atributo ‘DEFAULT’

30
 Figura 20. Archivo de configuración del programa

La primera parte del programa consiste en hacer una petición al endpoint de NCBI a

través de Biopython, que cuenta con una implementación de Entrez (navegador de NCBI).

Solicitando las secuencias seleccionadas previamente en el archivo de configuración

mediante una petición Http, obteniendo como resultado un objeto que usa setters y getters

que nos permiten la manipulación de los atributos biológicos que nos conciernen. En la Figura

21 se ejemplifica la estructura del objeto Entrez.

Figura 21. Objeto Entrez

31
 Del objeto Entrez extraemos los Ids de los organismos provistos por NCBI, acorde a

nuestra búsqueda, para con estos Ids realizar otra petición con el fin de obtener como

resultado las descripciones completas de cada organismo, siendo esta descripción una

estructura de datos brindada por Biopython. Después, con base en el criterio de la selección

de zonas, se eliminan aquellos resultados que no cumplan con las regiones elegidas, mismas

que fueron especificadas por el usuario en el archivo de configuración.

Como segunda parte las secuencias se guardan en una lista, para posteriormente ser

enviadas a la función de transformación para que sean mapeadas con el fin de representar

numéricamente las secuencias del ADN. Dentro de esta función se entra a un switch case

donde se utiliza la transformación que el usuario desea. Cabe mencionar que se

implementaron más funciones de mapeo como Atomic Number, Tetrahedron, Paired

Numeric, entre otras. Para el caso de esta tesis se decidió utilizar Voss por su buen

funcionamiento en los resultados de los trabajos estudiados en el estado del arte.

En la tercera parte se obtiene un vector resultante por cada una de las secuencias

genómicas, siendo éstas representadas numéricamente, pero al ser muy extensas se necesita

aplicar el proceso de caracterización. Para ello utilizamos la transformada rápida de Fourier,

ya que ésta nos permite sacar el patrón de la señal genómica reduciendo de esta forma los

tiempos de complejidad para nuestro algoritmo de agrupamiento. Para este paso se

implementaron las librerías Spectrum y Numpy (Ver la Figura 22).

32
 Figura 22. Implementación de la transformada rápida de Fourier

Finalmente proseguimos al proceso de clusterización en dónde las secuencias ya

caracterizadas son la entrada para el algoritmo de clustering. En este caso y tomando en

cuenta que en la filogenética se obtiene algo parecido a los árboles jerárquicos para

determinar la similitud entre organismos, se optó por utilizar el algoritmo de BIRCH. Para la

implementación decidimos utilizar Sklearn, librería que nos brinda implementaciones de

algoritmos de machine learning de forma funcional. Para llevar a cabo la clusterización, es

necesario establecer en la variable n_clusters el número de grupos que esperamos formar y

mediante la función fit proporcionada por la clase Birch ingresamos nuestras secuencias

genómicas ya procesadas. La implementación de dicho proceso en el código del programa se

muestra en la Figura 23.

Figura 23. Implementación de la función Birch

33
 Finalmente, como salida obtenemos los resultados del agrupamiento del algoritmo,

mismos que son guardados en la variable labels y son desplegados como se aprecia en la

Figura 24.

Figura 24. Resultados de salida de la función Birch

34
8. Resultados

8.1. Datos de experimentación y validación

Para evaluar el desempeño de BIRCH sobre señales genómicas, se decidió trabajar con

el Virus del Papiloma Humano (HPV, por sus siglas en inglés). Este organismo cuenta con

más de 200 tipos diferentes de virus [51]. Para elegir los tipos de HPV a ser procesados y

validar los grupos generados por el algoritmo de clustering tomamos como base o gold

standard el siguiente árbol filogenético de HPV (Ver Figura 25).

Grupos de colores
A5-A6: HPV alto riesgo A7: HPV alto riesgo A9: HPV alto riesgo
Tipos: 51, 56, 66 Tipos: 18, 39, 45, 59, 68 Tipos: 16, 31, 33, 35, 52, 58

Figura 25. Árbol filogenético del Papiloma Humano (HPV) (Imagen tomada de [52])

35
 La Figura 25 muestra un árbol filogenético para HPV. En las “ramas” se pueden observar

distintos tipos de este virus, y a su vez éstos están divididos en grupos, mismos que fueron

obtenidos de un alineamiento múltiple de secuencias utilizando la sección L2 [52].

Para nuestros experimentos elegimos trabajar únicamente con los grupos marcados en

verde, azul y naranja, A7, A5-A6 y A9 respectivamente, debido a que éstos presentan los

tipos de alto riesgo de HPV [52], mismos que se encuentran marcados en rojo en la Figura

25.

8.2. Diseño de experimentos y resultados obtenidos

Para nuestros experimentos tomamos todos los tipos de HPV de los 3 grupos (A7, A9,

A5-A6) con un total de 20 secuencias de ADN obtenidas de NCBI. Posteriormente las

convertimos a señal genómica, usando Voss y la Transformada Rápida de Fourier, para

alimentar el algoritmo. Los parámetros con los que ejecutamos BIRCH son los siguientes:

• n_clusters : 3 (Dado que este número representa los grupos del gold standar)
• Algoritmo Jerárquico: Aglomerative
• Threshold: 0.5

Prosiguiendo, el algoritmo de clustering nos etiquetará nuestras secuencias con el

número de clúster que le fue asignado y finalmente se muestran los resultados de forma

gráfica utilizando la librería Matplotlib, en donde se decidió tomar como valores

significativos la Norma para el Eje X y la Media para el Eje Y.

Para lograr los objetivos de esta tesis se decidieron realizar diferentes experimentos y a

continuación se describen cada uno de ellos, así como los resultados obtenidos.

36
 • Experimento I- Variantes de HPV de diferentes grupos: Para este experimento,

se decidió tomar un tipo de virus por cada grupo, seleccionando el HPV 16 del grupo A9, el

HPV 18 del grupo A7 y el HPV 51 del grupo A5-A6. Después de seleccionar dichas

muestras, se descargaron del NCBI ocho variantes del tipo de virus elegido por grupo,

haciendo un total de 24 elementos y utilizando como atributo de clusterización su región L2.

En este experimento se buscó experimentar con 8 variantes del mismo virus, ya que cada

virus tenía al menos 8 variantes y con esa cantidad se decidió por hacer un agrupamiento

rápido mediante el algoritmo.

Como podemos observar en la Tabla 1 todas las variantes del HPV 18 fueron agrupadas

en el mismo clúster (1), las del HPV 16 se agruparon juntas en el clúster (0) mientras que las

del tipo 51 se agruparon en el clúster (2). Esto demuestra que podemos agrupar de manera

correcta, de acuerdo con el gold standar, las diferentes variantes de los tipos de virus.

Tabla 1. Resultados de agrupamiento del experimento I – variantes de HPV de diferentes grupos

Tipo Etiqueta Grupo Tipo Etiqueta Grupo Tipo Etiqueta Grupo

18.1 1 A7 16.1 0 A9 51.1 2 A5-A6

18.2 1 A7 16.2 0 A9 51.2 2 A5-A6

18.3 1 A7 16.3 0 A9 51.3 2 A5-A6

18.4 1 A7 16.4 0 A9 51.4 2 A5-A6

18.5 1 A7 16.5 0 A9 51.5 2 A5-A6

18.6 1 A7 16.6 0 A9 51.6 2 A5-A6

18.7 1 A7 16.7 0 A9 51.7 2 A5-A6

18.8 1 A7 16.8 0 A9 51.8 2 A5-A6

37
Figura 26. Ploteo del experimento I – variantes de HPV de diferentes grupos

38
 • Experimento II – Variantes de HPV del grupo A7: Para este experimento, se

decidió tomar tres tipos de virus del grupo A7, seleccionando como muestras el HPV 18, 39

y 45. Después de seleccionar las muestras, se descargaron del NCBI ocho variantes de los

tipos de virus elegidos, haciendo un total de 24 elementos utilizando como atributo de

clasificación su región L2.

Como podemos observar en la Tabla 2 todas las variantes del HPV 18 fueron agrupadas

en el mismo clúster (2), las del HPV 39 se agruparon juntas en el clúster 0 mientras que las

del tipo 45 se agruparon en el clúster (1). Esto demuestra que a pesar de ser del mismo grupo

(A7) los virus muestran diferencias entre ellos y es posible agruparlos con nuestra

metodología. Este mismo comportamiento puede observarse en la Figura 27, en donde se

encuentra un cúmulo de puntos morados, uno de puntos rojos y uno de puntos azules-cyan;

correspondientes a variantes del HPV 39, HPV 18 y HPV 45, respectivamente.

Tabla 2. Resultados de agrupamiento del experimento II – variantes de HPV del grupo A7

Tipo Etiqueta Grupo Tipo Etiqueta Grupo Tipo Etiqueta Grupo

18.1 2 A7 39.1 0 A7 45.1 1 A7

18.2 2 A7 39.2 0 A7 45.2 1 A7

18.3 2 A7 39.3 0 A7 45.3 1 A7

18.4 2 A7 39.4 0 A7 45.4 1 A7

18.5 2 A7 39.5 0 A7 45.5 1 A7

18.6 2 A7 39.6 0 A7 45.6 1 A7

18.7 2 A7 39.7 0 A7 45.7 1 A7

18.8 2 A7 39.8 0 A7 45.8 1 A7

39
Figura 27. Ploteo del experimento II – variantes de HPV del grupo A7

40
 • Experimento III – Variantes de HPV del grupo A9: Para este experimento, se

decidió tomar tres tipos de virus del grupo A9, seleccionando como muestras el HPV 58, 33

y 31. Después de seleccionar las muestras, se descargaron del NCBI ocho variantes de los

tipos de virus elegidos, haciendo un total de 24 elementos utilizando como atributo de

clusterización su región L2.

Como podemos observar en la Tabla 3 todas las variantes del HPV 58 fueron agrupadas en

el mismo clúster (2), las del HPV 33 se agruparon juntas en el clúster (1) mientras que las del

tipo 31 se agruparon en el clúster (0). Similar al experimento anterior, se demuestra que a

pesar de ser del mismo grupo (A9) los virus muestran diferencias entre ellos.

Figura 28. Ploteo del experimento III - Variantes de HPV del grupo A9

41
Tabla 3. Resultados de agrupamiento del experimento III - variantes de HPV del grupo A9

Tipo Etiqueta Grupo Tipo Etiqueta Grupo Tipo Etiqueta Grupo

58.1 2 A9 33.1 1 A9 31.1 0 A9

58.2 2 A9 33.2 1 A9 31.2 0 A9

58.3 2 A9 33.3 1 A9 31.3 0 A9

58.4 2 A9 33.4 1 A9 31.4 0 A9

58.5 2 A9 33.5 1 A9 31.5 0 A9

58.6 2 A9 33.6 1 A9 31.6 0 A9

58.7 2 A9 33.7 1 A9 31.7 0 A9

58.8 2 A9 33.8 1 A9 31.8 0 A9

42
 • Experimento IV – Variantes de HPV del grupo A5-A6: Para este experimento,

se decidió tomar tres tipos de virus del grupo A5-A6, seleccionando como muestras el HPV

30, 53 y 56. Después de seleccionar las muestras, se descargaron del NCBI ocho variantes de

los tipos de virus elegidos, haciendo un total de 24 elementos utilizando como atributo de

clasificación su región L2.

Figura 29. Ploteo del experimento IV – variantes de HPV del grupo A5-A6

Como podemos observar en la Tabla 4 todas las variantes del HPV 53 fueron agrupadas

en el mismo clúster (2), las del HPV 30 se agruparon juntas en el clúster (1) mientras que las

del tipo 56 se agruparon en el clúster (0) al igual que los dos experimentos anteriores, se

demuestra que a pesar de ser del mismo grupo (A5 – A6) es posible agruparlos o

diferenciarlos con nuestra metodología.

43
Tabla 4. Resultados de agrupamiento del experimento IV – variantes de HPV del grupo A5-A6

Tipo Etiqueta Grupo Tipo Etiqueta Grupo Tipo Etiqueta Grupo

53.1 2 A5-A6 30.1 1 A5-A6 56.1 0 A5-A6

53.2 2 A5-A6 30.2 1 A5-A6 56.2 0 A5-A6

53.3 2 A5-A6 30.3 1 A5-A6 56.3 0 A5-A6

53.4 2 A5-A6 30.4 1 A5-A6 56.4 0 A5-A6

53.5 2 A5-A6 30.5 1 A5-A6 56.5 0 A5-A6

53.6 2 A5-A6 30.6 1 A5-A6 56.6 0 A5-A6

53.7 2 A5-A6 30.7 1 A5-A6 56.7 0 A5-A6

53.8 2 A5-A6 30.8 1 A5-A6 56.8 0 A5-A6

44
 • Experimento V – Agrupamiento de HPV de diferentes grupos: Para este

experimento, se decidió tomar todas los tipos de virus de todos los grupos (A7, A9 y A5-A6),

seleccionando como muestras el HPV 51, 67, 70, 33, 16, 59, 69, 52, 58, 35, 31, 68, 18, 66,

53, 56, 26, 30, 39 y 45. Después de seleccionar las muestras, se descargó del NCBI una sola

secuencia por cada tipo de virus elegido, haciendo un total de 20 secuencias utilizando como

atributo de clusterización su región L2.

La Figura 30 muestra la distribución gráfica de los resultados de este experimento. Para

el eje de la X se tomó como parámetro de mapeo estadístico la norma del vector y en el eje

Y la media estadística. Los puntos dentro del ploteo representan las diversas variedades del

HPV que se tomaron, cada una está pintada de un color acorde al resultado obtenido del

agrupamiento. Podemos observar que, a diferencia de los experimentos anteriores, no

parecieran formarse cúmulos cercanos de los virus, ya que a pesar de ser de un mismo grupo,

los puntos se encuentran distantes en los valores numéricos obtenidos por el mapeo

estadístico.

Figura 30. Ploteo del experimento V – agrupamiento de HPV de distintos grupos

45
 En la Tabla 5 podemos apreciar los resultados de clusterización para diferentes tipos de

virus de diferentes grupos, en donde 17 de 20 tipos de virus fueron etiquetados correctamente

con respecto al gold standar, dando una precisión de 85%. Los casos en los que se obtuvieron

diferentes resultados de clasificación a los esperados fueron el HPV 69, 26 y 51 (marcados

con rojo); estos tres tipos fueron agrupados en el clúster 0 (perteneciente al grupo A9) siendo

el clúster 2 la salida esperada, ya que estos virus pertenecen al grupo A5-A6.

Tabla 5. Resultados de agrupamiento del experimento V –HPV de distintos grupos

Tipo Etiqueta Grupo Tipo Etiqueta Grupo Tipo Etiqueta Grupo

69 0 A5-A6 18 1 A7 67 0 A9

26 0 A5-A6 45 1 A7 58 0 A9

51 0 A5-A6 39 1 A7 33 0 A9

30 2 A5-A6 70 1 A7 52 0 A9

53 2 A5-A6 68 1 A7 31 0 A9

56 2 A5-A6 59 1 A7 35 0 A9

66 2 A5-A6 16 0 A9

46
9. Conclusiones

Tomando como base los resultados obtenidos, podemos apreciar que efectivamente el

algoritmo BIRCH realiza un buen acoplamiento de los organismos vivos al utilizar el enfoque

de procesamiento de señales genómicas. Dicha afirmación la podemos validar al observar el

experimento final de este trabajo, en el cual se obtuvo un porcentaje de éxito del 85% en el

agrupamiento generado por el algoritmo con base en el gold standar elegido. Este resultado

a su vez demuestra la efectividad del enfoque del GSP, y que el algoritmo BIRCH es una

buena opción para encontrar similitudes, debido a que éste nos permite implementar

algoritmos jerárquicos para encontrar semejanzas entre los grupos formados, tomando como

referencia diferentes parámetros estadísticos.

Con relación a la implementación de los experimentos, el lenguaje de programación

Python fue de gran ayuda en las diferentes etapas de la metodología. De dicho lenguaje

utilizamos principalmente las librerías de BioPython y Scikit-learn, la primera para obtener

de forma sencilla las secuencias de organismos vivos del NCBI y la última para las etapas de

caracterización y agrupamiento. Todas estas implementaciones y APIs ofrecidas por el

lenguaje nos permitieron avanzar de forma rápida; quizás la desventaja encontrada durante

el desarrollo de la metodología fue la adaptación en el programa de diferentes librerías

hablando en temas del versionamiento, debido a que algunas librerías no eran compatibles.

Como trabajo futuro y hablando primero sobre las mejoras que se le pudieran hacer a la

herramienta, existen casos de uso en los cuales es necesario hacer muchas búsquedas por un

mismo organismo debido a que las regiones del ADN deseado no se encuentran en las

opciones de búsqueda, por lo que aquí se pudiera implementar una búsqueda dinámica hasta

encontrar el resultado deseado. Pasando a temas que conciernen al enfoque de GSP, aquí

47
tenemos un campo amplio para explorar, ya sea utilizando alguna otra forma de mapeo como

Atomic Number o Integer, tomando una función matemática diferente a la Transformada

Rápida de Fourier para caracterizar las señales o simplemente dentro del algoritmo BIRCH

utilizar diferentes medidas en los parámetros para generar el Clustering Feature Tree(CFT) y

probar otros algoritmos de clustering jerárquico sobre el generado CFT. Y finalmente en el

área biológica, se pudiera experimentar con otras regiones genéticas del organismo vivo

(incluso concatenar regiones), ya que en este trabajo probamos únicamente con L2, para ver

si se llegasen a generar buenos resultados de agrupamiento con base al gold standar.

48
Bibliografía

[1] Murphy, K. P. (2012). Machine learning: a probabilistic perspective. MIT press.

[2] Shortliffe, E. H. (2006). Biomedical informatics. J. J. Cimino (Ed.). Springer Science+

Business Media, LLC.

[3] Kuska (1998) Beer, Bethesda, and biology: how “genomics” came into being. J Nat
Cancer Inst 90:93

[4] Selzer, P. M., Marhöfer, R. J., & Rohwer, A. (2008). Applied bioinformatics. An
introduction–Springer, Verlag, Berlin, Heidelberg, Germany, 260.

[5] Tatusov RL, Koonin EV, Lipman DJ (1997) A genomic perspective on protein families.
Science 287: 631 – 637

[6] Recuero, P. (2017). Los 2 tipos de aprendizaje en Machine Learning: supervisado y no

supervisado. Mayo 15, 2020, de LUCA Sitio web: https://data-speaks.luca-
d3.com/2017/11/que-algoritmo-elegir-en-ml-aprendizaje.html

[7] Baikey KD. 1994. Numerical taxonomy and cluster analysis. In: Typologies and
taxonomies: an introduction to classification. USA: SAGE Publications, 34–65.

[8] (2018). CD-HIT. Mayo 15, 2020, de Weizhong Li's Group Sitio web: http://weizhongli-
lab.org/cd-hit/

[9] Edgar RC. 2010. Search and clustering orders of magnitude faster than BLAST.
Bioinfor-matics 26(19):2460–2461

[10] James, B., Luczak, B., &. (2018). MeShClust: an intelligent tool for clustering DNA
sequences. Mayo 15, 2020, de Oxford Academic Sitio web:
https://academic.oup.com/nar/article/46/14/e83/4990634

[11] NCBI. (2009). Genomic Signal Processing. Mayo 15, 2020, de PMC Sitio web:
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2766787/

49
[12] Larry Escobar. (2017). PROCESADORES DIGITALES DE SEÑALES (DSPs) Y
APLICACIONES. Mayo 15, 2020, de UNAM Sitio web: http://odin.fi-
b.unam.mx/labdsp/files/ADSP/apuntes/dsp_apli0_17

[13] Zhao B, Duan V, Yau SS-T. 2011. A novel clustering method via nucleotide-based
Fourier power spectrum analysis. Journal of Theoretical Biology 279(1):83–89

[14] Mendizabal-Ruiz, G., Román-Godínez, I., Torres-Ramos, S., Salido-Ruiz, R. A.,

Vélez-Pérez, H., & Morales, J. A. (2018). Genomic signal processing for DNA
sequence clustering. PeerJ, 6, e4264.

[15] Ramírez-López, V. Román-Godínez, I., Torres-Ramos, S. (2019) Análisis de

representaciones numéricas de secuencias de ADN usando K-means. Universidad de
Guadalajara.

[16] Narita, A., Nagai, M., Mizuno, S., Ogishima, S., Tamiya, G., Ueki, M., ... & Yamanaka,
C. (2020). Clustering by phenotype and genome-wide association study in autism.
Translational psychiatry, 10(1), 1-12.

[17] Eyüpoğlu, C. (2016). Clustering of Mitochondrial D-loop Sequences Using Similarity

Matrix, PCA and K-means Algorithm. International Journal of Intelligent Systems and
Applications in Engineering, 244-248.

[18] Frandsen, P. B., Calcott, B., Mayer, C., & Lanfear, R. (2015). Automatic selection of
partitioning schemes for phylogenetic analyses using iterative k-means clustering of
site rates. BMC evolutionary biology, 15(1), 1-17.

[19] Bustamam, A., Tasman, H., Yuniarti, N., Frisca, & Mursidah, I. (2017, July).
Application of k-means clustering algorithm in grouping the DNA sequences of
hepatitis B virus (HBV). In AIP Conference Proceedings (Vol. 1862, No. 1, p. 030134).
AIP Publishing LLC.

[20] National Human Genome Research Institute, ADN (Ácido Desoxirribonucleico).

Marzo 03, 2021, de NIH Sitio web: https://www.genome.gov/es/genetics-
glossary/ADN-acido-Desoxirribonucleico

50
[21] Magalhães, Lana. ADN: Qué es, definición y estructura (2021). Abril 27, 2021, de Toda
Materia sitio web: https://www.todamateria.com/adn/

[22] Secuenciación del ADN (2021). Abril 31, 2021, de National Human Genome Research
Institute Sitio web: https://www.genome.gov/27563183/secuenciacin-del adn/

[23] National Human Genome Research Institute, Genoma (Ácido Desoxirribonucleico).

Marzo 03, 2021, de NIH Sitio web: https://www.genome.gov/es/genetics-
glossary/Genoma

[24] Shelley Farrar Stoakes, ¿Qué es la Filogenia?. Marzo 14, 2021. Sitio web:
https://www.news-medical.net/life-sciences/What-is-Phylogeny-(Spanish).aspx

[25] Gregory TR. Understanding evolutionary trees. Evolution: Education and Outreach
2008; 1: 121-137.

[26] Simmons MP, Freudenstein JV. Artifacts of coding amino acids and other composite
characters for phylogenetic analysis. Cladistics. 2002; 18: 354– 365.

[27] Procariotas (2013), Marzo 17, 2021. Sitio web Universidad Nacional del Nordeste:
http://www.biologia.edu.ar/bacterias/micro1.htm

[28] Michu E. A short guide to phylogeny reconstruction. Plant soil environ. 2007; 53 (10):
442–446.

[29] Mendoza-Revilla, Javier. (2012). Aportes de la filogenética a la investigación

médica. Revista Medica Herediana, 23(2), 119-127.

[30] Abascal, Federico & Irisarri, Iker & Zardoya, Rafael. (2014). Filogenia y Evolución
Molecular.

[31] Coltell, Óscar, Arregui, María, Fabregat, Antonio, & Portolés, Olga. (2008). La
bioinformática en la práctica médica: Integración de datos biológicos y
clínicos. Revista médica de Chile, 136(5), 645-652

[32] Escobar, C. A. M., Murillo, L. V. R., & Soto, J. F. (2011). Tecnologías bioinformáticas
para el análisis de secuencias de ADN. Scientia et technica, 3(49), 116-121.

51
[33] (2015). Secuenciación del ADN. Marzo 21, 2021, de National Human Genome
Research Institute Sitio web: https://www.genome.gov/27563183/secuenciacin-del-
adn/

[34] National Center for Biotechnology Information. (2002). BLAST topics. Marzo 25,
2021, de National Library of Medicine Sitio web:
https://blast.ncbi.nlm.nih.gov/Blast.cgi?CMD=Web&PAGE_TYPE=BlastDocs&DO
C_TYPE=BlastHelp

[35] Ramírez López Valeria (2019). Análisis de representaciones numéricas de secuencias

de ADN usando K-means. Universidad de Guadalajara

[36] Dougherty E., Huang Y., Seungchan K., Cai X., & Yamaguchi R. (2009).
Genomic Signal Processing. Octubre 5, 2018, de NCBI Sitio
web: https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2766787/

[37] Dougherty E., Shmulevich I., Chen J., & Wang Z. (2005). Genomic signal
processing: perspectives. En Genomic signal processing and Statistics (p.1). USA:
Hindawi Publishing Corporation.

[38] Kwan H., Arniker S. (2009). Numerical representation of DNA sequences. En IEEE
International Conference on Electro/Information Technology (pp. 307–310)

[39] El Naqa, I., & Murphy, M. J. (2015). What is machine learning?. In machine learning
in radiation oncology (pp. 3-11). Springer, Cham.

[40] Soria, E. (2005). Transformada Discreta de Fourier. Marzo 30, 2021, de Universitat de
València Sitio web: https://www.uv.es/soriae/tema_5_pds.pdf

[41] Smith S. (2011). Chapter 12: The Fast Fourier Transform. Octubre 6, 2018,
de California Technical Publishing Sitio web: http://www.dspguide.com/ch12.htm

[42] Cao, S. (2013). Replicate the Fourier transform time-frequency

domains correspondence illustration using TikZ. Ocutubre 6, 2018, de TEX Sitio
web: https://tex.stackexchange.com/questions/127375/replicate-the-fourier-
transform-time frequency-domains-correspondence-illustrati

52
[43] Larose, D. T. (2015). Data mining and predictive analytics. John Wiley & Sons.

[44] Zhang, T., Ramakrishnan, R., & Livny, M. (1997). BIRCH: A new data clustering
algorithm and its applications. Data Mining and Knowledge Discovery, 1(2), 141-182.

[45] National Library of Medicine. (1988). Welcome to NCBI. Mayo 26, 2020, de NIH Sitio
web: https://www.ncbi.nlm.nih.gov

[46] Voss, R. F. (1992). Evolution of long-range fractal correlations and 1/f noise in DNA
base sequences. Physical review letters, 68(25), 3805.

[47] Hoang, T., Yin, C., Zheng, H., Yu, C., He, R. L., & Yau, S. S. T. (2015). A new method
to cluster DNA sequences using Fourier power spectrum. Journal of theoretical

[48] Lloyd, S. (1982). Least squares quantization in PCM. IEEE transactions on information
theory, 28(2), 129-137.

[49] Zhang, T., Ramakrishnan, R., & Livny, M. (1996). BIRCH: an efficient data clustering
method for very large databases. ACM sigmod record, 25(2), 103-114.

[50] Han, J., Pei, J., & Kamber, M. (2011). Data mining: concepts and techniques. Elsevier.

[51] Instituto Nacional del Cáncer. (2019). VPH y el cáncer. Mayo 26, 2020, de NIH Sitio
web:https://www.cancer.gov/espanol/cancer/causas-prevencion/riesgo/germenes-
infecciosos/vph-y-cancer

[52] Los Alamos National Laboratory. Human papillomaviruses: a compilation and analysis
of nucleic acid and amino acid sequences. 1997. Available at: http://hpv-web.lanl.gov

53