Eén van de meest opvallende eigenschappen van genoomsequenties is de grote mate waarin bepaalde fragmenten binnen het genoom herhaald worden. Dit is voornamelijk het geval bij eukaryoten. Zo bestaat het Y chromosoom van de mens grotendeels uit herhaalde deelsequenties. Bij een screening van de 3,6 miljoen DNA baseparen geëxtraheerd uit C. elegans werden meer dan 7000 families van herhaalde sequenties geïdentificeerd. Daar staat tegenover dat in het genoom van prokaryoten nauwelijks herhaalde sequenties voorkomen, behalve enkele kleinschalige en duidelijk gestructureerde herhalingen. Naast de ongelofelijke hoeveelheid aan herhalingen valt DNA ook op door de grote variëteit aan herhaalde structuren, de verscheidenheid aan mechanismen die worden voorgesteld om de oorsprong en het behoud van deze herhalingen te verklaren, en de biologische functies die sommige van deze herhalingen kunnen spelen.

Opgave

Uit de inleiding zal het wel duidelijk zijn dat genoomonderzoek nood heeft aan efficiënte algoritmen voor het opsporen van verschillende types van herhaalde structuren in genoomsequenties. In het bijzonder wordt gevraagd om voor deze opgave een algoritme te implementeren waarmee de langste herhaalde deelstring (LHD) binnen een gegeven DNA sequentie kan gevonden worden. Hiervoor ga je als volgt te werk.

1. Schrijf een functie LGP waaraan twee strings als argument moeten doorgegeven worden. Deze functie moet als resultaat de langste gemeenschappelijke prefix (LGP) van de twee gegeven strings teruggeven. Indien de gegeven strings geen gemeenschappelijke prefix hebben, dan moet een lege string als resultaat teruggegeven worden. De langste gemeenschappelijke prefix van de strings banaan en banana is bijvoorbeeld bana. Deze functie moet bij het vergelijken van de prefixen onderscheid maken tussen hoofdletters en kleine letters.
   
   Opmerking (terminologie): Een voorvoegsel bestaande uit één of meer letters vooraan een string noemen we een prefix van die string. Een achtervoegsel bestaande uit één of meer letters achteraan een string noemen we een suffix van die string. Zo is bio bijvoorbeeld een prefix van de string biotechnologie, en is technologie een suffix van diezelfde string.

2. Schrijf een functie LHD waaraan een string als argument moet doorgegeven worden. Deze functie moet als resultaat de langste herhaalde deelstring (LHD) van de gegeven string teruggeven. Merk op dat we voornamelijk geïnteresseerd zijn om deze functie te gebruiken om de langste herhaalde deelsequentie van een gegeven DNA sequentie (een string die enkel bestaat uit de letters A, C, G en T) te bepalen, maar dat deze functie meer algemeen uit elke string de langste herhaalde deelstring kan extraheren. Het algoritme dat je moet gebruiken om de LHD van een gegeven string te bepalen, werkt als volgt:

   1. Maak eerst een lijst met alle suffixen van de gegeven string. Zo moet voor de string banana bijvoorbeeld een lijst met de suffixen a, na, ana, nana, anana en banana opgebouwd worden. De volgorde waarin de suffixen in deze lijst geplaatst worden, is initieel niet belangrijk (zie volgende stap).

   2. Sorteer de suffixlijst alfabetisch. Dit zorgt ervoor dat suffixen met een gemeenschappelijke prefix na elkaar komen te staan. De gesorteerde suffixlijst van bovenstaand voorbeeld wordt dan: a, ana, anana, banana, na en nana.

   3. Bereken voor elk paar opeenvolgende suffixen in de gesorteerde suffixlijst de LGP (gebruik hiervoor de functie LGP). De langste van deze gemeenschappelijke prefixen is dan de LHD waarnaar we op zoek zijn. Indien er meerdere gemeenschappelijke prefixen zijn die het langst zijn, dan moet de eerste die gevonden wordt bij het overlopen van de paren (van links naar rechts) teruggegeven worden. Uit de gesorteerde suffixlijst a, ana, anana, banana, na en nana volgt onmiddellijk dat ana de LHD is van de string banana. Dit voorbeeld geeft meteen ook aan dat de herhalingen van een LHD elkaar gedeeltelijk kunnen overlappen.

Voorbeeld

>>> LGP('banaan', 'banana')
'bana'
>>> LGP('mango', 'mandarijn')
'man'
>>> LGP('perzik', 'perzik')
'perzik'
>>> LGP('appel', 'appelboom')
'appel'
>>> LGP('appelboom', 'appel')
'appel'
>>> LGP('appel', 'peer')
''
>>> LGP('pompelmoes', 'Pomelo')
''

>>> LHD('CAATCCGCCTGTATTAAGGTACGGCCTTTTGACTGAAGTT')
'GCCT'
>>> LHD('AGTGTGGGGCATGCCTATTGGCCACCTTGTAGGAGCCTTG')
'CCTTG'
>>> LHD('GACTAGCCGTCTACTTATTGAATCGCAGCATCATTTCGAG')
'ACT'
>>> LHD('GGCCCGTCGCGACATTTGAGCTAGTCAGCGATCTTTACCT')
'GCGA'
>>> LHD('TGCCCCGTCAACCTCTACTCATCTCGCTCTAAACTGTAAG')
'CTCTA'