Genome Rearrangements Zentrum für Bioinformatik der Universität des Saarlandes WS 2001/2002

Genome Rearrangements

Zentrum für Bioinformatikder Universität des Saarlandes

WS 2001/2002


Ende der achtziger Jahre haben Jeffrey Palmer und seine Kollegen durch Vergleich dermitrochondralen Genome von Pflanzen ein bemerkenswertes Muster evolutionärer Ent-wicklung entdeckt.

1 2 3 4 5B. oleracea (Kohl)

1 -5 4 -3 2

B. campestris (Steckrübe)

Viele Gene sind zu 99 % identisch nur ihre Reihenfolge (und ihre Richtung) haben sichgeändert. Ganze Blöcke von Genen wurden umsortiert und eventuell wurde auch die Richtung der Blöcke geändert.

Genome Rearrangement:

Finde eine minimale Reihe von Transformationen, die ein Genom (oder Chromosom)in ein anderes Genom (oder Chromosom) überführt.

Die Standardtransformation ist die Umkehrung (Reversal). Ein Reversal kehrt die Richtung eines oder mehrerer Blöcke um.

1 -5 -4 -3 -2

1 -5 4 -3 -2


1 2 3 4 5 6 7 8Maus (X Chromosom)

-4 -6 1 4 2 -3 5 8

Mensch (X Chromosom)

Da sich die Gene auf den X Chromosomen der Säugetiere im Laufe der Evolution kaum geändert haben (Ohno [1967]), kann man durch das Studium der X Chromsomen und der vorliegendenRearrangements die Evolution der Säugetiere in den letzten 125 Millionen Jahren studieren.

Herpes Viren haben bis zu 200 Gene. Die Genome dieser Viren entwickeln sich so schnell weiter,dass man kaum mehr eine Ähnlichkeit zwischen den „verwandten“ Genen verschiedener HerpesArten feststellen kann. Aber alle Arten weisen sieben Blöcke von Genen auf, die in den ver-schiedenen Viren unterschiedlich angeordnet sind.


David Sankoff hat den folgenden Ansatz zum Vergleich der Genreihenfolge formuliert:

Sorting by Reversals:

Die Reihenfolge der Gene von zwei Organismen wird durch zwei Permutationen repräsentiert:

= 1 2 ... n = 1 2 ... n

Ein Reversal ( i, j) eines Intervals [i,j] ist die Permutation

njiijji

