рекурсия python с сортировкой пузыря

Question

Итак, у меня есть эта проблема, когда я получаю 2 строки букв ACGT, один с буквами, а другой - буквы и тире «-». строка с тире сравнивается с строкой без нее. ячейка для ячейки. и для каждого спаривания у меня есть система подсчета очков. Я написал этот код для системы подсчета очков: например: dna1: -ACA dna2: TACG оценка составляет -1. (поскольку тире по сравнению с буквой (T) дает -2, буква по сравнению с той же буквой дает +1 (от A до A), +1 (от C до C) и не похожие буквы дают (-1), поэтому сумма равна -1.

def get_score(dna1, dna2, match=1, mismatch=-1, gap=-2): 
"""""" 

score = 0 

for index in range(len(dna1)): 
    if dna1[index] is dna2[index]: 
     score += match 
    elif dna1[index] is not dna2[index]: 
     if "-" not in (dna1[index], dna2[index]): 
      score += mismatch 
     else: 
      score += gap 

это работает отлично.

Теперь я должен использовать рекурсию, чтобы дать лучший результат на 2 строки. я получаю 2 строки, они могут быть разных размеров на этот раз. (я не могу измените порядок букв). поэтому я написал этот код, который добавляет «-» столько раз, сколько нужно для более короткой строки, чтобы создать 2 строки одинаковой длины и поместить их в начало списка. Теперь я хочу начать перемещение тире и записывать счет за каждую позицию позиции, а фин союзники получают наивысший балл. поэтому для перемещения тире вокруг я написал litle bubble sort .. но он dosnt, похоже, делает то, что я хочу. Я понимаю его длинный quesiton, но я бы хотел помочь. дайте мне знать, если что-то, что я написал, не понято.

def best_score(dna1, dna2, match=1, mismatch=-1, gap=-2,\ 
         score=[], count=0): 
"""""" 

diff = abs(len(dna1) - len(dna2)) 

if len(dna1) is len(dna2): 
    short = [] 
elif len(dna1) < len(dna2): 
    short = [base for base in iter(dna1)] 
else: 
    short = [base for base in iter(dna2)] 

for i in range(diff): 
    short.insert(count, "-") 

for i in range(diff+count, len(short)-1): 
    if len(dna1) < len(dna2): 
     score.append((get_score(short, dna2),\ 
         ''.join(short), dna2)) 
    else: 
     score.append((get_score(dna1, short),\ 
         dna1, ''.join(short))) 
    short[i+1], short[i] = short[i], short[i+1] 

if count is min(len(dna1), len(dna2)): 
    return score[score.index(max(score))] 
return best_score(dna1, dna2, 1, -1, -2, score, count+1) 

Answer 1

Во-первых, если я правильно deciephered вашу функцию затрат, лучше значение оценки не зависят от разрыва, так как количество черточек фиксирована.

Во-вторых, он линейно зависит от количества несоответствий и поэтому не зависит от точных значений совпадения и несоответствия, если они являются положительными и отрицательными соответственно.

Итак, ваша задача сводится к поиску самой длинной подпоследовательности длиннейших строковых букв, строго соответствующих подпоследовательности букв самого короткого.

В-третьих, определите по M(string, substr) функция returnin длина наилучшего совпадения сверху. Если наименьшая строка Fisrt буква S, то есть substr == 'S<letters>', то

M(string, 'S<letters>') = \ 
    max(1 + M(string[string.index(S):], '<letters>') + # found S 
      M(string[1:], '<letters>')) # letter S not found, placed at 1st place 

последний легко реализовать рекурсивный выражение.

Для пары string, substr обозначающей m=M(string, substr) лучшего результата равен

m * match + (len(substr) - m) * mismatch + (len(string)-len(substr)) * gap 

Несложно, хранения, какое значение было максимально в рекурсивном выражении, чтобы найти то, что точно лучший матч.