Een DNA sequentie kan voorgesteld worden door een string die enkel bestaat uit de letters A, C, G  en T. Het invers complement van een DNA sequentie wordt bekomen door de volgorde van de letters in de string om te keren, en daarbij elk voorkomen van een A te wijzigen in een T (en omgekeerd) en elk voorkomen van een G in een C (en omgekeerd). Zo is het invers complement van de DNA sequentie AGCTGCT bijvoorbeeld AGCAGCT. Een palindromische sequentie is een DNA sequentie die precies hetzelfde leest op de complementaire string. Zo is het invers complement van de DNA sequentie AATGCATT gelijk aan de oorspronkelijke DNA sequentie, en is deze DNA sequentie dus een voorbeeld van een palindromische sequentie.

Opgave

1. Schrijf een functie DNAPalindroom waaraan een DNA sequentie als argument moet doorgegeven worden. Deze functie moet als resultaat de waarde True teruggeven indien de gegeven DNA sequentie een palindromische sequentie is. Anders moet de waarde False teruggegeven worden.

2. Gebruik de functie DNAPalindroom om een functie langstePalindroom te schrijven. Aan deze functie moet een DNA sequentie als argument doorgegeven worden. De functie moet de langste palindromische deelsequentie van de gegeven sequentie als resultaat teruggeven. Om de langste palindromische deelsequentie te vinden, kan je alle mogelijke deelsequenties van de gegeven DNA sequentie overlopen, testen of het gaat om een palindromische sequentie, en uiteindelijk het langste palindroom overhouden. Om alle mogelijke deelsequenties van een gegeven DNA sequentie te doorlopen, kan je alle mogelijke startposities doorlopen en voor elke mogelijke startpositie alle mogelijke stopposities doorlopen. Op die manier vind je elke deelsequentie als de sequentie tussen elke combinatie van mogelijke start- en stopposities.

Voorbeeld

>>> DNAPalindroom('GAATTC')
True
>>> DNAPalindroom('GAAATTC')
False
>>> DNAPalindroom('ACCGGT')
True
>>> langstePalindroom('GGGCCTATTGACTTCTTATCGTAGCCGGCCTTGTTAGTAGATGAGAATCA')
'GCCGGC'
>>> langstePalindroom('AGCGCCTTGCAGCCGGGGACGGTGAGTTGGTAGCGCCCCTCAGGTCACTG')
'GCGC'