Fruitvliegen

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, waarvan voor het gemak de cryptische namen hebben vervangen door nummers van 1 tot 25. Een mutatie vindt plaats door een willekeurig subrijtje van een willekeurige lengte om te keren. Vind een reeks van mutaties waardoor het genoom van fruitvlieg 1 in fruitvlieg 2 verandert. Hoe korter de reeks hoe beter.

Opdracht

Genomen van D.Melanogaster (boven) en D.Miranda (onder). Beide genomen bestaan uit dezelfe genen, alleen de volgorde verschilt.

Mutatie zoals die plaats vindt binnen de soort Drosophila. Een gedeelte van het genoom keert ineens om.

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 opgetelde grootte van de omkeer-mutaties zo klein mogelijk moet 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

De advanced-sectie bestaat uit twee opties. Als er meerdere kortste paden gevonden zijn, willen we graag weten wat de overeenkomst daartussen is. Als er maar een is, willen we weten op wat voor genomen je algoritme een korte mutatiereeks gaat vinden. Motiveer hoedanook je antwoord.

Familiestamboom

Er is een philogenie (familiestamboom) van de familie fruitvlieg uitgetekend, zie de figuur.

.

Terug

Terug naar de Heuristieken hoofdpagina.