Open Reading Frames

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. 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.

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.


Solution

Let’s define the DNA codon map. This step will help bypassing mRNA transcription step:

dna_codon_table = {
    "TTT":"F", "CTT":"L", "ATT":"I", "GTT":"V",
    "TTC":"F", "CTC":"L", "ATC":"I", "GTC":"V",
    "TTA":"L", "CTA":"L", "ATA":"I", "GTA":"V",
    "TTG":"L", "CTG":"L", "ATG":"M", "GTG":"V",
    "TCT":"S", "CCT":"P", "ACT":"T", "GCT":"A",
    "TCC":"S", "CCC":"P", "ACC":"T", "GCC":"A",
    "TCA":"S", "CCA":"P", "ACA":"T", "GCA":"A",
    "TCG":"S", "CCG":"P", "ACG":"T", "GCG":"A",
    "TAT":"Y", "CAT":"H", "AAT":"N", "GAT":"D",
    "TAC":"Y", "CAC":"H", "AAC":"N", "GAC":"D",
    "TAA":"STOP", "CAA":"Q", "AAA":"K", "GAA":"E",
    "TAG":"STOP", "CAG":"Q", "AAG":"K", "GAG":"E",
    "TGT":"C", "CGT":"R", "AGT":"S", "GGT":"G",
    "TGC":"C", "CGC":"R", "AGC":"S", "GGC":"G",
    "TGA":"STOP", "CGA":"R", "AGA":"R", "GGA":"G",
    "TGG":"W", "CGG":"R", "AGG":"R", "GGG":"G"
}

For the complementary DNA strand, we can simply replace A, T, G, C with T, A, C, G, respectively:

def complementary_dna(dna_string):
    replace_bases = {"A":"T","T":"A","G":"C","C":"G"}
    return ''.join([replace_bases[base] for base in reversed(dna_string)])

Another function we need to define is the direct translation function using DNA string. The translation must start with methionine (ATG):

def translate(fragment):
    peptide = []
    methionine = fragment.find("ATG")
    codons = [fragment[methionine:methionine+3] for methionine in range(methionine, len(fragment), 3)]
    for codon in codons:
        peptide += dna_codon_table.get(codon)
    return ''.join(map(str, peptide)) 

But before we directly translate DNA into amino acid sequences, we need to find out possible fragments starting with methionine codon and ending with any of stop codons (TAA, TAG or TGA), while checking three bases (codon length) in between start and stop codons.

import re

pattern = re.compile(r'(?=(ATG(?:...)*?)(?=TAA|TAG|TGA))')

fragments = []
for string in re.findall(pattern, dna_string):
    fragments.append(string)

for string in re.findall(pattern, complementary_dna(dna_string)):
    fragments.append(string)

Since we have returned DNA fragments to possibly be translated in fragments set, we can run the translate function to find out the possible peptide sequences.

with open("rosalind_orf.txt") as file:
    for line in file:
        if line.startswith(">"):
            nextline = str()
        else:
            nextline += (line.strip("\n"))
    dna_string = nextline

for string in set(fragments):
    print(translate(string))
Important note:

This problem is taken from rosalind.info. Please visit ROSALIND to find out more about Bioinformatics problems. You may also clink onto links for the definitions of each terminology.