Mutate my DNA sequence

Question

When translating DNA into proteins, the ribosomes read the sequence of DNA nucleotides 3 by 3. Each set of 3 nucleotides is called a codon, and each codon encodes for an amino acid, with some redundancies. Here's the conversion table used by most organisms (table is read left, top, right):

Humans and most other organisms use just a single amino acid as a "start" codon: Methionine, a.k.a. Met, M, or ATG. This means that any DNA sequence coding for a protein starts with ATG, which will be recognised by the translation machinery.

However, three different codons are used to stop the translation: TAA, TAG and TGA. If the replication machinery encounters any of these, it will stop, and the translated protein will be released into the cell.

Therefore, one of the most dangerous mutations that can occur is one that will cause an early termination of protein translation. For example, if we take this DNA sequence:

ATGGCCTTCATATCGGCGGACAGCGAATCTGGTGATTAA

Split into codons:

ATG GCC TTC ATA TCG GCG GAC AGC GAA TCT GGT GAT TAA

Once translated, will give:

met ala phe ile ser ala asp ser glu ser gly asp STOP

But if we replace C at 14th position into an A, then the protein sequence will be

met ala phe ile STOP

This substitution would be written in genomics as 14C>A.

I could also perform other substitutions (25G>T for example) that would cause early termination, but 14C>A is the first one in the sequence, and so would produce the shortest protein after translation.

Challenge

Given a string of nucleotides coding for a protein (first codon is ATG, last is a STOP), find the first substitution that would cause an early termination of protein translation, resulting in the shortest possible protein. This is code golf, so fewest bytes wins!

Rules and specifications

(these will be updated if anyone asks relevant questions about what's allowed)

• DNA sequence is stored in a character string as consecutive block capitals, no spaces or punctuation in it, and contains only ACGT. If you want to store it into binary (A:00/C:01/G:10/T:11) or as integers (A:1/C:2/G:3/T:4), that's fine (you don't need to follow these encodings).

• Declaration of the codon to amino acid conversion table is part of the golfing challenge. You must choose which parts you deem relevant. Most softwares use hashes / dictionaries to store it.

• Code should return the substitution formatted under the preferred nomenclature: 14C>A (position, original nucleotide, ">", new nucleotide), but any format that includes those three elements is accepted.

• If there are no possible early termination sites, function should return any easily recognisable error value (raise an error, FALSE, -1, etc) or return nothing.

Test cases

ATGCACTGTTGGGGAGGCAGCTGTAACTCAAAGCCTTAG
-> 9T>A

ATGGTAGAACGGAGCAGCTGGTCATGTGTGGGCCCACCGGCCCCAGGCTCCTGTCTCCCCCCAGGTGTGTGGTCATGCCAGGCATGCCCTTAG
-> 7G>T

ATGGAACATCAATCTCAGGCACCTGGCCCAGGTCATTAA
-> 4G>T

ATGTGCCAAGTGCATTCTTGTGTGCTTGCATCTCATGGAACGCCATTTCCCCAGACATCCCTGTGGCTGGCTCCTGATGCCCGAGGCCCATGA
-> 6C>A

ATGCTTTTCCATGTTCTTTGGCCGCAGCAAGGCCGCTCTCACTGCAAAGTTAACTCTGATGCGTGA
-> 20G>A

ATGGTAGAGTAA
-> 7G>T

ATGGTTCCACGGTAA
-> ERROR

Answer 1

JavaScript (ES6),  124 ... 93  92 bytes

Output format: XiY, with X = original nucleotide, i = position, Y = new nucleotide.

s=>s[i=([,,x,y]=s.match(/(.A[AG]|.GA|T(.[AG]|(A|G).))(...)*$/)).index+!!x+!!y]+-~i+'AT'[+!x]

Try it online!

Regular expression

