Construcción de una base para el espacio de bubbles de un digrafo

Abstract

En un digrafo, una bubble se define como un par de caminos dirigidos con vértices extremos comunes, pero internamente disjuntos. Aparecen naturalmente en el grafo de ensamblaje generado con el fin de realizar la secuenciación del genoma de una especie, y su estudio posee diversas aplicaciones en este campo de la biología.\\ El conjunto de bubbles en un grafo puede tener, en el peor de los casos, un tamaño exponencial sobre la cantidad de nodos presentes en él, y en el contexto de este trabajo, este número puede variar desde los cientos de miles hasta los miles de millones de nodos, por lo que se hace necesario obtener un modo de representación razonable de ellas.\\ Con ese fin se diseñó un algoritmo que obtiene en tiempo polinomial una base para el espacio de bubbles construida a partir del conjunto de bubbles elementales. Luego se estudió algunas propiedades topológicas del grafo de ensamblaje que permitan diseñar un algoritmo que lleva a cabo esta misma tarea de manera diferente.