¿Cómo sacar SubString de Levenshtein ?
He recibido una tarea para realizar en python que trata sobre Levenshtein.
En este caso se me presenta un fichero de texto con un montón de Línias de bases de ADN
ATCG de un cromosoma. En dicho texto he de encontrar de cada una de las 10 primeras línias (solo las 10 primeras) La distancia mínima de Levenshtein dado un patrón de cadena de ADN y a continuación el String más parecido de dicho patrón de ADN.
En lo que llevo trabajando en esto he conseguido leer el fichero y que me busque la distancia minimia de las 10 primeras líneas. El problema surge a la hora de sacar el String más corto de cada línea, he estado practicando y haciendo cosas, por ejemplo he buscado el mínimo de cada una de las filas de la matriz para sacar el String pero debido a que en la matriz se crean varios valores en la misma fila con el mismo valor, me coge siempre el más pequeño que encuentra empezando por la izquierda, por lo que en vez de estar haciendo el mínimo de [i-1][j], [i][j-1], [i-1][j-1] estoy cogiendo otra letra.
La idea es que a partir del mínimo de la ultima línea consigas sacar el String más corto, hacer el levenshtein pero a la inversa para sacar el String.
Para facilitar las cosas voy a implementar unas imágenes donde se ejemplifica que es lo que me esta pasando y que es lo que se espera conseguir.
Este es un ejemplo (inventado) de que es lo que debería de hacer
Esta es una muestra de lo que he hecho y por conseguiente del error que he realizado
Como podéis observar en mi caso me coge el primer 2 en vez de coger verdaderamente el dos que debería de coger
Aunque la página me ha adjudicado la "experteduría" en python porque alguna vez he contestado a preguntas que no eran propiamente de python pero que se habían asignado a esa "etiqueta", no tengo ni idea de python como ya he dicho alguna vez. No obstante imagino que lo que quieres resolver se podrá hacer en otros lenguajes o con otras herramientas. Pero el problema, en mi caso, es que no consigo entender lo que pretendes. No tengo tampoco ni idea de genética pero supongo que el problema se puede plantear "en abstracto" sin relacionarlo forzosamente con el ADN. Hablas de las bases ATCG de los cromosomas y de 10 líneas, pero en las imágenes que incluyes no se ven 10 líneas ni las cabeceras de filas ni columnas parecen hacer referencia a esas bases.
Ya te anticipo que probablemente no pueda hacer nada por ti pero si consiguiera entender lo que quieres a lo mejor podía intentarlo. Pero tal vez no merezca la pena el esfuerzo si consideras que es difícil explicarlo con sencillez.
Perdona si te hago perder el tiempo con tan pocas posibilidades de poder echarte una mano.
He estado mirando algo sobre la distancia de Levenshtein aquí https://es.wikipedia.org/wiki/Distancia_de_Levenshtein#Python https://es.wikipedia.org/wiki/Distancia_de_Levenshtein#Python
A lo mejor esto te sirve de algo más que lo que te decía antes.
Si entiendo, la dificultat de entender dicho contexto.
Intentaré explicarme mejor.
Yo he recibo un fichero de texto en el que se encuentran muchas líneas con diferentes bases.
Ejemplo de las primeras 10 Líneas:
atactgcatgtcttcgtcgaca
tctgcggaagatcgcaacaa
tttcctactcaaagcgaccgta
cgataaaaagcctgaccagc
ttcgtacttggtgactctgtta
agctaattacagtgcgggta
ccaaatctttccaagacacac
gggggtagggttgaacttgc
ctagatgtacgactgaagga
ccgggcaatctaacagtacc
De cada una de las líneas Sacamos la distancia de levenshtein:
Si leíste levenshtein es el número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra.
En este caso a mi me dan este patrón por ejemplo: actcagggtacatg
A partir del código el cual ya viste en las webs que me pasaste se puede obtener dicha información.
De esta manera se genera una matriz m*n donde m(filas) es el patrón y n(numero de columnas) es cada línea.
Según el tipo de cambio que haya que generar en dicho texto respecto el patrón se asignan diferentes valores según si se trata de una inserción, una substitución o una eliminación.
Para poder generar la matriz saca el mínimo de [i-1][j], [i][j-1], [i-1][j-1].
Como cada valor es diferente en inserción, eliminación, substitución a partir del mínimo de esos se genera un nuevo numero en la matriz compranando las letras.
De esta manera si hacemos el mínimo de la ultima fila podemos saber la distancia mínima(el mínimo de cambios que se han tenido que realizar para poder llegar a dicho patrón en el texto)
Si nosotros hacemos el paso al a inversa, es decir a partir del mínimo de la ultima fila hacer el mínimo de [i-1][j], [i][j-1], [i-1][j-1]. (Donde j es la fila) (i es la columna) podrimos sacar el string más corto, es decir, supongamos que tenemos lo siguiente (complemtante inventado con valores erronios)
A T C C (linia) eje i
G 2 3 5 4
A 1 5 0 3
GA = patron (eje j)
Como puedes ver el mínimo es 0 (ultima fila) y habría que hacer el mínimo de 5 3 5 para saber a que letra corresponde para que sea el string más corto, en este caso es 3.
De esta manera vamos construyendo el String en este caso seria TC
El problema con el que me encuentro es ese, el hacer el código para sacar dicho String.
Yo lo que he intentado es sacar el mínimo de cada una de las filas para poder sacar el String, pero debido a que varios valores iguales se pueden generar en la misma fila, el mínimo que me coge es siempre el situado más a la izquierda, cogiendo la letra erronia.
EJemplo:
A T C C (línea) eje i
G 2 2 2 4
A 1 5 3 0
GA = patron (eje j)
En este caso me cogería el 0 de la ultima fila que equilvae a C y el 2 de la primera columna.
Entonces me queda AC en vez de CC que seria el string más corto.
Espero haberme explicado correctamente ahora. Se que no entiendes en si de python, pero en otros lenguajes a lo mejor puede ser algo parecido...
Gracias por tu atención.
Como parece que no hay otros candidatos a tratar el asunto, voy a seguir intentando entenderlo. Si decides "cortar" porque estimas que al final no va a servir de nada lo entenderé perfectamente.
Me pones un ejemplo de las primeras diez líneas de un archivo de texto, de un número variable de caracteres (aunque no parecen muy superiores a 20 por línea) todos ellos elegidos entre 4 posibles (a, t, c, g). Para cada una de estas líneas calculamos la distancia de Levenshtein (DL) respecto a otra línea "patrón" de 14 caracteres. De esta forma asociaríamos a cada una de las 10 líneas un número que sería la DL que el corresponde.
Dices "De esta manera se genera una matriz m*n donde m(filas) es el patrón y n(numero de columnas) es cada línea." No entiendo. El patrón tiene 14 letras, ¿quiere eso decir que m = 14? ¿Y n = 10 en este caso? ¿Dónde se escriben, en esa matriz, las DL de cada línea?
Aprovechando el código en java que proporciona el enlace de wiki he calculado las DL para tus diez líneas de ejemplo y tu patrón y esto es lo que me ha dado:
Cadena DL ---------------------- -- Atactgcatgtcttcgtcgaca 12 Tctgcggaagatcgcaacaa 12 Tttcctactcaaagcgaccgta 13 Cgataaaaagcctgaccagc 13 Ttcgtacttggtgactctgtta 12 Agctaattacagtgcgggta 12 Ccaaatctttccaagacacac 13 Gggggtagggttgaacttgc 11 Ctagatgtacgactgaagga 11 Ccgggcaatctaacagtacc 12 Actcagggtacatg 0
He incluido la cadena patrón como comprobación de la "bondad" del algoritmo.
