logo móvil
Contáctanos

Detección directa de superburbujas

Autores: Gärtner, Fabian; Stadler, Peter F.

Idioma: Inglés

Editor: MDPI

Año: 2019

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro