From Daan
Jump to: navigation, search
m (Protected "Fruitvliegen" (‎[edit=autoconfirmed] (indefinite) ‎[move=autoconfirmed] (indefinite)))
 
(14 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
[[Image:Fruitvliegen2.jpg|thumb|right]]
 +
  
[[Image:Fruitvliegen2.jpg|thumb|right]]
 
  
 
==Inleiding==
 
==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.
 
  
 +
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 reeks van achtereenvolgende 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==
 +
 +
 +
[[Image:tweegenomen.gif|thumb|border|right|middle|upright=1.5||| Fig.1: Genomen van D.Melanogaster (boven) en D.Miranda (onder). Beide genomen bestaan uit dezelfe genen, alleen de volgorde verschilt.]]
  
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.  
+
[[Image:mutatie.gif|thumb|border|right|middle|upright=1.5||| Fig.2: Mutatie zoals die plaats vindt binnen de soort Drosophila. Een gedeelte van het genoom keert ineens om.]]
  
  
==Opdracht==
+
a) Bepaal een sequentie van mutaties dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert. Bepaal ook de grenzen van de oplossingskwaliteit en de toestandsruimte.
 +
 
  
[[Image:tweegenomen.gif|thumb|border|right|middle|upright=2|||Genomen van D.Melanogaster (boven) en D.Miranda (onder). Beide genomen bestaan uit dezelfe genen, alleen de volgorde verschilt.]]
+
b) Vind de "kortste" sequentie van mutaties dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert. Als er meerdere kortste oplossingen zijn, vergelijk ze dan met elkaar.
  
[[Image:mutatie.gif|thumb|border|right|middle|upright=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.  
+
Er is een theorie, die stelt dat kleine mutaties waarschijnlijker zijn dan grote mutaties. Een manier omdat te modelleren is om mutatiepunten te geven aan mutaties. Het aantal punten is de lengte van het stuk dat omkeert.
  
  
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, in zo min mogelijk mutatiepunten.
  
  
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) Een alternatieve formule geeft ½n<sup>1.3</sup> mutatiepunten voor mutaties van lengte n. Grote mutaties worden zo dus "nog" onwaarschijnlijker. Zoek wederom naar een mutatiesequentie die het genoom van D. Melanogaster in het genoom van D. Miranda verandert in zo min mogelijk mutatiepunten.
  
  
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.
+
e) Maak een test-set met 100 random-volgorde genomen van lengte 25. Sorteer ze met je algoritmes en probeer zicht te krijgen op het minimale aantal mutatiepunten dat nodig is om een genoom gesorteerd te krijgen. Probeer wederom een boven- en ondergrens vast te stellen als je kunt.
 +
  
 
==Advanced==
 
==Advanced==
  
Op wat voor genomen gaat je algoritme een korte mutatiereeks vinden? Op welke een lange? Motiveer je antwoord.
+
 
 +
f) Probeer te formaliseren wat voor genomen ''veel'' mutatiestappen nodig hebben om gesorteerd te worden met a), en wat voor genomen ''weinig'' stappen.
 +
 
 +
 
 +
g) Als er bij b) meerdere kortste paden gevonden zijn, willen we graag weten wat de overeenkomst daartussen is. Ingewikkeld!
 +
 
  
 
==Familiestamboom==
 
==Familiestamboom==
 +
  
 
Er is een philogenie (familiestamboom) van de familie fruitvlieg uitgetekend, zie de figuur.  
 
Er is een philogenie (familiestamboom) van de familie fruitvlieg uitgetekend, zie de figuur.  

Latest revision as of 21:38, 16 October 2018

Fruitvliegen2.jpg


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 reeks van achtereenvolgende 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) Bepaal een sequentie van mutaties dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert. Bepaal ook de grenzen van de oplossingskwaliteit en de toestandsruimte.


b) Vind de "kortste" sequentie van mutaties dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert. Als er meerdere kortste oplossingen zijn, vergelijk ze dan met elkaar.


Er is een theorie, die stelt dat kleine mutaties waarschijnlijker zijn dan grote mutaties. Een manier omdat te modelleren is om mutatiepunten te geven aan mutaties. Het aantal punten is de lengte van het stuk dat omkeert.


c) Schrijf een algoritme dat het genoom van D. Melanogaster in het genoom van D. Miranda verandert, in zo min mogelijk mutatiepunten.


d) Een alternatieve formule geeft ½n1.3 mutatiepunten voor mutaties van lengte n. Grote mutaties worden zo dus "nog" onwaarschijnlijker. Zoek wederom naar een mutatiesequentie die het genoom van D. Melanogaster in het genoom van D. Miranda verandert in zo min mogelijk mutatiepunten.


e) Maak een test-set met 100 random-volgorde genomen van lengte 25. Sorteer ze met je algoritmes en probeer zicht te krijgen op het minimale aantal mutatiepunten dat nodig is om een genoom gesorteerd te krijgen. Probeer wederom een boven- en ondergrens vast te stellen als je kunt.


Advanced

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


g) Als er bij b) 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.

Philo.jpg
.


Terug

Terug naar de Heuristieken hoofdpagina.