Frederick Sanger (1918-2013) was een Britse biochemicus die er als één van vier mensen in geslaagd is om twee Nobelprijzen in de wacht te slepen. In 1958 won hij een Nobelprijs voor zijn werk rond het bepalen van de structuur van eiwitten — in het bijzonder de structuur van insuline — en in 1980 won hij samen met Walter Gilbert een Nobelprijs voor hun bijdrage aan het bepalen van de basevolgorde van een DNA sequentie (allebei Nobelprijzen voor de chemie).
Voor dit laatste ontwikkelden ze in 1977 een nieuwe methode die Sangersequenering genoemd wordt. Deze methode was gedurende 25 jaar de meest gebruikte sequeneringsmethode, maar ze is vandaag wat op het achterplan verdwenen door de opkomst van de Next Generation Sequencing methoden. Ze wordt echter nog vaak gebruikt voor kleinere projecten, voor de validatie van Next-Gen resultaten en om langere sequentiereads (> 500 basen) te bekomen. In onderstaande video wordt in grote lijnen uitgelegd hoe deze methode werkt.
In deze opgave stellen we een DNA sequentie voor als een string die enkel bestaat uit de hoofdletters A, C, G en T, die de verschillende basen (of nucleotiden) voorstellen. Voorts moet je van de Sangermethode enkel weten dat het sequeneren van een DNA sequentie een groot aantal fragmenten oplevert, waarvan enkel de lengte en de laatste base gekend zijn. We zullen zo een fragment voorstellen door een string die bestaat uit nul of meer koppeltekens (-) die onbekende basen voorstellen aan het begin van de sequentie, gevolgd door één van de vier baseletters. Zo stelt onderstaande string bijvoorbeeld een fragment van lengte 6 voor, wat aangeeft dat de zesde base van de DNA sequentie een G is.
-----G
Alle fragmenten die het sequeneren van een DNA sequentie oplevert, worden opgeslaan in een tekstbestand dat één fragment per regel bevat. Omdat de lengte van elk fragment op een stochastische manier bepaald wordt, is het mogelijk dat er geen fragmenten zijn met een bepaalde lengte of dat er verschillende fragmenten zijn met dezelfde lengte. Door fouten in het sequeneringsproces is het goed mogelijk dat er fragmenten zijn met dezelfde lengte, maar met een verschillende baseletter op het einde. Hierdoor is het niet altijd duidelijk welke base er op welke positie staat.
----T C -C -----G C -----C ---T ----A ----C -----G
Met de fragmenten uit bovenstaand voorbeeldbestand kunnen we bijvoorbeeld afleiden dat de eerste base van de sequentie een C is (bevestigd door twee fragmenten), de tweede base ook een C, en de vierde base een T. Over de derde base hebben we geen informatie, omdat er geen fragmenten zijn van lengte 3. De vijfde base kan een A, een C of een T zijn, en de zesde base kan een C of een G zijn.
De International Union of Pure and Applied Chemistry (IUPAC) heeft een code opgesteld (de IUPAC code) die aan alle verschillende combinaties van één, twee, drie of vier verschillende basen een verschillende hoofdletter uit het alfabet toekent. Zo wordt de combinatie "A of C of T" aangeduid met de letter H, de combinatie "C of G" met de letter S, en de combinatie "A of C of G of T" met de letter N. Op basis van de informatie in bovenstaand voorbeeldbestand kan de DNA sequentie dus gereconstrueerd worden als CCNTHS. Hierbij hebben we de letter N ook gebruikt voor posities in de sequentie waarover geen informatie gekend is.
In deze opgave werken we met twee soorten tekstbestanden. Een IUPAC bestand bevat voor alle verschillende combinaties van één, twee, drie of vier verschillende baseletters een regel met daarop een unieke hoofdletter, gevolgd door een spatie en de baseletters van de combinatie in alfabetische volgorde. Alle hoofdletters in de eerste kolom van het bestand zijn verschillend. Een fragmentenbestand bevat alle fragmenten die de Sangersequenering van een DNA sequentie heeft opgeleverd, elk op een afzonderlijke regel. Gevraagd wordt:
Schrijf een functie IUPAC waaraan de locatie van een IUPAC bestand moet doorgegeven worden. De functie moet een dictionary teruggeven die alle combinaties van baseletters uit het gegeven bestand afbeeldt op de hoofdletter waarmee de combinatie voorgesteld wordt. Deze hoofdletter is terug te vinden in de eerste kolom van het bestand.
Schrijf een functie code waaraan twee argumenten moeten doorgegeven worden: i) een collectie-object (een string, een lijst, een tuple of een verzameling) met één of meer baseletters, en ii) een dictionary die alle verschillende combinaties van één, twee, drie of vier verschillende baseletters (voorgesteld als een string met de baseletters in alfabetische volgorde) afbeeldt op de unieke hoofdletter waarmee de combinatie voorgesteld wordt. De functie moet de hoofdletter teruggeven die correspondeert met de combinatie van basen die als eerste argument aan de functie wordt doorgegeven, rekening houdend met de afbeelding die bepaald wordt door de dictionary die als tweede argument aan de functie wordt doorgegeven.
Schrijf een functie fragmenten waaraan de locatie van een fragmentenbestand moet doorgegeven worden. De functie moet een dictionary teruggeven waarin alle posities van de gesequeneerde DNA sequentie waarover informatie te vinden is in het gegeven fragmentenbestand worden afgebeeld op de verzameling van basen op die positie volgens het fragmentenbestand. De eerste positie van de sequentie is positie 1, de tweede positie 2, enzoverder.
Schrijf een functie sequentie waaraan de locaties van een fragmentenbestand en een IUPAC bestand moeten doorgegeven worden. De functie moet de DNA sequentie teruggeven die kan gereconstrueerd worden uit de fragmenten in het gegeven fragmentenbestand. Hierbij moet gebruikgemaakt worden van de IUPAC codes die gedefinieerd worden in het gegeven IUPAC bestand. Indien het fragmentenbestand geen informatie bevat over een bepaalde positie in de DNA sequentie, dan moet die positie ingevuld worden met de letter uit het gegeven IUPAC bestand die staan voor één van de vier mogelijke basen (A of C of G of T). De laatste positie van de sequentie correspondeert met de laatste positie waarover informatie kan teruggevonden worden in het gegeven fragmentenbestand.
Bij onderstaande voorbeeldsessie gaan we ervan uit dat de tekstbestanden fragmenten1.txt1, fragmenten2.txt2 en IUPAC.txt3 zich in de huidige directory bevinden.
>>> codes = IUPAC('IUPAC.txt')
>>> codes
{'G': 'G', 'C': 'C', 'ACGT': 'N', 'ACT': 'H', 'ACG': 'V', 'AC': 'M', 'CT': 'Y', 'AT': 'W', 'AG': 'R', 'CG': 'S', 'T': 'T', 'A': 'A', 'GT': 'K', 'AGT': 'D', 'CGT': 'B'}
>>> code('ATC', codes)
'H'
>>> code(['G', 'C', 'G', 'C', 'C', 'C'], codes)
'S'
>>> code(('A', 'T', 'T', 'T', 'A', 'T', 'A', 'T', 'A', 'A'), codes)
'W'
>>> code({'G', 'A', 'T'}, codes)
'D'
>>> fragmenten('fragmenten1.txt')
{1: {'C'}, 2: {'C'}, 4: {'T'}, 5: {'C', 'A', 'T'}, 6: {'C', 'G'}}
>>> fragmenten('fragmenten2.txt')
{1: {'T'}, 2: {'G'}, 3: {'A'}, 4: {'C'}, 6: {'G'}}
>>> sequentie('fragmenten1.txt', 'IUPAC.txt')
'CCNTHS'
>>> sequentie('fragmenten2.txt', 'IUPAC.txt')
'TGACNG'