Background:

Consider a DNA sequence, S, provided as input. The goal is to convert this to a string of amino acids corresponding to the codons in S. The first three letters in S correspond to the first codon and the first amino acid in the sequence. The genetic code for the second amino acid corresponds to the 4th-6th letters and so on. The function start with converting individual codons (three uppercase letters) into amino acids (single lowercase letter). DNAtoAA converts S into a string, AA, of all distinct amino acids contained in the string ordered as they first appear in S. Note that the string should not include any amino acid more than once. For example, the string ATAATCATAATG should be converted to im.

Task:

Concise discussions of the following algorithm and its running time:

import time

def DNAtoAA(S): """Convert genetic sequence contained in input string, S, into string of amino acids corresponding to the distinct amino acids found in S and listed in the order that they appear in S Return amino acid corresponding to input codon. Assumes valid codon has been provided as input is returned for valid codons that do not respond to amino acids. """ table = { 'ATA':'i', 'ATC':'i', 'ATT':'i', 'ATG':'m', 'ACA':'t', 'ACC':'t', 'ACG':'t', 'ACT':'t', 'AAC':'n', 'AAT':'n', 'AAA':'k', 'AAG':'k', 'AGC':'s', 'AGT':'s', 'AGA':'r', 'AGG':'r', 'CTA':'l', 'CTC':'l', 'CTG':'l', 'CTT':'l', 'CCA':'p', 'CCC':'p', 'CCG':'p', 'CCT':'p', 'CAC':'h', 'CAT':'h', 'CAA':'q', 'CAG':'q', 'CGA':'r', 'CGC':'r', 'CGG':'r', 'CGT':'r', 'GTA':'v', 'GTC':'v', 'GTG':'v', 'GTT':'v', 'GCA':'a', 'GCC':'a', 'GCG':'a', 'GCT':'a', 'GAC':'d', 'GAT':'d', 'GAA':'e', 'GAG':'e', 'GGA':'g', 'GGC':'g', 'GGG':'g', 'GGT':'g', 'TCA':'s', 'TCC':'s', 'TCG':'s', 'TCT':'s', 'TTC':'f', 'TTT':'f', 'TTA':'l', 'TTG':'l', 'TAC':'y', 'TAT':'y', 'TAA':'_', 'TAG':'_', 'TGC':'c', 'TGT':'c', 'TGA':'_', 'TGG':'w', } t1 = time.time() # Compute hashes of P and first M element of P # and compare AA = "" if len(S)%3 == 0: for i in range(0, len(S), 3): AA+= table[S[i:i + 3]] AAlist = []

for element in AA: # fill the list if the list is empty if len(AAlist) == 0: AAlist.append(element) # check with the last element of the list if AAlist[-1] != element: AAlist.append(element) n = len(AAlist) # we can return empty and single character # string directly if (n<2): return AAlist # consider the general case of n j = 0 for i in range(n): if (AAlist[j] != AAlist[i]): j += 1 AAlist[j] = AAlist[i] # Putting string termination # character. j += 1 AAlist = AAlist[:j] t2 = time.time() runtime = t2 - t1 print(*AAlist, sep = "") print("Running Time:", runtime)