Блог

Я новичок в Python, и у меня есть проект, который я просто не могу понять. Требуется использовать рекурсию для поиска самой длинной допустимой последовательности ДНК при задании двух нитей. Мне предоставляется файл под названием dna.txt . Первая строка файла содержит число, которое показывает, сколько пар нитей ДНК будет. Тогда остальные строки являются строками ДНК. Моя задача — просмотреть каждую пару нитей по отдельности и найти самую длинную допустимую последовательность ДНК и записать ее в новый файл под названием dnaresults.txt . Если бы это было сделано с помощью итерации, я вполне уверен, что смог бы с этим справиться. Но проект требует, чтобы я использовал рекурсию для а) поиска допустимых последовательностей ДНК и б) поиска самых длинных пар ДНК. Я понимаю рекурсию на самом базовом уровне (Фибоначчи, скользящая сумма и т.д.), Но я просто не могу понять, как применить ее в этой ситуации.

Например, входной файл будет выглядеть следующим образом:

 3
GAAGCTCG
CCTCGGGA
AAATTT
GGGCCC
CTCTAGGAC
GAGTACCTG
  

и мне необходимо вывести это в новый файл:

 DNA sequence pair 0:
AGC
TCG

DNA sequence pair 1:
No matches found

DNA sequence pair 2:
GGAC
CCTG
  

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

 def main():
    dnaFile = open('dna.txt').readlines()
    numOfPairs = int(dnaFile[0])

    for i in range(0, numOfPairs*2, 2):
        firstStrand = str(dnaFile[i 1])
        secondStrand = str(dnaFile[i 2])
        firstStrand.upper()
        secondStrand.upper()
  

Итак, вот где я сейчас нахожусь. Если бы кто-нибудь мог указать мне правильное направление с помощью рекурсии, это было бы потрясающе. Я действительно просто не понимаю, как я должен использовать рекурсию для сравнения цепей ДНК, сохраняя при этом и возвращая только самую длинную. Заранее спасибо!

Редактировать: Мои извинения. Последовательность ДНК действительна, когда A в одной цепочке соединяется с T в другой (и наоборот), а G в одной цепочке соединяется с C в другой (и наоборот).

 ACTGTC
TGACAG
  

Это допустимая последовательность, потому что каждая пара является A-T или G-C.

 ACTGTC
GCACTA
  

Это не совсем допустимая последовательность, потому что не каждая пара является A-T или G-C. Допустимы только 3-я и 4-я пары (TG и AC).

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

Вот рекурсивное решение:

Сначала функция для проверки допустимых пар:

 def valid_pair(c1, c2):
    pairs = {
      'G': 'C',
      'C': 'G',
      'A': 'T',
      'T': 'A'
    }
    return pairs[c1] == c2
  

Теперь метод рекурсии:

 def compare_strands(s1, s2, count=0, result=["", ""]):
    if not s1 or not s2: # base case
        return count, result
    # If it is not a valid pair
    if not valid_pair(s1[0], s2[0]):
        old_max, old_str = count, result
        new_max, new_str = compare_strands(s1[1:], s2[1:], 0, ["", ""])
        if new_max < old_max:
            new_max = old_max
            new_str = old_str
    else:
        temp_result = []
        temp_result.append(result[0]   s1[0])
        temp_result.append(result[1]   s2[0])
        # result[1]  = s2[0]
        count = count   1
        new_max, new_str = compare_strands(s1[1:], s2[1:], count, temp_result)
    return new_max, new_str
  

Тестирование:

 with open('dna.txt', 'r') as f:
    size = int(f.readline())
    for i in range(size):
        strand1 = f.readline().strip('n')
        strand2 = f.readline().strip('n')
        print(compare_strands(strand1, strand2))
  

Вывод:

 (3, ['AGC', 'TCG'])
(0, ['', ''])
(4, ['GGAC', 'CCTG'])
  

Редактировать: Для записи в файл.

 with open('dna.txt', 'r') as f:
    size = int(f.readline())
    for i in range(size):
        strand1 = f.readline().strip('n')
        strand2 = f.readline().strip('n')
        result = compare_strands(strand1, strand2)
        with open('result.txt', 'a') as result_file:
            result_file.write('DNA sequece pair {}:n'.format(i))
            if result[0]:
                result_file.write('{}n{}nn'.format(result[1][0], result[1][1]))
            else:
                result_file.write('No matches foundnn')