Algoritmo eficiente para buscar subcadenas coincidentes de más de 14 caracteres de un texto dentro de otro texto

Tengo un texto largo (aproximadamente 5 MB de tamaño de archivo) y otro texto llamado patrón (alrededor de 2000 caracteres).Algoritmo eficiente para buscar subcadenas coincidentes de más de 14 caracteres de un texto dentro de otro texto

La tarea es encontrar piezas coincidentes de un patrón genómico que tengan 15 caracteres o más en el texto largo.

ejemplo:

largo del texto: ACGTACGTGTCA AAAACCCCGGGGTTTTA GTACCCGTAGGCGTAT Y mucho más tiempo

patrón: ACGGTATTGAC AAAACCCCGGGGTTTTA TGTTCCCAG

Estoy mirada para un algoritmo eficiente (y fácil de entender e implementar).

Una bonificación sería una forma de implementar esto con solo arreglos de caracteres en C++ si eso es posible.

Fuente

2012-05-08 Hedge

otros personajes permite intervenir? Esta es la diferencia entre las subsecuencias comunes ("ABC" y "ADC" comparten "AC") y las subpáginas comunes ("ABC" y "ADC" comparten solo las subpáginas de un carácter "A" y "B"). –

http://en.wikipedia.org/wiki/Longest_common_subsequence_problem –

@JasonZhu Este no es exactamente el caso, quiere todas las subsecuencias comunes más largas que 15 caracteres, no solo la más larga. – Imp

Stand back, Voy a vivir-código:

void match_substring(const char *a, const char *b, int n) // n=15 in your case 
{ 
    int alen = strlen(a); // I'll leave all the null-checking and buffer-overrun business as an exercise to the reader 
    int blen = strlen(b); 
    for (int i=0; i<alen; i++) { 
     for (int j=0; j<blen; j++) { 
      for (int k; (i+k<alen) && (j+k<blen) && a[i+k]==b[i+k]; k++); 
      if (k >= n) 
       printf("match from (%d:%d) for %d bytes\n", i, j, k); 
     } 
    } 
}

Fuente

2012-05-08 01:17:04

que se llama búsqueda Naïve string, fui con él. Una mejora fácil de implementar sería el algoritmo Knuth-Morris-Pratt. – Hedge

Si está utilizando una buena implementación de la biblioteca C (o incluso una mediocre como glibc que tiene una buena implementación de esta función), strstr le irá muy bien. He oído que hay un nuevo algoritmo que es especialmente bueno para el ADN (alfabeto pequeño), pero no puedo encontrar la referencia en este momento. Aparte de eso, 2way (que usa glibc) es óptimo.

Fuente

2012-05-08 01:15:39

¡No creo que sea seguro para subprocesos! –

Por supuesto, es seguro para subprocesos. No modifica nada. O más formalmente, todas las funciones no documentadas específicamente como no seguras para subprocesos son seguras para subprocesos. –

¿Está proponiendo que el OP use 'strstr()' en cada subsecuencia de 15 caracteres del patrón de 2000 caracteres? – caf

Una forma sería la de hacerse con una implementación de Aho-Corasick y utilizarlo para crear algo que reconocerá cualquiera de los trozos de 15 caracteres en el patrón, y luego usar esto para buscar el texto. Con Aho-Corasick, el costo para construir el emparejador y el costo de búsqueda son ambos lineales, por lo que esto debería ser práctico.

Fuente

2012-05-08 04:12:53 mcdowella

Aquí hay un algoritmo: no estoy seguro de si tiene un nombre. Requiere un hash "rolling", una función hash (no criptográfica) que tiene la propiedad de que, dado el hash de una secuencia AB...C, es eficiente calcular el hash de la secuencia B...CD.

calcular el hash de rodadura de las secuencias pattern[0..14], pattern[1..15], pattern[2..16] ... y almacenar cada índice en pattern en una tabla hash.
Coseche el hash rodante de haystack[0..14] y vea si está en la tabla hash. Si es así, compare haystack[0..14] con pattern[pos..pos+14] donde pos se recuperó de la tabla hash.
Desde el hash de rodadura de haystack[0..14], calcular de manera eficiente el hash de rodadura de haystack[1..15] y ver si está en la tabla hash. Repita hasta llegar al final de haystack.

Nota que sus 15 cadenas de caracteres sólo tienen 2 valores posibles para que su "función hash" podría haber una asignación simple al valor de la cadena tratada como una base-4 número de 15 dígitos, que es rápido para calcular, tiene la propiedad hash rodante y es único.

Fuente

2012-05-08 04:34:55 caf

No estoy seguro, pero sospecho que tendrá toneladas de colisiones en el caso del ADN. E incluso si solo comparas los hash, no la comparación completa (sin colisión), sigue siendo el mismo big-O en el tiempo que mi algoritmo. Sin embargo, tiene una mejor localidad de caché. –

@R .: Si dimensiona su tabla hash para obtener 'amortizaciones' O (1) ', esto debería ser' O (m + n) '- ¿no es suyo' O (mn) '? – caf

Para cada desplazamiento en el pajar ('n'), necesita verificar su hash contra no solo uno, sino todos los desplazamientos posibles en el patrón (' m'). Es decir, se compara con 'm' diferentes hashes precalculados. Eso hace que el algoritmo sea 'O (nm)'. –

Sugeriría ir a su biblioteca y ver "Algorithms 4th Edition" de Robert Sedgwick y Kevin Wayne. Tienen un capítulo completo dedicado a la búsqueda de subcadenas. Además, probablemente valga la pena visitar el sitio web del libro algs4.cs.princeton.edu.

TL; DR - Si está decidido, puede realizar una búsqueda de subcadenas utilizando matrices de caracteres en tiempo garantizado, de forma lineal a la longitud de entrada. Hay muestras de código en el libro y en línea. No es mucho más fácil que eso.

Fuente

2012-05-08 04:44:35 themaestro

-1

Creo que el "árbol de sufijos" puede resolver con una mejor preformance de O (log n)

Fuente

2012-05-11 05:16:03 kaitian521

Algoritmo eficiente para buscar subcadenas coincidentes de más de 14 caracteres de un texto dentro de otro texto

Respuesta

Cuestiones relacionadas