r = /(.A[AG]|.GA|T(.[AG]|(A|G).))(...)*$/
     (          |               )           // 1st capturing group
      .A[AG]|.GA                            // match ★AA, ★AG or ★GA
                 T(.[AG]|(A|G).)            // 'T' + 2nd & 3rd capturing groups:
                                            // match T★A, T★G, TA★ or TG★
                                 (...)*$    // make sure that the number of trailing
                                            // nucleotides is a multiple of 3

To summarize, this will match 21 codons that can be mutated to generate a STOP. By testing the 2nd and 3rd capturing groups, we can classify them into 3 categories describing the position of the nucleotide that needs to be altered.

 2nd group | 3rd group | position | matching codons
-----------+-----------+----------+-------------------------------------------------------
  not set  |  not set  |    1st   | (TAA) (TAG) (TGA) CAA CAG CGA AAA AAG AGA GAA GAG GGA
    set    |  not set  |    2nd   | TTA TTG TCA TCG TGG
    set    |    set    |    3rd   | TAT TAC TGT TGC

Commented

s =>               // s = input DNA sequence
  s[               // append the original nucleotide ...
    i =            //   ... which is at position i (0-based)
    ( [,, x, y] =  //   x = 2nd capturing group, y = 3rd capturing group
        s.match(r) //   apply the regular expression to s
    ).index        //   get the position of the matching codon
    + !!x + !!y    //   add 2 if x and y are set, 1 if only x is set, 0 if x is not set
  ]                //
  + -~i            // append the 1-indexed position
  + 'AT'[+!x]      // append the new nucleotide: 'T' if x is not set, 'A' otherwise

Answer 2

Perl 5, 73 72 bytes

-1 byte using anchor at the end instead of the start

/(?|(.)(A[AG]|GA)|T(.)[AG]|T[AG](.))(...)*$/;$_="$+[1]$1>".($-[1]%3?A:T)

TIO

/^(...)*?(?|(.)(A[AG]|GA)|T(.)[AG]|T[AG](.))/;$_="$+[2]$2>".($-[2]%3?A:T)

Try it online!

Answer 3

Jelly, 30 bytes

os3ḅ4f“EGM‘Ḋ
JṬ€×Ɱ4ZẎçƇ⁸ḢĖżW€Ṁ

A monadic Link accepting a list of integers (in [1,2,3,4] mapping to ACGT respectively) which yields a list of lists of integers, [[position, new nucleotide], original nucleotide].

(A valid sequence with start, and stop but no possible substitution that would cause early termination will output [[4]])

Try it online!
...Or see this version which performs both a translation from the ACGT input format, and a translation to the {position}{original nucleotide}>{new nucleotide} output format.

How?

