Eenmaal de DNA sequentie van een organisme bepaald is, stelt zich de vraag welke gebieden van het genoom coderen voor eiwitten. Open reading frames (ORFs) vormen een belangrijk concept bij het voorspellen van deze coderende gebieden. Om dit te begrijpen, is het belangrijk te weten dat de vertaling van een DNA sequentie naar een eiwit gebeurt door telkens drie opeenvolgende nucleotiden (codons genaamd) om te zetten naar het volgende aminozuur dat aan de groeiende eiwitketen toegevoegd wordt. Bepaalde codons spelen een bijzondere rol bij het vertalen van DNA naar eiwitten:

Een ORF is een gebied dat begint bij het eerstvolgende startcodon (vanaf het begin van de sequentie of na het vorige stopcodon) en loopt tot en met het eerstvolgende stopcodon. Merk op dat het volgens deze definitie perfect mogelijk is dat er verschillende startcodons voorkomen tussen het eerste en laatste codon van een ORF, maar dat er nooit tussenliggende stopcodons voorkomen. Het stopcodon van een ORF ligt ook altijd een veelvoud van drie posities verder dan het eerste startcodon van het ORF. Men zegt dat het start- en stopcodon in hetzelfde reading frame liggen. Omdat codons bestaan uit drie nucleotiden, heeft een DNA sequentie dus drie reading frames waarin er telkens nul of meer ORFs kunnen gevonden worden.

Beschouw bij wijze van voorbeeld de onderstaande DNA sequentie, die kan gelezen worden in drie reading frames. Het eerste reading frame begint met de letter g, het tweede reading frame met de eerste letter c en het derde reading frame met de tweede letter c.

1 gcc ctt aat ttt att cat tgg att cca ttc att aac gtg ctg atg tcc cat ttg ttt a
  |-------------* |-----------|-----------|---------------------------------*
2 g ccc tta att tta ttc att gga ttc cat tca tta acg tgc tga tgt ccc att tgt tta
            |-----------|---------------------------------*         |
3 gc cct taa ttt tat tca ttg gat tcc att cat taa cgt gct gat gtc cca ttt gtt ta
               *                     |---------------------------------*

We hebben in deze weergave de codons van elk reading frame van elkaar gescheiden door een spatie. In dit voorbeeld beschouwen we de codons att, gca en gcc als startcodons (groen) en de codons tct, tga en ttt als stopcodons (rood). Onder elk reading frame hebben we de ORFs onderlijnd met koppeltekens (-). Daarbij geven we telkens het eerste nucleotide van een startcodon aan met een verticale streep (|) en het laatste nucleotide van een stopcodon met een sterretje (*). Op die manier is het duidelijk te zien dat er twee ORFs kunnen gevonden worden in het eerste reading frame, en telkens één ORF in het tweede en derde reading frame.

Opgave

In deze opgave stellen we DNA sequenties (inclusief codons) voor als strings die enkel bestaan uit de kleine letters a, c, g en t. Schrijf een functie ORFs waaraan drie argumenten moeten doorgegeven worden: i) een DNA sequentie (str), ii) een lijst (list) van startcodons (str) en iii) een lijst (list) van stopcodons (str). De functie moet een lijst (list) teruggeven die alle ORFs bevat die gevonden worden in de drie reading frames van de sequentie. Een ORF wordt hierbij voorgesteld als een tuple van de vorm

(startpositie, stoppositie, frame)

De startpositie van het ORF is de positie (int) van de eerste nucleotide van het startcodon, en de stoppositie de positie (int) van de laatste (derde) nucleotide van het stopcodon. Posities worden aangegeven ten opzichte van het begin van de DNA sequentie, waarbij het eerste nucleotide positie nul heeft. Het frame van het ORF slaat op het reading frame waarin het ORF gevonden werd. In de lijst die wordt teruggegeven, moeten de ORFs gerangschikt staan volgens stijgende startpositie.

Voorbeeld

>>> ORFs('gcccttaattttattcattggattccattcattaacgtgctgatgtcccatttgttta', ['att', 'gca', 'gcc'], ['tct', 'tga', 'ttt'])
[(0, 11, 1), (7, 42, 2), (12, 56, 1), (26, 52, 3)]
>>> ORFs('cgtgtgcacaactcaccccgtagacccaaaatgtggataacatg', ['aca', 'gtg'], ['aaa', 'ccc', 'gac'])
[(1, 18, 2), (3, 17, 1)]
>>> ORFs('cgagggctctcactgggacggcagaggctagtcacagtat', ['agt'], ['gac', 'ggc'])
[]