La distancia de edición es el método más utilizado para cuantificar la similitud entre dos cadenas. Investigamos el problema de la búsqueda de similitud bajo la distancia de edición. Dada una colección de secuencias, el objetivo de la búsqueda de similitud bajo la distancia de edición es encontrar secuencias en la colección que sean similares a una secuencia de consulta dada, donde la puntuación de similitud se calcula utilizando la distancia de edición. El método canónico para calcular la distancia de edición entre dos cadenas utiliza un enfoque basado en programación dinámica que se ejecuta en tiempo y espacio cuadrático, lo que puede no proporcionar resultados en un tiempo razonable para secuencias grandes. Se aboga por algoritmos paralelos para reducir el tiempo requerido por el cálculo de la distancia de edición. Con este fin, presentamos algoritmos paralelos escalables para apoyar una búsqueda de similitud eficiente bajo la distancia de edición. La eficiencia y escalabilidad de los algoritmos propuestos se demuestra a través de un extenso conjunto de experimentos en conjuntos de datos reales. Además, para abordar el problema de la carga de trabajo desigual entre diferentes unidades de procesamiento, que se debe principalmente a la variación significativa en el tamaño de las secuencias, se discuten y analizan empíricamente diferentes esquemas de distribución de datos. Los resultados experimentales han mostrado que la aceleración lograda por el enfoque híbrido sobre el paralelismo inter-tarea e intra-tarea es de 18 y 13, respectivamente.