Detección directa de superburbujas
Autores: Gärtner, Fabian; Stadler, Peter F.
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Detección directa de superburbujas
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Superburbujas
Dígrafos
Algoritmos
Tiempo lineal
Enumeración
Búsqueda en profundidad
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 41
Citaciones: Sin citaciones
Las superburbujas son una clase de subgrafos inducidos en digrafos que juegan un papel esencial en los algoritmos de ensamblaje para datos de secuenciación de alto rendimiento. Están conectados con el resto del digrafo anfitrión por una única entrada y un único vértice de salida. Los algoritmos de tiempo lineal para la enumeración de superburbujas recientemente han estado disponibles. Los enfoques actuales requieren la descomposición del digrafo de entrada en componentes fuertemente conectadas, que luego se analizan por separado. En principio, se podría utilizar una sola búsqueda en profundidad, siempre y cuando se pueda garantizar que la raíz del árbol de búsqueda en profundidad (DFS) no se encuentre en el interior o en el punto de salida de una superburbuja. Aquí, describimos un algoritmo de tiempo lineal para determinar raíces adecuadas para un bosque DFS que garantiza identificar correctamente las superburbujas en un digrafo. Además de las ventajas de una implementación más sencilla, observamos un aumento de casi tres veces en el rendimiento en conjuntos de datos del mundo real. Presentamos una implementación de referencia del nuevo algoritmo que acepta muchos formatos de entrada comúnmente utilizados para digrafos. Está disponible como código abierto en github.
Descripción
Las superburbujas son una clase de subgrafos inducidos en digrafos que juegan un papel esencial en los algoritmos de ensamblaje para datos de secuenciación de alto rendimiento. Están conectados con el resto del digrafo anfitrión por una única entrada y un único vértice de salida. Los algoritmos de tiempo lineal para la enumeración de superburbujas recientemente han estado disponibles. Los enfoques actuales requieren la descomposición del digrafo de entrada en componentes fuertemente conectadas, que luego se analizan por separado. En principio, se podría utilizar una sola búsqueda en profundidad, siempre y cuando se pueda garantizar que la raíz del árbol de búsqueda en profundidad (DFS) no se encuentre en el interior o en el punto de salida de una superburbuja. Aquí, describimos un algoritmo de tiempo lineal para determinar raíces adecuadas para un bosque DFS que garantiza identificar correctamente las superburbujas en un digrafo. Además de las ventajas de una implementación más sencilla, observamos un aumento de casi tres veces en el rendimiento en conjuntos de datos del mundo real. Presentamos una implementación de referencia del nuevo algoritmo que acepta muchos formatos de entrada comúnmente utilizados para digrafos. Está disponible como código abierto en github.