Als één van de laatste stappen van genetische recombinatie, kunnen twee homologe chromosomen tijdens de meiose genetisch materiaal uitwisselen in een proces dat synapsis genoemd wordt. Door deze chromosomale crossover ontstaan gerecombineerde chromosomen. Crossover komt meestal voor wanneer overeenkomstige regio’s van overeenkomstige chromosomen breken en zich daarna terug aanhechten aan het andere chromosoom.

Een theoretische beschrijving van crossover werd geïntroduceerd door Thomas Hunt Morgan, die zich daarbij liet inspireren op het werk van de Belgische professor Frans Alfons Janssens van de Katholieke Universiteit Leuven. Deze laatste had het fenomeen reeds in 1909 beschreven en noemde het chiasmatypie.

Opgave

We stellen een chromosoom voor als een reeks (Array) van strikt stijgende gehele getallen (Number). Elk getal is dus groter dan het voorgaande getal. De punten waar twee chromosomen kunnen openbreken — en waar zich dus crossover kan voordoen — worden aangegeven door de gemeenschappelijke getallen in de twee corresponderende reeksen. Dit wordt hieronder geïllustreerd, waarbij crossover kan voorkomen waar de twee chromosomen elkaar raken.

De chromosomen kunnen op de volgende manier doorlopen worden:

1. Als startpunt kan het begin (de linkerkant) van één van beide chromosomen gekozen worden.

2. Vanaf elk punt kan vooruit (naar rechts) gestapt worden.

3. Bij een crossoverpunt heb je de keuze om verder te stappen op hetzelfde chromosoom, of over te schakelen op het andere chromosoom.

Gevraagd wordt:

• Schrijf een functie crossoverpunten waaraan twee chromosomen (Array) moeten doorgegeven worden. De functie moet teruggeven hoeveel crossoverpunten (Number) er zijn tussen deze chromosomen.

• Schrijf een functie maximaleSom waaraan twee chromosomen (Array) moeten doorgegeven worden. De functie moet de maximale som (Number) bepalen van alle paden die op de hierboven beschreven manier kunnen doorlopen worden. In het voorbeeld wordt de maximale som 450 bereikt door het volgende pad te doorlopen: 3 + 5 + 7 + 9 + 20 + 25 + 44 + 47 + 55 + 56 + 57 + 60 + 62

De maximale som wordt gevonden door de maximale deelsommen te bepalen van de fragmenten vóór het eerste crossoverpunt, tussen opeenvolgende crossoverpunten, en na het laatste crossoverpunt. Merk op dat het mogelijk is dat twee deelsommen gelijk zijn indien de eindpunten zelf crossoverpunten zijn, of indien twee crossoverpunten elkaar onmiddellijk opvolgen zonder tussenliggende punten.

Algoritme

Om de crossoverpunten te vinden, kan je gebruikmaken van het feit dat de getallen in de twee gegeven reeksen strikt stijgend zijn. Je kunt beide reeksen dan tegelijkertijd van links naar rechts doorlopen, waarbij je voor elke reeks afzonderlijk bijhoudt op welke positie je je momenteel bevindt. Ga telkens één stap vooruit in de reeks waar op de huidige positie het kleinste getal staat. Als je op de huidige positie in beide reeksen hetzelfde getal aantreft, dan heb je een crossoverpunt gevonden. Tijdens het doorlopen van beide reeksen kan je meteen ook al de deelsommen voor, tussen, en na de crossoverpunten bepalen.

Voorbeeld

> chromosoom1 = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62]
> chromosoom2 = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100]
> crossoverpunten(chromosoom1, chromosoom2)
4
> maximaleSom(chromosoom1, chromosoom2)
450

> chromosoom1 = [-5, 100, 1000, 1005]
> chromosoom2 = [-12, 1000, 1001]
> crossoverpunten(chromosoom1, chromosoom2)
1
> maximaleSom(chromosoom1, chromosoom2)
2100

Bronnen

• Morgan TH (1916). A Critique of the Theory of Evolution¹. Princeton, NJ, Princeton University Press.