Inleiding
Drosophila Melanogaster en Drosophila Miranda zijn fruitvliegsoorten waarvan het genoom goed bestudeerd is. Hiervoor geldt dat de genen van het genoom voor beide soorten identiek zijn, en dat het verschil ligt in de volgorde. Mutaties in het genoom vinden alleen plaats doordat gedeelten ervan omkeren , en zo de genvolgorde veranderen.
Formeler laat de opdracht zich als volgt omschrijven: een fruitvliegengenoom is een rijtje van 25 genen, die we voor het gemak van hun naam ontdaan en hebben en genummerd hebben van 1 tot 25. Een mutatie vindt plaats door een willekeurig subrijtje van een willekeurige lengte te inverteren. Vind een reeks van mutaties waardoor het genoom van fruitvlieg 1 in fruitvlieg 2 verandert. Hoe korter de reeks hoe beter.
Opdracht
a) Schrijf een algoritme dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert, met zo min mogelijk mutaties.
b) Evalueer je algoritme op basis van een zelfgemaakte test-set met 10000 random-volgorde genomen van lengte 10, 25, 50, 100. Baseer je evaluatie op het benodigd aantal mutaties om de genen op volgorde te krijgen.
c) Schrijf een algoritme dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert, met zo min mogelijk verplaatste genen. Dat betekent dat de omkeer-mutaties gemiddeld zo klein mogelijk moeten zijn.
d) Evalueer dit algoritme op basis van je zelfgemaakte test-set. Baseer je evaluatie op het aantal mutaties en het aantal verplaatste genen. Zoek uit welk mutatietraject nodig is om een Melanogaster in een Miranda te doen veranderen. Het is mogelijk dat er meerdere antwoorden zijn; bewaar ze allemaal.
Advanced
Op wat voor genomen gaat je algoritme een korte mutatiereeks vinden? Op welke een lange? Motiveer je antwoord.
