如何使用递归找到最长的有效 DNA 序列？

Question

我是 Python 新手，我有一个我无法理解的项目。当给定两条链时，它需要使用递归来找到最长的有效 DNA 序列。我得到了一个名为 dna.txt 的文件。文件的第一行包含一个数字，表示将有多少对 DNA 链。然后其余的线是DNA串。我的工作是单独查看每对链，找到最长的有效 DNA 序列，并将其写入一个名为 dnaresults.txt 的新文件中。如果这要通过迭代来完成，我相当有信心我可以处理它。但是该项目要求我使用递归来 a) 找到有效的 DNA 序列并 b) 找到最长的 DNA 对。我在非常基本的层面上理解递归（斐波那契，滚动和等），但我无法理解如何在这种情况下应用它。

例如，输入文件如下所示：

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()

这就是我现在所处的位置。如果有人能通过递归为我指明正确的方向，那将是惊人的。对于我应该如何使用递归来比较 DNA 链，同时只存储和返回最长的链，我真的一无所知。提前致谢！

编辑：我很抱歉。当一条链上的 A 与另一条链上的 T 配对（反之亦然）并且一条链上的 G 与另一条链上的 C 配对（反之亦然）时，DNA 序列是有效的。

ACTGTC

TGACAG

这是一个有效的序列，因为每一对都是 AT 或 GC。

ACTGTC

GCACTA

这不是一个完全有效的序列，因为不是每一对都是 AT 或 GC。只有第 3 对和第 4 对有效（TG 和 AC）。

Answer 1

此类问题的递归使用大量堆栈，并且比使用需要线性时间和恒定空间的内置数据结构慢得多。我知道需要递归，因为那是你的问题，但我仍然觉得我应该这么说。这是一个递归解决方案：首先是一个检查有效对的函数：def valid_pair(c1, c2):&nbsp; &nbsp; pairs = {&nbsp; &nbsp; &nbsp; 'G': 'C',&nbsp; &nbsp; &nbsp; 'C': 'G',&nbsp; &nbsp; &nbsp; 'A': 'T',&nbsp; &nbsp; &nbsp; 'T': 'A'&nbsp; &nbsp; }&nbsp; &nbsp; return pairs[c1] == c2现在递归方法：def compare_strands(s1, s2, count=0, result=["", ""]):&nbsp; &nbsp; if not s1 or not s2: # base case&nbsp; &nbsp; &nbsp; &nbsp; return count, result&nbsp; &nbsp; # If it is not a valid pair&nbsp; &nbsp; if not valid_pair(s1[0], s2[0]):&nbsp; &nbsp; &nbsp; &nbsp; old_max, old_str = count, result&nbsp; &nbsp; &nbsp; &nbsp; new_max, new_str = compare_strands(s1[1:], s2[1:], 0, ["", ""])&nbsp; &nbsp; &nbsp; &nbsp; if new_max < old_max:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new_max = old_max&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; new_str = old_str&nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; temp_result = []&nbsp; &nbsp; &nbsp; &nbsp; temp_result.append(result[0] + s1[0])&nbsp; &nbsp; &nbsp; &nbsp; temp_result.append(result[1] + s2[0])&nbsp; &nbsp; &nbsp; &nbsp; # result[1] += s2[0]&nbsp; &nbsp; &nbsp; &nbsp; count = count + 1&nbsp; &nbsp; &nbsp; &nbsp; new_max, new_str = compare_strands(s1[1:], s2[1:], count, temp_result)&nbsp; &nbsp; return new_max, new_str测试：with open('dna.txt', 'r') as f:&nbsp; &nbsp; size = int(f.readline())&nbsp; &nbsp; for i in range(size):&nbsp; &nbsp; &nbsp; &nbsp; strand1 = f.readline().strip('\n')&nbsp; &nbsp; &nbsp; &nbsp; strand2 = f.readline().strip('\n')&nbsp; &nbsp; &nbsp; &nbsp; print(compare_strands(strand1, strand2))输出：(3, ['AGC', 'TCG'])(0, ['', ''])(4, ['GGAC', 'CCTG'])编辑：写入文件。with open('dna.txt', 'r') as f:&nbsp; &nbsp; size = int(f.readline())&nbsp; &nbsp; for i in range(size):&nbsp; &nbsp; &nbsp; &nbsp; strand1 = f.readline().strip('\n')&nbsp; &nbsp; &nbsp; &nbsp; strand2 = f.readline().strip('\n')&nbsp; &nbsp; &nbsp; &nbsp; result = compare_strands(strand1, strand2)&nbsp; &nbsp; &nbsp; &nbsp; with open('result.txt', 'a') as result_file:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result_file.write('DNA sequece pair {}:\n'.format(i))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if result[0]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result_file.write('{}\n{}\n\n'.format(result[1][0], result[1][1]))&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result_file.write('No matches found\n\n')