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:
Gracias. Espero vuestra ayuda Urgentemente.
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 = [[0] * second_length for x in range(first_length)]
for i in range(first_length):
distance_matrix[i][0] = i
for j in range(second_length):
distance_matrix[0][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