How to translate DNA recursively? (No while/for loops, also no translate function) in Python-CodePudding

So I need to translate DNA, but I'm not allowed to use any loops, it has to be done recursively. Without any loops, I really have no clue how to go about it... Because without the loop it can only print 1 nucleotide at a time. The translate function is also not allowed.

def one_dna_to_rna(c):
"""Converts a single-character c from DNA nucleotide
   to complementary RNA nucleotide
"""
if c == 'A':
    return 'U'
if c == 'C':
    return 'G'
if c == 'G':
    return 'C'
if c == 'T':
    return 'A'
else:
    return ""

def transcribe(s):
""" Argument is a string consisting of DNA nucleotis (A, C, G, T)
    Output will be (A -> U, C -> G, G -> C, T -> A)
"""

#nucleotides = ['A', 'C', 'G', 'T', " "]

x = len(s) - 1

if s == "":
    return ""
    
if s[0:x] == 'A':
    return one_dna_to_rna(s)
if s[0:x] == 'C':
    return one_dna_to_rna(s)
if s[0:x] == 'G':
    return one_dna_to_rna(s)
if s[0:x] == 'T':
    return one_dna_to_rna(s)
return one_dna_to_rna(s)   transcribe(s[0:x])

#Tests
#assert transcribe('ACGTTGCA') == 'UGCAACGU'
#assert transcribe('ACG TGCA') == 'UGCACGU'  
#assert transcribe('GATTACA')  == 'CUAAUGU'

CodePudding user response：

This function modification might not help to solve the problem, but It can be quite helpful when you have to put so many if conditions.

def one_dna_to_rna(c):
   dna_rna={'A':'U','C':'G','G':'C','T':'A'}
   if c in dna_rna:
      return dna_rna[c]
   else:
       return ""

CodePudding user response：

Please note that recursion sucks for this purpose in python. Recursion is great in other languages, but really not meant to be used like this in python.

It's okay to juggle between loops and recursion for learning purposes, but remember that recursion should not be used this way in python, so try not to get bad habits.

Anyway, any loop can easily be transformed into recursion:

def do_something_in_a_loop(s):
    result = init_value
    for c in s:
        result  = do_something(c)
    return result

def do_something_in_recursion(s, i=0, acc=None):
    if acc is None:
        acc = init_value
    if i < len(s):
        acc  = do_something(s[i])
        return do_something_in_recursion(s, i 1, acc)
    else: # i >= len(s)
        return acc

As a sidenote, here is one way to write your function without any explicit loop not recursion:

from collections import defaultdict

def transcribe(dna):
    d = defaultdict(str, {'A':'U','C':'G','G':'C','T':'A'})
    ''.join(map(d.__getitem__, dna))

print(transcribe('ACG TGCA'))
# UGCACGU

Or equivalently:

def transcribe(dna):
    d = {'A':'U','C':'G','G':'C','T':'A'}
    return ''.join(d.get(c, '') for c in dna)

print(transcribe('ACG TGCA'))
# UGCACGU

CodePudding user response：

You can recursively change one letter at the time, increasing the index you want to update each time you go deeper into recursion:

map_rna= {'A':'U','C':'G','G':'C','T':'A'}
def f(sequence, pos, map_rna):
    if pos < len(sequence):
        text =  sequence[:pos]    map_rna[sequence[pos]]   sequence[pos   1 : ]
        return f(sequence, pos 1, map_rna)
    else:
        return sequence

So:

sequence= "ACGTTGCA"
f(sequence, 0, map_rna)

output:

UGCAACGU

CodePudding user response：

I guess this is some learning exercise, because you would normally use loops here for sure. However, lets try to solve this with recursion!

I started by simplifying method for character translation (similarily as @Jeson Pun did):

def translate_char(char):
    TRANSLATIONS = {
        "A": "U",
        "C": "G",
        "G": "C",
        "T": "A",
        " ": "", # let's solve spaces here
    }
    return TRANSLATIONS[char]

There are for sure multiple ways to do this, but I was curious about using yield, as I'm not very experienced with it and in the same time, it seemed like it can be used for this kind of problem (so there is no need for passing some object to keep all the data).

So, what are we doing? First, we need some method to translate one character and also call translation of the next one (creating loop with recursion):

def translate_ith_char(i, whole_string):
    # end if there are no more characters
    if i == len(whole_string):
        return

    # else
    # get translated character and yield it 
    yield translate_char(whole_string[i])
    # call this method on the next character
    # here I needed to change `yield` to `yield from` to delegate iteration (see (here)[https://stackoverflow.com/questions/52725568/how-to-yield-in-a-recursive-function-in-python])
    yield from translate_ith_char(i   1, whole_string)

And now just finish it with method transcribe that's called from outside:

def transcribe(whole_string):
    # because we are yielding, we don't get values, but a generator
    generator = translate_ith_char(0, whole_string)
    # we get a string from generator
    transcribed_value = "".join(generator)
    return transcribed_value

Here's complete code passing tests

def transcribe(whole_string):
    generator = translate_ith_char(0, whole_string)
    transcribed_value = "".join(generator)
    return transcribed_value


def translate_ith_char(i, whole_string):
    if i == len(whole_string):
        return

    yield from translate_char(whole_string[i])
    yield from translate_ith_char(i   1, whole_string)

def translate_char(char):
    TRANSLATIONS = {
        "A": "U",
        "C": "G",
        "G": "C",
        "T": "A",
        " ": "",
    }
    return TRANSLATIONS[char]


# Tests
assert transcribe("ACGTTGCA") == "UGCAACGU"
assert transcribe("ACG TGCA") == "UGCACGU"
assert transcribe("GATTACA") == "CUAAUGU"

Ok, that was fun, and I learned a bit about using yield and yield from!

I'm not saying this is the best solution (it is not - it's absurdly complicated for this task), but to my knowledge it is a working one, and (in my opinion) pretty clean. It might be viable solution (with some changes) if it was used on stream of dna with unknown length.