Algoritmo para encontrar una subcadena común en N series

Estoy familiarizado con los algoritmos LCS para 2 cadenas. Buscando sugerencias para encontrar subcadenas comunes en 2..N cadenas. Puede haber múltiples subcadenas comunes en cada par. Puede haber diferentes subcadenas comunes en subconjuntos de cadenas.Algoritmo para encontrar una subcadena común en N series

cadenas: (ABCDEFGHIJKL) (DEF) (ABCDEF) (BIJKL) (FGH)

cadenas comunes:

1/2 (DEF) 
1/3 (ABCDEF) 
1/4 (IJKL) 
1/5 (FGH) 
2/3 (DEF)

cadenas más larga comunes:

1/3 (ABCDEF)

cadenas más comunes:

1/2/3 (DEF)

Fuente

2010-03-10 Dwight Kelly

¿Es un problema de competencia de ACM que requiere un algoritmo con cierto rendimiento? – Roman

¿No sería la subcadena 'F' la más común, ya que aparece en cuatro cadenas? – interjay

Sería una buena idea decirnos por qué lo necesita, para que podamos entender dónde podemos comprometernos y dónde no. –

Este sor Esto se hace todo el tiempo en el análisis de secuencias de ADN. Puede encontrar una variedad de algoritmos para ello. Una colección razonable está en la lista here.

Hay también el enfoque de fuerza bruta de la fabricación de tablas de cada subcadena (si está interesado sólo en los cortos): forman un árbol de N-ario (N = 26 para las letras, 256 para ASCII) en cada nivel, y almacenar histogramas de la cuenta en cada nodo. Si podes los nodos poco usados (para mantener los requisitos de memoria razonables), terminas con un algoritmo que encuentra todas las subsecuencias de longitud hasta M en algo como N * M^2 * log (M) para la entrada de longitud N. Si en cambio lo divide en K cadenas separadas, puede construir la estructura de árbol y simplemente leer las respuestas en una sola pasada a través del árbol.

Fuente

2010-03-10 17:15:35

Vine a decir esto, que esto se usa en biología de cómputo todo el tiempo. Sin embargo, la definición de "subcadena/subsecuencia" es a menudo ambigua (sin intencionalmente para los no-algorítmicos) y creo que en este caso, su problema requiere que sean contiguos. – Larry

Los árboles SUfix son la respuesta, a menos que tenga cadenas realmente grandes donde la memoria se convierte en un problema. Espere 10 ~ 30 bytes de uso de memoria por carácter en la cadena para una buena implementación. También hay un par de implementaciones de código abierto que facilitan su trabajo.

Hay otros algoritmos más succes también, pero son más difíciles de implementar (busque "árboles de sufijo comprimidos").

Fuente

2010-03-10 17:31:48 luispedro

Algoritmo para encontrar una subcadena común en N series

Respuesta

Cuestiones relacionadas