njjjiii

)...1()1)...(1()1...(12

)...1()1)...(1()1...(12

= 1 2 ... i-1 i i+1... j-1 j j+1 ...n ( i, j) = 1 2 ... i-1 j j-1... i+1 i j+1 ...n

Reversal Distance Problem:

Gegeben zwei Permutationen und . Bestimme eine minimale Serie von Reversals 1 2... t ,so dass gilt:

1 2... t =

Die minimale Zahl d( ) von Reversals, die eine Permutation in die Identität überführt, nennt man die Reversal-Distanz von . Identität = (1 2 3 ... n).


Pancake Flipping Problem:

Bill Gates (ein „undergraduate“ Student in Harvard) und Christos Papadimitriou machten dieersten Versuche dieses Problem zu lösen (Gates & Papadimitriou [1979]). Sie zeigten, dass derPräfix-Reversal-Diameter dpräf(n) = max dpräf() der symmetrischen Gruppe mit n Elementen kleiner gleich 5/3(n+1) ist und für unendlich viele n größer gleich 17/16n ist.

Die minimale Zahl dpräf( ) von Präfix-Reversals (1,i) , die eine Permutation in die Identität überführt, nennt man die Präfix-Reversal-Distanz von . Identität = (1 2 3 ... n).

Bezeichnung: Falls |i-j| = 1, dann schreiben wir i~j .

Definition: Man nennt ein Paar (i , i+1) adjazent, falls i ~ i+1.

Falls |i-j| 1, dann schreiben wir i~j .

Man nennt ein Paar (i , i+1) einen Haltepunkt, falls i ~ i+1

Da die Identität keine Haltepunkte hat und da jedes Reversal bestenfallszwei Haltepunkte beseitigen kann, gilt:

2

)()(

bd wobei b() die Zahl der Haltepunkte von ist.


Der Haltepunkt-Graph

einer Permutation = 0 1 ...n n+1 ist ein Graph mit n+2 Knoten V = {0 ,1, ...,n ,n+1}

Definition:

Man nennt einen Rundgang in diesem Graphen alternierend, wenn jedes aufeinander folgendePaar von Kanten im Rundgang aus einer blauen und einer roten Kante besteht.( ... rot, blau, rot, blau, rot, ....) Wenn wir im folgenden Abschnitt von einem Rundgang sprechen, so ist immer ein alternierender Rundgang gemeint.

und gefärbten Kanten: Die benachbarten Knoten i und i+1 werden durch blaue Kanten verbunden.

0 2 3 1 4 6 5 7

Jedes Knotenpaar (i , j) mit i ~ j wird über eine rote Kante miteinander verbunden.

Die Knoten in Haltepunkt-Graphen sind balanciert, d.h., #rote Kanten (v) = #blauen Kanten (v).

Es existiert ein alternier. Euler-Rundgang (d.h. der Rundgang geht genau einmal über jede Kante).

Der Graph kann in kanten-disjunkte alternierende Rundgänge zerlegt werden.


0 2 3 1 4 6 5 7

Der Graph kann in kanten-disjunkte alternierende Rundgänge zerlegt werden.

0 2 3 1 4 6 5 7

0 2 3 1 4 6 5 7

0 2 3 1 4 6 5 7

0 2 3 1 4 6 5 7

Zerlegung in kanten-disjunkte alternierendeRundgänge.


Wir interessieren uns für die Zerlegung eines Haltepunkt-Graphen in maximal viele Rundgänge.

0 1 2 3 4 5 6 7

Die Identität kann in n+1 Rundgänge zerlegt werden. Sei eine Permutation. Der Haltepunkt-Graph von G() habe eine maximale Rundgang-Zerlegung der Größe c().

Wir werden im folgenden Abschnitt zeigen, dass

c() – c() 1

Es folgt dann:

d() n+1 – c().

Satz (Bafna & Pevzner [1996])

Für jede Permutation gilt:

Satz:

Die Anwendung eines beliebigen Reversals auf die maximale Zahl von Rundgängen um höchstens einen Rundgang vergrößert, d.h.

Beweis: Siehe nächste Seite!


Beweis des Satzes: Ein beliebiges Reversal (i,j) verändert den Graphen G() in vier Knoten.

Die schwarzen KantenDEL={(i-1, i), (j, j+1)}werden ersetzt durchADD={(i-1, j), (i, j+1)}

(1) Gehören die Kanten in ADD zum gleichen Rundgang einer maximalen Zerlegung von G(),so erhalten wir durch Löschen dieses Rundgangs eine Menge von c() –1 Rundgängen von (in)G(). Folglich ist in diesem Fall c() c() –1.

ADD

(1,2)0 1 2 3 4 5 6 7

0 2 1 3 4 5 6 7

0 1 2 3 4 5 6 7

0 2 3 1 4 6 5 7

(5,6)

0 2 3 1 4 5 6 7

DEL

ADD


Beweis des Satzes: Ein beliebiges Reversal (i,j) verändert den Graphen G() in vier Knoten.

Die schwarzen KantenDEL={(i-1, i), (j, j+1)}werden ersetzt durchADD={(i-1, j), (i, j+1)}

(1) Gehören die Kanten in ADD zu zwei Rundgängen R1 und R2 der max. Zerlegung von G (),so erhalten wir durch Löschen dieser Rundgänge eine Menge von c() –2 Rundgängen von (in)G()\(R1R2). Offensichtlich bildet die Kantenmenge (R1 R2 DEL)\ADD

0 2 1 3 4 5 6 7

0 2 3 1 4 6 5 7

(5,6)

0 2 3 1 4 5 6 7

DEL

ADD

ADD

(1,2)

0 1 2 3 4 5 6 7

0 2 1 3 4 5 6 7

R1 R2

einen balanciertenTeilgraphenvon G(), der wenigstens einen weiteren Rundgang enthält.

c() c() - 2+ 1

c() c() - 1


Erwartete Reversal-Distanz:

Für eine beliebige Permutation Sn betrachten wir alle Rundgänge in einer max. Zerlegung. Sei ci() die Zahl der Rundgänge mit Länge i in der max. Zerlegung (die nicht 0 und n+1 besuchen). Sei 2 die Zahl der Rundgänge in der max. Zerlegung, die entweder 0 oder n+1 besuchen.

Es gilt:

)()()1(2

2

n

iicc

Wir betrachten nun alle Rundgänge deren Länge mindestens k ist. Die Zahl dieser Rundgänge ist

)()(1

2

k

iicc

Da der Haltepunkt-Graph genau 2(n+1) Kanten hat da die Rundgänge kanten-disjunkt sind, gilt:

)1(2 nk

)()1(21

)()(1

2

1

2

k

ii

k

ii icn

kcc

)1(2 nk

)()()1(21

)(1

2

k

iicikn

kc

2)()(1

)1)(2

1()(1

2

k

iicik

kn

kd

d() (n+1) – c()

)1(2 nk


Erwartete Reversal-Distanz:

Für eine beliebige Permutation Sn bezeichnen wir die erwartete Zahl von Rundgängender Länge i in der maximalen Zerlegung von G() mit E(ci()).

Lemma:

icE

i

i

2))((

Beweis:

Wir nehmen an, dass xk = xl ist.

Ein Rundgang der Länge i = 2t enthält t blaue Kanten von der Form

{(x‘t , x1), (x‘1 , x2), (x‘2 , x3), .... , (x‘t-1 , xt) } mit xj ~ x‘j

Wir betrachten die Menge x1, x2 , .... , xt und zeigen, dass für jeden Rundgang in einer max.Zerlegung gilt, dass alle xi verschieden sind (xi xj).

(x‘t , x1) .... (x‘k-1 , xk) (x‘k , xk+1) .... (x‘l-1 , xl)(x‘l , xl+1) .... (x‘t-1 , xt)

Dann ist die Zerlegung nicht maximal, da wir einen weiteren Rundgang (siehe Bild) zurZerlegung hinzufügen könnten und eine Menge von balancierten Knoten übrigbleiben würde(weitere Rundgänge). Wir erhalten also einen Widerspruch zur Annahme, dass xk = xl.

=

Fortsetzung des Beweises auf der nächsten Seite.


da die Elemente der t Paare nebeneinander gesetzt werden müssen und man daher nur die möglichen Permutationen von (n-t) Elemente betrachten muß (=>(n-t)!)und man für jedes Paar zwei mögliche Reihenfolgen hat => 2t.

Für jede mögliche Auswahlgilt: Es existieren für jedes xi (höchstens) zwei Nachbarn x‘i.

Es gibt n!/(n-t)! mögliche Auswahlen von sortierten Menge x1, ... , xt.

2t n!/(n-t)! mögliche Rundgänge der Länge 2t.

Man beachte, dass wir bei dieser Zählung jeden Rundgang 2t mal zählen.

(2t /2t)(n!/(n-t)!) mögliche Rundgänge der Länge 2t.

Man wähle einen beliebigen 2t-Rundgang. Die Zahl der Permutationen, in denen dieser Rund-gang höchtens auftreten kann, kann wie folgt abgeschätzt werden:

2t(n-t)!

Die Wahrscheinlichkeit, dass irgend ein 2t-Rundgang in einer zufällig gewählten Permutationauftritt, kann daher wie folgt abgeschätzt werden:

!

)!(2

n

tnp

t

tttntn

ntn

n

tncEcE

itt

tRundgängealle

t

ti 2

2

2

2

)2(!)!(

!)!(2

!

)!(2))(())((

22

22


Satz (Bafna & Pevzner [1996])

n

nn

dE

)

)log(log(

31))((

Beweis:

2)()(1

)1)(2

1()(1

2

k

iicik

kn

kd

2))(()1)(2

1())((1

2

k

iicEn

kdE

2)()1)(2

1()(1

2

k

iicn

kd

42

)1)(2

1(1

4

k

i

i

in

k

484212)1)(2

1(1

0

k

i

ink

821)12()2

1(2

k

kk

nn k

k

nn 2

2

Fortsetzung des Beweises auf der nächsten Seite.

42)1)(2

1(1

4

k

i

ink


Wähle

))log(

log(n

nk

k

k

nndE 2

2))((

k

nk 2

n

nn

dE ))

)log(log(

31())((

Bafna und Pevzner geben ferner die folgende Abschätzung an:

nn

dE

)log(

5.41))((


Satz (Caprara [1997])

Das Reversal-Distanz-Problem für vorzeichenlose Permutationen ist NP-hard.

Satz (Kaplan, Shamir, Tarjan [1997])

Es existiert ein Algorithmus mit Laufzeit O(n2), der die optimale Folge von Reversals (Reversal-Distanz) für jede vorgegebene Permutation mit Vorzeichen (signed permutation)bestimmt.

1 2 3 4 5 6 7 8Maus (X Chromosom)

-4 -6 1 4 2 -3 5 8

Mensch (X Chromosom)


Definition:

Ein Block einer Permutation ist ein maximales Teilinterval von , das keine Haltepunkte enthält.

1567432Ein Block wird wachsend genannt, wenn die Zahlenwerte im Block wachsen. Der Block wirdfallend genannt, wenn die Zahlenwerte vom Anfang zum Ende hin im Block kleiner werden.Ein Block, der nur aus einer Zahl besteht, wird auch fallend genannt.

Sei eine Permutation, die einen fallenden Block (gelb markiert) enthält:

..... i-1 i i+1 ..... i+1 i - 1 und i+1 i + 1

Haltepunkt

Es existiert ein weiterer Haltepunkt zwischen der Zahl . i - 1Unter der Annahme, dass ..... i-1 i der fallende Block in mit der kleinsten Zahl i am Endedes Blocks ist, gilt: und dem rechten Nachbarn der Zahl i – 1.

..i i+1 .. (j = i-1) j+1 ..Fall1:

Haltepunkte

..i (j = i-1) .... i+1j+1 ..

Haltepunkt

Fall2: .. (j = i-1) j+1 .. i i+1.

?

.. (j = i-1) i .... j+1i+1 ..


Lemma:

Falls eine Permutation einen fallenden Block enthält, dann existiert ein Reversal, das die Zahl der Haltepunkte um wenigstens einen Haltepunkt verkleinert.

Beweis: Siehe vorhergehende Seite.

Sei eine Permutation, die keinen fallenden Block enthält.

Sei eine Permutation, die nicht die Identität ist und keine fallenden Blöcke enthält, danngibt es ein Reversal, das nicht die Zahl der Haltepunkte ändert und einen fallenden Blockder Länge größer gleich 2 produziert.

Jeder Block ist steigend und besteht daher aus mindestens zwei aufeinander folgenden Zahlen. Falls nicht die Identitätist, so gibt es an jedem Ende eines Blockes einen Haltepunkt. Dreht man einen solchen steigenden Block um, so erhält man einen fallenden Block und die Zahl der Haltepunkteändert sich nicht.

Lemma:

Heuristik 1:

Solange es einen Haltepunkt in der Permutation gibt, führe man die folgenden Operationen aus:

Gegeben eine Permutation .

• Falls es mindestens einen fallenden Block gibt, dann finde einen, dessen Umkehrung (Reversal) die Zahl der Haltepunkte reduziert und drehe ihn um.

• Falls es keinen fallenden Block gibt, dann finde einen steigenden Block und drehe ihn um (Reversal).


Satz:

Die vorhergehende Heuristik (1) benötigt im schlimmsten Fall 2b() Reversals, um einebeliebige Permutation in die Identität zu überführen. Hierbei ist b( ) die Zahl der Halte-punkte von . Daher ist die Zahl der von der Heuristik verwendeten Reversals immer kleinergleich 4 x d(), wobei d() die Reversal-Distanz (die optimale Zahl von Reversals) ist.

Beweis: Siehe vorhergehende Seite und siehe Seite 5:d() b()/2, wobei b() die Zahl der Haltepunkte ist.

Lemma:Sei eine Permutation mit einem fallenden Block. Falls es kein Reversal gibt, das die Zahl derHaltepunkte verkleinert und einen anderen fallenden Block zurücklässt (oder produziert), danngibt es ein Reversal in , das die Zahl der Haltepunkte um zwei verkleinert.

Beweis:

und dem rechten Nachbarn der Zahl i – 1.Es existiert ein weiterer Haltepunkt zwischen der Zahl i - 1Sei ..... i-1 i der fallende Block in mit der kleinsten Zahl i am Ende des Blocks:

..i i+1 .. (j = i-1) j+1 ..Fall1:

Haltepunkte

..i (j = i-1) .... i+1j+1 ..

Haltepunkt

Fall2: .. (j = i-1) j+1 .. i i+1.

?

.. (j = i-1) i .... j+1i+1 ..

Es existiert ein fallenderBlock ..... i (j = i-1)... !

(j = i-1) muß links von j

liegen!


da andernfalls das Reversal des Intervals von i – 1 bis i die Zahlder Haltepunkte reduzieren würde und den fallenden Block mit k zurücklassen würde.

Mit einem symmetrischen Argument kann man zeigen, dass k + 1 rechts von k liegen muß. Sei ..... k k+1 .... der fallende Block in mit der größten Zahl k am Anfang des Blocks:

i k + 1ki -1

k muß links von i liegen, da andernfalls das Reversal des Intervals von i – 1 bis i die Zahlder Haltepunkte reduzieren würde und den fallenden Block mit k zurücklassen würde.

k muß rechts von i -1 liegen,

Mit symmetrischer Argumentation folgt, dass i links von k + 1 liegen muß.

Siehe Übung!


Heuristik 2:

Solange es einen Haltepunkt in der Permutation gibt, führe man die folgenden Operationen aus:

Gegeben eine Permutation .

• Falls es einen fallenden Block gibt, dessen Reversal die Zahl der Haltepunkte reduziert und einen fallenden Block zurücklässt, dann drehe ihn um.

• Falls es keinen solchen Block gibt, dann finde (1) einen Block, dessen Reversal die Zahl der Haltepunkte um zwei reduziert, und drehe ihn um und (2) suche einen steigenden Block, dessen Reversal keine neuen Halte- punkte produziert, und drehe ihn um.

Satz:Die Heuristik 2 verwendet höchstens b() Reversals und verwendet daher höchstens 2 x d() vieleReversals (höchstens zwei mal die optimale Zahl von Reversals).

Documents

Genome Rearrangements Zentrum für Bioinformatik der Universität des Saarlandes WS 2001/2002