Iniciar sesión Crear cuenta # Python - Ayuda! Logaritmo de Levenshtein!

Vista: ## Ayuda! Logaritmo de Levenshtein!

Publicado por Manolo (1 intervención) el 23/10/2016 13:51:52
Hola buenas! Tengo que realizar un trabajo sobre cadenas de adn con el algoritmo de levenshtein y no se como hacerlo. Se trata de buscar tres cadenas (ejemplo de cadena - GTCTGCTTGGCACTGGCCAATTGTGCAGACT) en un texto que se encuentra en un archivo (.txt) formado por muchas lineas como la anterior. Las entradas son las tres cadenas y las salidas son las lineas y las distancias minimas a las que se encuentran en el texto. Os dejo el enunciado para mayor ayuda:

Haz una función, llamada `` dna``, basada en el algoritmo de Levenshtein, que busque dentro de ** cada una de las líneas del fichero anterior ** las siguientes secuencias genéticas y diga a qué línea las ha encontrado con mínima distancia y cuál es esta distancia (si está en varias líneas, que indique la primera línea en la que aparece a distancia mínima).

Os dejo el algoritmo:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
`def lev_distance(first, second):`
`    if len(first) > len(second):`
`        first, second = second, first`
`    if len(second) == 0:`
`        return len(first)`
`    first_length = len(first) + 1`
`    second_length = len(second) + 1`
`    distance_matrix = [ * second_length for x in range(first_length)]`
`    for i in range(first_length):`
`        distance_matrix[i] = i`
`    for j in range(second_length):`
`        distance_matrix[j]=j`
`    for i in xrange(1, first_length):`
`        for j in range(1, second_length):`
`            deletion = distance_matrix[i-1][j] +1`
`            insertion = distance_matrix[i][j-1] +1`
`            substitution = distance_matrix[i-1][j-1]`
`            if first[i-1] != second[j-1]:`
`                substitution += 1`
`                distance_matrix[i][j] = min(insertion,deletion, substitution)`
`    return distance_matrix[first_length-1][second_length-1]`

Gracias. Espero vuestra ayuda Urgentemente.
Valora esta pregunta  0