os3ḅ4f“EGM‘Ḋ      - helper Link: [0,...,0,new nucleotide], N; DNA integer list, A
o                 - (N) logical OR (A) (vectorises)
 s3               - split into chunks of three
   ḅ4             - convert from base four to integer
      “EGM‘       - code-page index list = [69,71,77]
     f            - filter keep (i.e. only keep stops)
           Ḋ      - dequeue (so if only a single stop was found and hence no early
                             stops we'll have an empty list which is falsey)

JṬ€×Ɱ4ZẎçƇ⁸ḢĖżW€Ṁ - Main Link: DNA integer list, A
J                 - range of length (of A) -> [1,2,...]
 Ṭ€               - untruth each -> [[1],[0,1],[0,0,1],...]
   ×Ɱ4            - map across [1,2,3,4[ performing multiplication
      Z           - transpose
       Ẏ          - tighten -> [[1],[2],[3],[4],[0,1],[0,2],[0,3],[0,4],[0,0,1],...]
                  - (call that X)
          ⁸       - use chain's left argument, A, as the right argument
         Ƈ        - filter keep those (x in X) for which this is truthy:
        ç         -   call the helper link as a dyad f(x, A)
           Ḣ      - head (which will be the shortest)
            Ė     - enumerate (that)
              W€  - wrap each (integer a in A) in a list
             ż    - zip left and right together
                Ṁ - get the maximum

Answer 4

Python 3, 88 bytes

f=lambda i,j,k,*l,n=1:(j+k<4)*(n,i,5)+(i-k>2)*(n+1,j,1)or(i-j>2)*(n+2,k,1)or f(*l,n=n+3)

Try it online!

Solution without regex. Uses 1235 for AGCT, respectively. Takes each base as a separate argument. Will suggest A for any instance of T*A, T*G, TA*, TG*. Outputs as (position, original base, new base). Returns an (invalid) 6-element tuple when there is no early termination site.

Explanation

f=lambda i,j,k,*l,n=1:
  (j+k<4)         # If the last two bases are 1+1 (AA), 1+2 (AG) or 2+1 (AG)
    *(n,i,5)      #   Return (position, 1st base, 5 (T))
  +(i-k>2)        # If the 1st base is 5 (T) and the 3rd base 1 (A) or 2 (G) 
    *(n+1,j,1)    #   Return (position, 2nd base, 1 (A))
  or(i-j>2)       # If the 1st base is 5 (T) and the 2nd base 1 (A) or 2 (G) 
    *(n+2,k,1)    #   Return (position, 3rd base, 1 (A))
  or f(*l,n=n+3)  # Else process the next three bases

Answer 5

C# (Visual C# Interactive Compiler), 138 bytes

x=>{for(int i=0;;i++)foreach(var k in"AGT")if("TAG TAA TGA".Contains(x.Remove(i,1).Insert(i,k+"").Substring(i-i%3,3)))return(i+1,x[i],k);}

Try it online!

Answer 6

05AB1E, 29 27 bytes

vNU4E¨NXǝ3ô•`|Ž•₅вåàiX>yN)q

Input as 2341 for ACGT respectively.
Output in the format and order [position, original nucleotide, new nucleotide]. Will output the input itself if there are no possible early termination sites. (Could be 1 byte less by removing the > if 0-based positions were allowed.)

Try it online or verify all test cases or verify all test cases with a conversion back to ACGT.

Explanation:

v             # Loop over each of the digits of the (implicit) input-string
 NU           #  Store the current loop-index in variable `X`
   4E         #  Inner loop in the range [1,4]:
     ¨        #   Remove the last digit of the (implicit) input-string
              #   (this is to ensure it doesn't find the trailing STOP all inputs will have)
      NXǝ     #   Insert the current digit of the inner loop at position `X` in the string
         3ô   #   Split the string into parts of size 3
   •`|Ž•      #   Push compressed integer 7964812
        ₅     #   Push builtin integer 255
         в    #   Convert the larger integer to base-255 as list: [122,124,142]
   å          #   Check for each of these three values if it's in the list
    ài        #   If any is truthy:
      X       #    Push the current index of the outer loop we stored in `X`
       >      #    And increase it by 1 to make the 0-based index 1-based
        y     #    Push the current digit of the outer loop
         N    #    Push the current digit of the inner loop
          )   #    Wrap all three values into a list
           q  #    And terminate the program
              #    (after which this list is output implicitly as result)
              # (and if no value is found after the nested loop,
              #  output the (implicit) input as output implicitly instead)

See this 05AB1E tip of mine (sections How to compress large integers? and How to compress integer lists?) to understand why •`|Ž• is 7964812 and •`|Ž•₅в is [122,124,142].

Answer 7

Python 2, 138 133 144 142 bytes

f=lambda s,i=0:next((`i-~j`+s[j]+'TAA'[j]for j in[0,1,2]if re.match('.TTA.[[[AAAGGG]]].'[j::3]+'|.GA',s[:3])),s[6:]and f(s[3:],i+3))
import re

Try it online!

Returns nXY instead of nX>Y, or the empty string if there is no valid substitution.

Answer 8

K (oK), 91 bytes

{,/(1+t),(x@t:(&u)+3*-3!p),(u:r@p)#'t@3!p:*&1=+/'r:0N 3#,//~(t:3 3#"TAATAGTGA")=\:/:0N 3#x}

Try it online!

I'm sure my solution can be significally golfed (I used too many named varialbes)

Answer 9

Brainf***, 696 624 397 Bytes

>>>>>>,,,++>>>+[-<<,<<+<<+<<+>,>>,>>>[>+<<<<<<<<+>>>>>>>-]>[-<+>]<<<<<<<<-[-[-[->->-[-[-[->->[-]>->+++>>>+<<<<<]>[->-[-[[-]>->+++>>+<<<<<]]>[->+>->+<<<]]<]>[->-[-[-[->->++>>+<<<<]>[->++>->+<<<]<]>[->+>-->+<<<]<]>[-]]<]>[->-[-[-[->->++>>+<<<<]>[->++>->+<<<]<]]>[-]]<]]]>[->-[-[>->[-]>->+++>>>+<<<<<]>[->-[[-]>->+++>>>+<<<<<]>[->>>++++<<<]]<]>[->-[-[[-]>->+++>>>+<<<<<]]>[->>>++++<<<]]]>>>>]<<<.>.>.

Uses the actual bytes 1, 2, 3, 4 to code for A, G, C, T respectively and outputs the position as a byte as well, so you only get the position modulo 256. Outputs position + two zero bytes if there is no possible mutation.

Try it online!

How?

# X 1 Y 1 Z 1 C L L F
>>>>>>,,, #first codon is always ATG
++>>>+[
    - #zero exit flag
    <<,<<+<<+<<+> #input X into L1 for a trick later|set switch flags|seek to Y
    ,>>, #memory is now 0 1 Y 1 Z 1 4 X 0 0
    >>>[>+<<<<<<<<+>>>>>>>-]>[-<+>] #copy L1 onto cell0
            #memory is now X 1 Y 1 Z 1 4 X 0 0
    <<<<<<<< #begin switch on X
    -[-[-[-
    
    #case T:
        >- > #begin switch on Y
        -[-[-[-
        #case TT:
            >->[-]>->+++>>>+<<<<<] #TT not possible|zero out switch flags|inc exit flag|increase counter
        #case TC:
            >[- > #switch Z
            -[-[[-]>->+++>>+<<<<<] #cases TCT TCC not possible
             ] #TCG ~ TAG (fall through) 
            >[- >+>->+<<<] #TCA ~ TAA 
            ]<]
        #case TG:
            >[- >
            -[-[-[-
            >->++>>+<<<<] #TGT ~ TGA
            >[- >++>->+<<<]<] #TGC ~ TGA
            >[- >+>-->+<<<]<] #TGG ~ TAG
            >[-] #TGA is correct STOP
            ]<]
        #case TA:
            >[- >
            -[-[-[-
            >->++>>+<<<<] #TAT ~ TAA
            >[- >++>->+<<<]<] #TAC~TAA
             ] #TAG is correct STOP (fall through)
            >[-] #TAA is correct STOP
            ]
        <]
    #case C:
        ] (fall through)
      #we can fall through because we already put the letter into L1
    #case G:
        ] (fall through) 
    #case A:
        >[- >
        -[-[
        #cases _C & _T not possible
            >->[-]>->+++>>>+<<<<<]
        #case _G:
            >[- >
            -[[-]>->+++>>>+<<<<<] #cases _GC/_GT/_GG are not possible
            >[->>>++++<<<] #_GA ~ TGA
            ]<]
        #case _A:
            >[- >
            -[-[[-]>->+++>>>+<<<<<] #cases _AC/_AT not possible
             ] #AAG ~ TAG (fall through)
            >[->>>++++<<<] #_AA ~ TAA
            ]
        ]
    
    #pointer is on cell5
    #if exit flag is zero then exit loop:
    >>>>
]
<<<.>.>. #print position and letters

It loads one codon at a time and uses a series of switch statements to look for all the possible codons that could mutate into a STOP. Further golfing ideas I have are:

• For C__, G__, A__ codons, the switch statements are almost identical. There has to be a way to collapse them Done.

• Is there a way to fall through cases in BF? Some of the cases are identical There is! Just replace the entire case with ].

• There's probly a more optimal arrangement of the memory cells

The last bullet won't save too much; I'm happy with shaving 300 bytes for now.

Answer 10

Retina 0.8.2, 68 bytes

((...)*?((.)(?=AA|AG|GA)|T(.(?=G)|G.)))(?<=(.)).*
$.1$6>$#4$*T$#5$*A

Try it online! Link includes test cases. Explanation:

(

Capture the string up to and including the mutation so that we can take the length.

 (...)*?

Capture as few codons as necessary.

 (

Choose either:

  (.)(?=AA|AG|GA)

a nucleotide followed by AA, AG or GA (using the count of captures of capture group 4 to identify the necessary mutation)

 |

or

  T(.(?=G)|G.)

a nucleotide either side of a G, both following a T (using the count of captures of capture group 5 to identify the necessary mutation)

 )

End of choice.

)

End the first capture at the nucleotide to be mutated.

(?<=(.))

Look behind to see the nucleotide to be mutated (trying to capture it inside the group turns out to be nontrivial).

.*

Also delete the rest of the input.

$.1

Output the position of the nucleotide to be mutated.

$6>

Output the nucleotide to be mutated plus a >.

$#4$*T

If the first alternative matched then mutate the nucleotide to a T.

$#5$*A

If the second alternative matched then mutate the nucleotide to an A.

Answer 11

Red, 187 bytes

Thanks to @Jitse for finding a bug!

func[s][k: 0 until[v: take/part s 3 foreach t["TAA""TAG""TGA"][u: collect[repeat i 3[if(m: v/:i)<> n: t/:i[keep/only reduce[k + i m">"n]]]
]if 1 = length? u[print u exit]]k: k + 3 s =""]]

Try it online!

Using Red's parse:

Red, 211 bytes

func[s][u: func[c][print[index? p p/1">"c]]t:"T"a:"A"c:"C"g:"G"parse
s[any[[[p:[a | g | c]"AA"|"AG"|"GA"](u"T")|[t p:[t | c | g][a | g]](u"A")|[t
p:[a | t | c]a](u"G")|["TG"p:[g | t | c]](u"A")](exit)| 3 skip]]]

Try it online!

Answer 12

K (ngn/k), 56 bytes

{(1+;x;a)@'*<(*&~^5 6 9?4/+0N 3#)'i@[x;;:;]'a:1&3!i:!#x}

Try it online!

encodes "TAGC" as 0 1 2 3 respectively

returns 1 1 0 on error

important observation: there's no point trying to replace a nucleotide with anything other than T (when first in the codon) or A (when second or third)

{ } function with argument x

i:!#x the list 0 1 ... length(x)-1, assigned to i

a:1&3!i mod 3 and min with 1: 0 1 1 0 1 1 ... 0 1 1, assigned to a

@[x;;:;] a projection - tetradic @ (a.k.a. "amend") with 2 missing arguments. this is a function that when given args u and v, creates a copy of x and replaces its u-th element with v

i@[x;;:;]'a call the projection with corresponding elements from i and a

( )' each

0N 3# reshape to a 3 columns wide matrix

4/+ decode from base 4. for a codon u v w this is (16*u)+(4*v)+w

*&~^5 6 9? find the index of the first codon that decodes to 5 (TAA) or 6 (TAG) or 9 (TGA)

*< from the length(x) such possible first codons, find the index p of the one that terminates earliest

(1+;x;a)@' make a list of (1+p;x[p];a[p])