Помоги составить алгоритм восстановления максимально похожей строки(с инделями) в моем…
- User
Помоги составить алгоритм восстановления максимально похожей строки(с инделями) в моем случае, : def my_max(arr): rule=["ccc","c--","-c-","--c","cc-","c-c","-cc"] c_r=rule[0] m=arr[0] for i,e in enumerate(arr): if e>m: m=e c_r=rule[i] return m,c_r
def LCSbackTrack(v,w,z): s=[[[0 for i in range(len(z)+1)] for i in range(len(w)+1) ] for i in range(len(v)+1)] b_t=[[[0 for i in range(len(z)+1)] for i in range(len(w)+1) ] for i in range(len(v)+1)] for i in range(1,len(v)+1): for j in range(1,len(w)+1): for k in range(1,(len(z)+1)): ma=0 if v[i-1]==w[j-1] and w[j-1]==z[k-1]: ma=1 s[i][j][k],b_t[i][j][k]=my_max([ s[i-1][j-1][k-1]+ma, s[i-1][j][k], s[i][j-1][k], s[i][j][k-1], s[i-1][j-1][k], s[i-1][j][k-1], s[i][j-1][k-1] ]) return s[i][j][k], b_t
def outputLCS(b_t, v, w, z, i, j, k, res=["","",""]): if i==0 or j==0 or k==0: return res if b_t[i][j][k]=="ccc": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+=z[k-1] outputLCS(b_t,v,w,z,i-1,j-1,k-1,res) elif b_t[i][j][k]=="c--": res[0]+=v[i-1] res[1]+='-' res[2]+='-' outputLCS(b_t,v,w,z,i-1,j,k,res) elif b_t[i][j][k]=="-c-": res[0]+='-' res[1]+=w[j-1] res[2]+='-' outputLCS(b_t,v,w,z,i,j-1,k,res) elif b_t[i][j][k]=="--c": res[0]+='-' res[1]+='-' res[2]+=z[k-1] outputLCS(b_t,v,w,z,i,j,k-1,res) elif b_t[i][j][k]=="cc-": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+='-' outputLCS(b_t,v,w,z,i-1,j-1,k,res) elif b_t[i][j][k]=="c-c": res[0]+=v[i-1] res[1]+='-' res[2]+=z[k-1] outputLCS(b_t,v,w,z,i-1,j,k-1,res) elif b_t[i][j][k]=="-cc": res[0]+='-' res[1]+=w[j-1] res[2]+=z[k-1] outputLCS(b_t,v,w,z,i,j-1,k-1,res)
s1="ATATCCG" s2="TCCGA" s3="ATGTACTG" res=LCSbackTrack(s1,s2,s3) r=outputLCS(res[1],s1,s2,s3,len(s1),len(s2),len(s3)) print(r)
- Assistant
Алгоритм восстановления максимально похожей строки с инделами в данном случае выглядит следующим образом:
-
Определение функции my_max(arr), которая принимает на вход массив arr и возвращает максимальное значение элемента и соответствующее правило из заданного набора правил rule. В данном случае используется правило "ccc" для первого элемента массива arr.
-
Определение функции LCSbackTrack(v, w, z), которая принимает на вход три последовательности v, w, z и возвращает матрицу s и матрицу b_t. Матрица s хранит значения максимальной похожести строки между всеми возможными подстроками последовательностей v, w и z. Матрица b_t хранит информацию о том, каким правилом было получено максимальное значение в матрице s.
-
Внутри функции LCSbackTrack используется вложенный цикл для перебора всех возможных комбинаций элементов из последовательностей v, w и z. Для каждой комбинации вычисляется значение ma, равное 1, если все элементы равны между собой, иначе ma равно 0. Затем с помощью функции my_max выбирается максимальное значение из следующих вариантов:
- значение в матрице s с индексами (i-1, j-1, k-1) и прибавленное значение ma
- значение в матрице s с индексами (i-1, j, k)
- значение в матрице s с индексами (i, j-1, k)
- значение в матрице s с индексами (i, j, k-1)
- значение в матрице s с индексами (i-1, j-1, k)
- значение в матрице s с индексами (i-1, j, k-1)
- значение в матрице s с индексами (i, j-1, k-1)
-
Функция LCSbackTrack возвращает значение s[i][j][k] и матрицу b_t.
-
Определение функции outputLCS(b_t, v, w, z, i, j, k, res=["","",""]), которая принимает на вход матрицу b_t, последовательности v, w, z и текущие индексы i, j, k, а также список res, содержащий текущее состояние восстановленной максимально похожей строки. Функция рекурсивно вызывает саму себя, пока не достигнет одного из базовых случаев: i=0, j=0 или k=0. В каждом рекурсивном вызове функция проверяет значение b_t[i][j][k] и соответствующим образом обновляет элементы списка res.
-
Функция outputLCS возвращает список res.
-
Исходные строки s1, s2 и s3 задаются значениями "ATATCCG", "TCCGA" и "ATGTACTG" соответственно.
-
Вызывается функция LCSbackTrack с аргументами s1, s2 и s3. Результат сохраняется в переменной res.
-
Вызывается функция outputLCS с аргументами res[1], s1, s2, s3, len(s1), len(s2), len(s3) и пустым списком res.
-
Результат выводится на экран с помощью функции print().
-
- User
почини мне функцию outputLCS
- Assistant
Исправленный код функции outputLCS:
def outputLCS(b_t, v, w, z, i, j, k, res=["","",""]): if i==0 or j==0 or k==0: return res if b_t[i][j][k]=="ccc": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i-1,j-1,k-1,res) elif b_t[i][j][k]=="c--": res[0]+=v[i-1] res[1]+='-' res[2]+='-' return outputLCS(b_t,v,w,z,i-1,j,k,res) elif b_t[i][j][k]=="-c-": res[0]+='-' res[1]+=w[j-1] res[2]+='-' return outputLCS(b_t,v,w,z,i,j-1,k,res) elif b_t[i][j][k]=="--c": res[0]+='-' res[1]+='-' res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i,j,k-1,res) elif b_t[i][j][k]=="cc-": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+='-' return outputLCS(b_t,v,w,z,i-1,j-1,k,res) elif b_t[i][j][k]=="c-c": res[0]+=v[i-1] res[1]+='-' res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i-1,j,k-1,res) elif b_t[i][j][k]=="-cc": res[0]+='-' res[1]+=w[j-1] res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i,j-1,k-1,res)В каждом условном блоке добавлена команда
return, чтобы корректно возвращать результат рекурсивного вызова функцииoutputLCS. Таким образом, результат рекурсивного вызова передается дальше по цепочке рекурсии и на каждом уровне мы получаем актуальное значение спискаres. - User
def my_max(arr): rule=["ccc","c--","-c-","--c","cc-","c-c","-cc"] c_r=rule[0] m=arr[0] for i,e in enumerate(arr): if e>m: m=e c_r=rule[i] return m,c_r
def LCSbackTrack(v,w,z): s=[[[0 for i in range(len(z)+1)] for i in range(len(w)+1) ] for i in range(len(v)+1)] b_t=[[[0 for i in range(len(z)+1)] for i in range(len(w)+1) ] for i in range(len(v)+1)] for i in range(1,len(v)+1): for j in range(1,len(w)+1): for k in range(1,(len(z)+1)): ma=0 if v[i-1]==w[j-1] and w[j-1]==z[k-1]: ma=1 s[i][j][k],b_t[i][j][k]=my_max([ s[i-1][j-1][k-1]+ma, s[i-1][j][k], s[i][j-1][k], s[i][j][k-1], s[i-1][j-1][k], s[i-1][j][k-1], s[i][j-1][k-1] ]) return s[i][j][k], b_t
def outputLCS(b_t, v, w, z, i, j, k, res=["","",""]): if i==0 or j==0 or k==0: return res if b_t[i][j][k]=="ccc": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i-1,j-1,k-1,res) elif b_t[i][j][k]=="c--": res[0]+=v[i-1] res[1]+='-' res[2]+='-' return outputLCS(b_t,v,w,z,i-1,j,k,res) elif b_t[i][j][k]=="-c-": res[0]+='-' res[1]+=w[j-1] res[2]+='-' return outputLCS(b_t,v,w,z,i,j-1,k,res) elif b_t[i][j][k]=="--c": res[0]+='-' res[1]+='-' res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i,j,k-1,res) elif b_t[i][j][k]=="cc-": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+='-' return outputLCS(b_t,v,w,z,i-1,j-1,k,res) elif b_t[i][j][k]=="c-c": res[0]+=v[i-1] res[1]+='-' res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i-1,j,k-1,res) elif b_t[i][j][k]=="-cc": res[0]+='-' res[1]+=w[j-1] res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i,j-1,k-1,res)
s1="ATATCCG" s2="TCCGA" s3="ATGTACTG" res=LCSbackTrack(s1,s2,s3) r=outputLCS(res[1],s1,s2,s3,len(s1),len(s2),len(s3)) print(r)
Почему этот код выводит не ["A-TAT---CC--G-", "--T-----C-C-GA", "-AT--GTAC--TG-"], а ['-GCCTA-T', 'AGCC---T', '-GTC--AT']
- Assistant
Проблема в данном коде состоит в том, что в рекурсивном вызове функции
outputLCSотсутствует инструкцияreturn. Из-за этого результат рекурсивного вызова не возвращается на каждом уровне рекурсии, и в итоге выводится только часть результата.Чтобы исправить эту проблему, вам нужно добавить инструкцию
returnперед каждым рекурсивным вызовом функцииoutputLCS. Таким образом, результат будет корректно возвращаться на каждом уровне рекурсии и сохраняться при повторных вызовах функции.Вот исправленный код функции
outputLCS:def outputLCS(b_t, v, w, z, i, j, k, res=["","",""]): if i==0 or j==0 or k==0: return res if b_t[i][j][k]=="ccc": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i-1,j-1,k-1,res) elif b_t[i][j][k]=="c--": res[0]+=v[i-1] res[1]+='-' res[2]+='-' return outputLCS(b_t,v,w,z,i-1,j,k,res) elif b_t[i][j][k]=="-c-": res[0]+='-' res[1]+=w[j-1] res[2]+='-' return outputLCS(b_t,v,w,z,i,j-1,k,res) elif b_t[i][j][k]=="--c": res[0]+='-' res[1]+='-' res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i,j,k-1,res) elif b_t[i][j][k]=="cc-": res[0]+=v[i-1] res[1]+=w[j-1] res[2]+='-' return outputLCS(b_t,v,w,z,i-1,j-1,k,res) elif b_t[i][j][k]=="c-c": res[0]+=v[i-1] res[1]+='-' res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i-1,j,k-1,res) elif b_t[i][j][k]=="-cc": res[0]+='-' res[1]+=w[j-1] res[2]+=z[k-1] return outputLCS(b_t,v,w,z,i,j-1,k-1,res)Теперь после каждого рекурсивного вызова добавляется инструкция
return, чтобы результат рекурсивного вызова возвращался на каждом уровне рекурсии. - User
всё равно вывод не такой
- Assistant
Приношу извинения за предыдущую ошибку. Проблема в коде возникает из-за неправильного обновления списка
resвнутри каждого условия. Списокresдолжен передаваться в каждый рекурсивный вызов функцииoutputLCS, чтобы на каждом уров
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.