我是 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)。
此类问题的递归使用了大量的堆栈,并且比使用占用线性时间和恒定空间的内置数据结构要慢得多。我知道需要递归,因为那是你的问题,但我仍然觉得我应该这么说。
这是一个递归解决方案:
首先是一个检查有效对的函数:
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')
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句