Fruitvliegen

Inleiding

Drosophila Melanogaster en Drosophila Miranda zijn fruitvliegsoorten waarvan het genoom goed bestudeerd is. Voor deze twee soorten geldt dat de genen voor beide soorten identiek zijn, maar wel in een andere volgorde staan. Mutaties in de genenrij van de Drosophila vinden alleen plaats doordat subrijen ervan in hun geheel omkeren (fig.2 ). In deze opdracht is het zaak te achterhalen welke sequentie van mutaties de ene fruitvliegensoort in de andere heeft doen veranderen. Misschien zijn er meerdere reeksen mogelijk; in dat geval willen we de meest plausibele reeks vinden: die met de kleinste mutaties en die met de minste mutaties.

Opdracht

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

Fig.2: 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) Maak een test-set met 100 random-volgorde genomen van lengte 25. Sorteer ze met je algoritme uit onderdeel a) en probeer zicht te krijgen op het minimaal en maximaal aantal benodigde mutaties om een genoom gesorteerd te krijgen. Probeer een boven- en ondergrens vast te stellen als je kunt.

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) Maak een test-set met 100 random-volgorde genomen van lengte 25. Sorteer ze met je algoritme uit onderdeel c) en probeer zicht te krijgen op het minimaal en maximaal aantal verplaatsende genen dat nodig is om een genoom gesorteerd te krijgen. Probeer wederom een boven- en ondergrens vast te stellen als je kunt.

e) Probeer te formaliseren wat voor genomen veel stappen nodig hebben om gesorteerd te worden met a), en wat voor genomen weinig stappen.

Advanced

f) Probeer te formaliseren wat voor genomen veel verplaatsingen nodig hebben met c) en wat voor weinig.

g) Als er bij a) meerdere kortste paden gevonden zijn, willen we graag weten wat de overeenkomst daartussen is. Ingewikkeld!

Familiestamboom

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

.

Terug

Terug naar de Heuristieken hoofdpagina.