Transcription May Begin Anywhere**

In “Transcribing DNA into RNA”, we discussed the transcription of DNA into RNA, and in “Translating RNA into Protein”, we examined the translation of RNA into a chain of amino acids for the construction of proteins. We can view these two processes as a single step in which we directly translate a DNA string into a protein string, thus calling for a DNA codon table.
However, three immediate wrinkles of complexity arise when we try to pass directly from DNA to proteins. First, not all DNA will be transcribed into RNA: so-called junk DNA appears to have no practical purpose for cellular function. Second, we can begin translation at any position along a strand of RNA, meaning that any substring of a DNA string can serve as a template for translation, as long as it begins with a start codon, ends with a stop codon, and has no other stop codons in the middle. See Figure 1.

As a result, the same RNA string can actually be translated in three different ways, depending on how we group triplets of symbols into codons. For example, …AUGCUGAC… can be translated as …AUGCUG…, …UGCUGA…, and …GCUGAC…, which will typically produce wildly different protein strings. Open Reading Frames - 图1
Figure 1. Schematic image of the particular ORF with start and stop codons shown.

Problem

Either strand of a DNA double helix can serve as the coding strand for RNA transcription. Hence, a given DNA string implies six total reading frames, or ways in which the same region of DNA can be translated into amino acids: three reading frames result from reading the string itself, whereas three more result from reading its reverse complement.
An open reading frame (ORF) is one which starts from the start codon and ends by stop codon, without any other stop codons in between. Thus, a candidate protein string is derived by translating an open reading frame into amino acids until a stop codon is reached.
Given: A DNA string s of length at most 1 kbp in FASTA format.
Return: Every distinct candidate protein string that can be translated from ORFs of s. Strings can be returned in any order.

Sample Dataset

  1. >Rosalind_99
  2. AGCCATGTAGCTAACTCAGGTTACATGGGGATGACCCCGCGACTTGGATTAGAGTCTCTTTTGGAATAAGCCTGAATGATCCGAGTAGCATCTCAG

Sample Output

  1. MLLGSFRLIPKETLIQVAGSSPCNLS
  2. M
  3. MGMTPRLGLESLLE
  4. MTPRLGLESLLE

Solution

本题有误区，一般认为开放阅读框就是正反链各三个，但是实际上本题是遇到 AUG 就算，所以远不止 6 个！非常坑。
假设输入序列为 5'->3' 端的 DNA 序列，然后相应的求出反向互补，即互补链也是 5'->3' 方向的序列。因为转录只能是这个方向。
%9CWYBNHF~8GC9N]@4OU5L1.png

  1. 将两条链翻译为 mRNA ，直接替换 T->U 即可。
  2. 暴力寻找每条链中 AUG 序列，然后找到一个就开始往后翻译。如果遇到终止密码子就加入答案中，否则走完序列的不算！

由于本题需要去重，也没有说，因此用集合操作。

  1. from typing import List
  3. def readFasta(fileName: str) -> str:
  4.     seqs = []
  5.     with open(fileName) as f:
  6.         seq = []
  7.         for line in f:
  8.             line = line.strip()  # withespace
  9.             if line.startswith('>'):  # ID
  10.                 if seq:  # last sequence finished
  11.                     yield ''.join(seq)
  12.                     seq = []
  13.             elif line:  # bases
  14.                 seq.append(line.strip())
  15.         # last sequence
  16.         if seq:
  17.             yield ''.join(seq)
  19. d = {
  20.     'UUU': 'F', 'CUU': 'L', 'AUU': 'I', 'GUU': 'V', 
  21.     'UUC': 'F', 'CUC': 'L', 'AUC': 'I', 'GUC': 'V', 
  22.     'UUA': 'L', 'CUA': 'L', 'AUA': 'I', 'GUA': 'V', 
  23.     'UUG': 'L', 'CUG': 'L', 'AUG': 'M', 'GUG': 'V', 
  24.     'UCU': 'S', 'CCU': 'P', 'ACU': 'T', 'GCU': 'A', 
  25.     'UCC': 'S', 'CCC': 'P', 'ACC': 'T', 'GCC': 'A', 
  26.     'UCA': 'S', 'CCA': 'P', 'ACA': 'T', 'GCA': 'A', 
  27.     'UCG': 'S', 'CCG': 'P', 'ACG': 'T', 'GCG': 'A', 
  28.     'UAU': 'Y', 'CAU': 'H', 'AAU': 'N', 'GAU': 'D', 
  29.     'UAC': 'Y', 'CAC': 'H', 'AAC': 'N', 'GAC': 'D', 
  30.     'UAA': '', 'CAA': 'Q', 'AAA': 'K', 'GAA': 'E', 
  31.     'UAG': '', 'CAG': 'Q', 'AAG': 'K', 'GAG': 'E', 
  32.     'UGU': 'C', 'CGU': 'R', 'AGU': 'S', 'GGU': 'G', 
  33.     'UGC': 'C', 'CGC': 'R', 'AGC': 'S', 'GGC': 'G', 
  34.     'UGA': '', 'CGA': 'R', 'AGA': 'R', 'GGA': 'G', 
  35.     'UGG': 'W', 'CGG': 'R', 'AGG': 'R', 'GGG': 'G'
  36. }
  38. def orf(seq: str) -> str:
  39.     n = len(seq)
  40.     res = set()
  42.     def helper(seq: str) -> None:
  43.         rna = seq.replace("T", 'U')
  44.         for i in range(0, n - 3 + 1):
  45.             if rna[i:i+3] == 'AUG':
  46.                 protein = []
  47.                 for j in range(i, n, 3):
  48.                     if j + 3 > n: break
  49.                     codon = rna[j:j+3]
  50.                     if not d[codon]:
  51.                         res.add(''.join(protein[:]))
  52.                         break
  53.                     protein.append(d[codon])
  54.     helper(seq)
  55.     helper(seq[::-1].translate(str.maketrans('ATCG', 'TAGC')))
  56.     return '\n'.join(res)
  58. for seq in readFasta("./DNA.fasta"):
  59.     print(orf(seq))
  60. '''
  61. AGCCATGTAGCTAACTCAGGTTACATGGGGATGACCCCGCGACTTGGATTAGAGTCTCTTTTGGAATAAGCCTGAATGATCCGAGTAGCATCTCAG
  63. MLLGSFRLIPKETLIQVAGSSPCNLS
  64. M
  65. MGMTPRLGLESLLE
  66. MTPRLGLESLLE
  67. '''

