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

Question

我是 Python 新手，我有一个我无法理解的项目。当给定两条链时，它需要使用递归来找到最长的有效 DNA 序列。我得到了一个名为 dna.txt 的文件。文件的第一行包含一个数字，表示将有多少对 DNA 链。然后其余的线是DNA串。我的工作是单独查看每对链，找到最长的有效 DNA 序列，并将其写入一个名为 dnaresults.txt 的新文件中。如果这要通过迭代来完成，我相当有信心我可以处理它。但是该项目要求我使用递归来 a) 找到有效的 DNA 序列并 b) 找到最长的 DNA 对。我在非常基本的层面上理解递归（斐波那契，滚动和等），但我无法理解如何在这种情况下应用它。例如，输入文件如下所示：3GAAGCTCGCCTCGGGAAAATTTGGGCCCCTCTAGGACGAGTACCTG我需要将其输出到一个新文件：DNA sequence pair 0:AGCTCGDNA sequence pair 1:No matches foundDNA sequence pair 2:GGACCCTG这是我到目前为止所尝试的。我可以使用该数字来确定执行循环的次数。我可以将这对股分开并放在它们自己的变量中。但是，一旦到了评估和比较它们的时间，我就很难过，因为我不明白在这种情况下如何使用递归。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 序列是有效的。ACTGTCTGACAG这是一个有效的序列，因为每一对都是 AT 或 GC。ACTGTCGCACTA这不是一个完全有效的序列，因为不是每一对都是 AT 或 GC。只有第 3 对和第 4 对有效（TG 和 AC）。

Answer 1

此类问题的递归使用大量堆栈，并且比使用需要线性时间和恒定空间的内置数据结构慢得多。我知道需要递归，因为那是你的问题，但我仍然觉得我应该这么说。

这是一个递归解决方案：

首先是一个检查有效对的函数：

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{}\n\n'.format(result[1][0], result[1][1]))

            else:

                result_file.write('No matches found\n\n')