Information Technology Reference
In-Depth Information
Nachbarn
Allel
in
A
in
B
zusammengefasst
1
3, 5
6, 4
3, 4, 5, 6
5
,7
2
5, 7
7, 5
3
6, 1
4, 7
1, 4, 6, 7
4
7, 6
1, 3
1, 3, 6, 7
1, 2
,6
5
1, 2
2, 6
6
4, 3
5, 1
1, 3, 4, 5
2
,3,4
7
2, 4
3, 2
Tabe l l e 11 . 4 : Be i sp i e l e i ne r Kant ent abe l l e für d i e Kant enrekomb i na t i on
Kanten zu seinen Nachbarn im Chromosom. Die Kanten der Graphen zweier Chro-
mosomen werden gemischt. Daher rührt auch der Name dieses Verfahrens, das die
Nachbarschaftsinformation erhält.
Das Vorgehen dieses Verfahrens läuft in zwei Schritten ab. Zuerst muss man eine
Kantentabelle
aufbauen. Dafür listet man zu jedem Allel seine Nachbarn (in beiden
Eltern) auf. Gegebenenfalls sind das erste und das letzte Gen des Chromosoms be-
nachbart. Hat ein Allel in beiden Eltern den gleichen Nachbarn (wobei die Seite ir-
relevant ist), so führt man diesen Nachbar nur einmal auf, dafür aber markiert. Der
zweite Schritt ist der Aufbau eines Nachkommen. Hierbei wählt man das erste Al-
lel zufällig aus einem der beiden Eltern. Ein ausgewähltes Allel muss dann aus der
Kantentabelle (d. h. aus den Listen der Nachbarn der Allele) gelöscht werden. Das
jeweils nächste Allel wählt man aus den noch nicht gelöschten Nachbarn des voran-
gehenden, wobei die folgende Prioritätsliste gilt:
1. markierte (d. h. doppelt auftretende) Nachbarn,
2. Nachbarn mit kürzester Nachbarschaftsliste (wobei markierte Nachbarn ein-
fach zählen),
3. zufällige Auswahl eines Nachbarn.
Man kann analog einen zweiten Nachkommen aus dem ersten Allel des anderen
Elter erzeugen. Dies wird jedoch meistens nicht gemacht.
Als Beispiel zur Kantenrekombination sollen die beiden Chromosomen
A:
631 5 274
und
B:
3 725614
miteinander verknüpft werden. Dafür fassen wir beide Chromosomen als Ring auf
(d. h. das erste und das letzte Gen sind benachbart). Die zugehörige Kantentabelle ist
in Tabelle 11.4 dargestellt. In
A
ist der linke Nachbar der 6 die 4, der rechte Nachbar
der 4 die 6; in
B
analog. In beiden Chromosomen stehen 5, 2 und 7 nebeneinander.
Diese Nachbarschaftsinformation (zeigt sich in Markierungen) sollte, soweit es mög-
lich ist, erhalten werden.
In Tabelle 11.5 verdeutlichen wir den Aufbau eines Nachkommen. Wir gehen
davon aus, dass mit dem erstemAllel des Chromosoms
A
,alsoder6begonnenwird.
Danach streicht man die 6 aus allen Nachbarschaftslisten (dritte Spalte). Da unter