正则表达式与变相“笛卡尔乘积”

  1. 用 re 需要找出所有的开始和结束，但是需要注意的就是，如何解决 3 的倍数关系！因为可能找到不是 3 倍数，肯定不对！
  2. 所有的终止子只能出现一次！因为转录到最近的终止子就停止了，因此不能够再枚举后续的终止子位置了。 ```python from typing import List

def readFasta(fileName: str) -> str: seqs = [] with open(fileName) as f: seq = [] for line in f: line = line.strip() # withespace if line.startswith(‘>’): # ID if seq: # last sequence finished yield ‘’.join(seq) seq = [] elif line: # bases seq.append(line.strip())

  1.     # last sequence
  2.     if seq:
  3.         yield ''.join(seq)

d = { ‘UUU’: ‘F’, ‘CUU’: ‘L’, ‘AUU’: ‘I’, ‘GUU’: ‘V’, ‘UUC’: ‘F’, ‘CUC’: ‘L’, ‘AUC’: ‘I’, ‘GUC’: ‘V’, ‘UUA’: ‘L’, ‘CUA’: ‘L’, ‘AUA’: ‘I’, ‘GUA’: ‘V’, ‘UUG’: ‘L’, ‘CUG’: ‘L’, ‘AUG’: ‘M’, ‘GUG’: ‘V’, ‘UCU’: ‘S’, ‘CCU’: ‘P’, ‘ACU’: ‘T’, ‘GCU’: ‘A’, ‘UCC’: ‘S’, ‘CCC’: ‘P’, ‘ACC’: ‘T’, ‘GCC’: ‘A’, ‘UCA’: ‘S’, ‘CCA’: ‘P’, ‘ACA’: ‘T’, ‘GCA’: ‘A’, ‘UCG’: ‘S’, ‘CCG’: ‘P’, ‘ACG’: ‘T’, ‘GCG’: ‘A’, ‘UAU’: ‘Y’, ‘CAU’: ‘H’, ‘AAU’: ‘N’, ‘GAU’: ‘D’, ‘UAC’: ‘Y’, ‘CAC’: ‘H’, ‘AAC’: ‘N’, ‘GAC’: ‘D’, ‘UAA’: ‘’, ‘CAA’: ‘Q’, ‘AAA’: ‘K’, ‘GAA’: ‘E’, ‘UAG’: ‘’, ‘CAG’: ‘Q’, ‘AAG’: ‘K’, ‘GAG’: ‘E’, ‘UGU’: ‘C’, ‘CGU’: ‘R’, ‘AGU’: ‘S’, ‘GGU’: ‘G’, ‘UGC’: ‘C’, ‘CGC’: ‘R’, ‘AGC’: ‘S’, ‘GGC’: ‘G’, ‘UGA’: ‘’, ‘CGA’: ‘R’, ‘AGA’: ‘R’, ‘GGA’: ‘G’, ‘UGG’: ‘W’, ‘CGG’: ‘R’, ‘AGG’: ‘R’, ‘GGG’: ‘G’ }

def orf(seq: str) -> str: n = len(seq) res = set()

  1. def helper(seq: str) -> None:
  2.     import re, bisect
  3.     rna = seq.replace("T", 'U')
  4.     start = [i.start() for i in re.finditer(r'AUG', rna)]
  5.     end = [i.start() for i in re.finditer(r'UAG|UGA|UAA', rna)]
  6.     for i in start:
  7.         # idx = bisect.bisect_right(end, i)
  8.         for j in end:
  9.             if j > i and (j - i) % 3 == 0:
  10.                 res.add(''.join(d[rna[k:k+3]] for k in range(i, j, 3)))
  11.                 break  # 距离它最近的一个足够
  13. helper(seq)
  14. helper(seq[::-1].translate(str.maketrans('ATCG', 'TAGC')))
  15. return '\n'.join(res)

for seq in readFasta(“./DNA.fasta”): print(orf(seq)) ‘’’ AGCCATGTAGCTAACTCAGGTTACATGGGGATGACCCCGCGACTTGGATTAGAGTCTCTTTTGGAATAAGCCTGAATGATCCGAGTAGCATCTCAG

MLLGSFRLIPKETLIQVAGSSPCNLS M MGMTPRLGLESLLE MTPRLGLESLLE ‘’’ ```