Python - Levenshtein SubString mas corto

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.

Hola Wildead, puedes ser mas especifica en tu pregunta? no me queda claro de donde buscas el string mas corto...

Hola, gracias por atenderme.

Voy a intentar ser mas especifico.


El String mas corto se sacaria a partir del minimo de la distancia de levenshtein, es decir.

Supongamos que tenemos la siguiente matriz con valores inventados.

- - A C G T G A T
- 0 0 0 0 0 0 0 0
T 2 3 0 0 2 1 1 1
C 4 5 2 3 2 5 3 2
A 6 5 3 3 2 5 4 4


La distancia minima de levenshtein en este caso seria 2 (que corresponde la ultima fila).
El eje vertical es el Patron, el eje horizontal es el que contiene la linia del texto.
De esta manera si hacemos el minimo de [i-1][j], [i][j-1], [i-1][j-1] donde j son las filas y i son las columnas, podemos volver hacia atras para sacar el string del texto.

En este caso partiendo del minimo que ya he comentado que es el 2 (que equivale a una T en el texto) hariamos el minimo de 3,3,2
como dicho minimo es un 2 y se encuentra en la columna de esa T pues entonces ahora tendremos TT.
Y asi vamos haciendo succesivamente, de esta manera tenemos que hacer ahora elminimo de 0 3 2 como este es 0 cogeremos la G que es a la columna que corresponde dicha letra.

Asi nuestro string mas corto partiendo de la distancia minima es TTG; en mi caso yo habia hecho el minimo de cada una de las filas y debido a que en la misma fila se pueden generar varios valores iguals como se muestra en el ejemplo en la fila de la T hay varios 0 y siempre me coge el de mas a la izquierda de manera que me hace un string de TTC, y eso se debe a que no lo hago a partir de [i-1][j], [i][j-1], [i-1][j-1] .

Mi problema es como programar eso.

Espero haberme explicado mejor gracias por atenderme.