SPOJ.com - Problem PROG0366

PROG0366 - Chromosomal crossover

As one of the last steps of genetic recombination two homologous chromosomes can exchange genetic material during meiosis in a process that is referred to as synapsis. Because of this chromosomal crossover, recombined chromosomes arise. Crossover usually occurs when corresponding regions of corresponding chromosomes break and thereafter attach back to the other chromosome.

Fig. 64. Scheme to illustrate a method of crossing over of the chromosomes. Illustration made by Thomas Hunt Morgan (1916).

Fig. 65. Scheme to illustrate double crossing over of the chromosomes. Illustration made by Thomas Hunt Morgan (1916).

A theoretical description of crossover was introduced by Thomas Hunt Morgan, who was inspired by the work of the Belgian Professor Frans Alfons Janssens of the University of Leuven. The latter had already described his chiasmatype theory in 1909.

Assignment

In this assignment, we represent a chromosome as a list or a tuple of strictly increasing integers (each number is larger than the previous number). The points where two chromosomes can break open - and where a crossover can occur - are indicated by the common numbers in the two corresponding lists or tuples. This is illustrated in the figure below, where crossover can occur where the two chromosomes meet.

Two chromosomes [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62] en [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100], of which the crossover points are in bold. At the top and at the bottom the partial sums before, between and after the crossover points are shown for the first and the second chromosome, respectively. The maximum partial sums are rendered in bold.

The chromosomes can be navigated through the following way:

As a starting point the beginning (the left side) of one of the two chromosomes can be selected.
Stepping forward (to the right) is possible from any point.
At a crossover point, you have the choice to continue on the same chromosome, or switch to the other chromosome.

Asked:

Write a function crossoverpoints to which two chromosomes must be passed. The function should return how many crossover points there are between these chromosomes.
Write a function maximumSum to which two chromosomes must be passed. The function should determine the maximum sum of all paths that can be followed in the manner described above. In the example above, the maximum sum of 450 is achieved by going through the following path:

3 + 5 + 7 + 9 + 20 + 25 + 44 + 47 + 55 + 56 + 57 + 60 + 62

Algorithm

In order to find the crossover points, you can use the fact that the numbers in the two data frames are strictly increasing. In that way, you can go through the lists simultaneously from left to right, while you keep track of your position for each list separately. Always move one step ahead in the list from where at the current position is the smallest number. If you find a similar number on the current position in both lists, then you have found a crossover point. While running through both lists, you can also determine the partial sums before, between, and after the crossover points.

Example

>>> chromosome1 = [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62]
>>> chromosome2 = [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100]
>>> crossoverpoints(chromosome1, chromosome2)
4
>>> maximumSum(chromosome1, chromosome2)
450

>>> chromosome1 = [-5, 100, 1000, 1005]
>>> chromosoom2 = [-12, 1000, 1001]
>>> crossoverpoints(chromosome1, chromosome2)
1
>>> maximumSum(chromosome1, chromosome2)
2100

Source

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

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.

Fig. 64. Scheme to illustrate a method of crossing over of the chromosomes. Illustration made by Thomas Hunt Morgan (1916).

Fig. 65. Scheme to illustrate double crossing over of the chromosomes. Illustration made by Thomas Hunt Morgan (1916).

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

In deze opgave stellen we een chromosoom voor als een lijst of een tuple van strikt stijgende gehele getallen (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 lijsten of tuples. Dit wordt geïllustreerd in onderstaande afbeelding, waarbij crossover kan voorkomen waar de twee chromosomen elkaar raken.

Twee chromosomen [3, 5, 7, 9, 20, 25, 30, 40, 55, 56, 57, 60, 62] en [1, 4, 7, 11, 14, 25, 44, 47, 55, 57, 100], waarbij de crossoverpunten in het vet weergegeven worden. Bovenaan en onderaan worden de deelsommen voor, tussen en na de crossoverpunten weergegeven voor respectievelijk het eerste en het tweede chromosoom. De maximale deelsommen zijn hierbij in het vet weergegeven.

De chromosomen kunnen op de volgende manier doorlopen worden:

Als startpunt kan het begin (de linkerkant) van één van beide chromosomen gekozen worden.
Vanaf elk punt kan vooruit (naar rechts) gestapt worden.
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 moeten doorgegeven worden. De functie moet teruggeven hoeveel crossoverpunten er zijn tussen deze chromosomen.
Schrijf een functie maximaleSom waaraan twee chromosomen moeten doorgegeven worden. De functie moet de maximale som bepalen van alle paden die op de hierboven beschreven manier kunnen doorlopen worden. In het bovenstaand 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

Algoritme

Om de crossoverpunten te vinden, kan je gebruik maken van het feit dat de getallen in de twee gegeven lijsten strikt stijgend zijn. Je kunt beide lijsten dan tegelijkertijd van links naar rechts doorlopen, waarbij je voor elke lijst afzonderlijk bijhoudt op welke positie je je momenteel bevindt. Ga telkens één stap vooruit in de lijst waar op de huidige positie het kleinste getal staat. Als je op de huidige positie in beide lijsten eenzelfde getal aantreft, dan heb je een crossoverpunt gevonden. Tijdens het doorlopen van beide lijsten 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