Un algoritmo de búsqueda rápida más rápido
Autores: Lin, Jie; Adjeroh, Donald; Jiang, Yue
Idioma: Inglés
Editor: MDPI
Año: 2014
Acceso abierto
Artículo científico
2014
Un algoritmo de búsqueda rápida más rápido
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
FQS
Búsqueda rápida
Coincidencia
Práctico
ADN
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 24
Citaciones: Sin citaciones
Presentamos el algoritmo FQS (búsqueda rápida más rápida), una variación mejorada del algoritmo de búsqueda rápida. El algoritmo de búsqueda rápida (QS) de coincidencia exacta de patrones y sus variantes se encuentran entre los algoritmos de coincidencia prácticos más rápidos hoy en día. El algoritmo FQS calcula un valor de desplazamiento estadísticamente esperado, lo que permite desplazamientos máximos y un menor número de comparaciones entre el patrón y el texto. En comparación con las variantes QS de última generación de algoritmos de coincidencia exacta de patrones, el algoritmo FQS propuesto es el más rápido cuando , donde es el tamaño del alfabeto. FQS también tiene un tiempo de ejecución competitivo cuando . Al ejecutarse en tres archivos de texto prácticos, (), Bible () y World192 (), FQS resultó tener el mejor rendimiento en la práctica. Nuestro algoritmo FQS tendrá aplicaciones importantes en el ámbito de la búsqueda de bases de datos genómicas, que involucran bases de datos de secuencias de ADN o ARN con cuatro símbolos o bases de datos de proteínas con .
Descripción
Presentamos el algoritmo FQS (búsqueda rápida más rápida), una variación mejorada del algoritmo de búsqueda rápida. El algoritmo de búsqueda rápida (QS) de coincidencia exacta de patrones y sus variantes se encuentran entre los algoritmos de coincidencia prácticos más rápidos hoy en día. El algoritmo FQS calcula un valor de desplazamiento estadísticamente esperado, lo que permite desplazamientos máximos y un menor número de comparaciones entre el patrón y el texto. En comparación con las variantes QS de última generación de algoritmos de coincidencia exacta de patrones, el algoritmo FQS propuesto es el más rápido cuando , donde es el tamaño del alfabeto. FQS también tiene un tiempo de ejecución competitivo cuando . Al ejecutarse en tres archivos de texto prácticos, (), Bible () y World192 (), FQS resultó tener el mejor rendimiento en la práctica. Nuestro algoritmo FQS tendrá aplicaciones importantes en el ámbito de la búsqueda de bases de datos genómicas, que involucran bases de datos de secuencias de ADN o ARN con cuatro símbolos o bases de datos de proteínas con .