Eötvös Loránd Tudományegyetem Matematikai Intézet
Ivánkó Natália Réka
Génszekvenciák távolsága a bioinformatikában S M
zakdolgozat
atematika BSc
A
lkalmazott matematikus szakirány
Témavezet® : Bérczi Kristóf
ELTE Operációkutatási Tanszék
Budapest, 2015
Tartalomjegyzék Bevezetés
1
1. Blokk-cserék
4
1.1. Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2. Alapproblémára vonatkozó els® algoritmus . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3. Cirkuláris kromoszómákra vonatkozó algoritmus . . . . . . . . . . . . . . . . . . . . . .
12
1.4. Lineáris kromoszómákra vonatkozó kiterjesztett algoritmus . . . . . . . . . . . . . . . .
17
1.5. Alkalmazás a vibrió fajok evolúciójában . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2. Transzpozíciók
24
2.1. Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.2. 1.5-approximációs algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
2.3. Egyszer¶sített 1.5-approximációs algoritmus . . . . . . . . . . . . . . . . . . . . . . . .
29
2.4. 1.375-approximációs algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3. Pre x transzpozíciók
42
3.1. Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
3.2. Approximációs algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
3.3. Alsó és fels® korlátok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
3.4. Inverz permutációk rendezése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4. Pre x blokk-cserék
51
4.1. Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.2. 2-approximációs algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
4.3. Alsó és fels® korlátok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
Irodalomjegyzék
58
iii
Köszönetnyilvánítás Ezúton szeretnék köszönetet mondani Bérczi Kristófnak, aki az utolsó évben a témavezet®m volt. A téma megszeretése mellett rengeteg motivációt és ösztönzést köszönhetek neki a közös munkánk során. Hálás vagyok hasznos tanácsaiért, ötleteiért, magyarázataiért, mellyel egy éven keresztül kisérte végig a dolgozatom alakulását, valamint egy-egy probléma megoldásában tett el®relépéseimet. A legtöbb köszönet szüleimnek, nagyszüleimnek jár a szeretetükért, gondoskodásukért, és rengeteg bátorításukért az egyetemi éveim alatt. Nélkülük a negyedéig sem jutottam volna el. Köszönettel tartozom a barátaimnak, els®sorban Tasi Emesének, hogy minden szó nékül t¶rte az éjszakázásaimat, Klein Tamásnak, aki pár szóval mindig fel tudott vidítani. Köszönet jár Reskó Sándornak, akihez bármikor fordulhattam, és mindig többre sarkallt a nehéz pillanataimban, illetve egy kiváló biológusnak, Korponai Kristófnak, a hozzám intézett türelméért, hogy az utolsó pillanatig nyaggathattam véget nem ér® kérdéseim sorozatával, melyet mindig maximálisan és legtöbbször végtelen türelemmel igyekezett megválaszolni. Végül, de nem utolsó sorban köszönettel tartozom gimnáziumi tanáromnak, Gy®ry Ákosnak, aki megszeretette velem a matematikát.
iv
Bevezetés This vagrant island Earth A pilgrim shining bright We are shuddering Before the beautiful Before the plentiful We're the voyagers
1
Az él®világ összetétele folyamatosan változik, a fajok folyamatosan átalakulnak, új fajok keletkeznek és kihalnak. A jelenlegi fajok mind az evolúció egy-egy ágának pillanatnyi állapotát képviselik, változatosságuk a fajképz®dések és kihalások hosszú sorozatának eredménye. A molekuláris genetika újabb eredményei rávilágítottak, hogy az evolúció folyamata nyomot hagyott az él®lények genomjában [28], [26]. A genom az él®lényekben, illetve azok egyetlen sejtjében található öröklési anyag, azaz DNS teljes állománya. A molekuláris evolúció kutatásában gyakran használnak matematikai modelleket két él®lény genomjának összehasonlítására, melyek segítségével evolúciós kapcsolatokat tudnak megsejteni két adott faj között, illetve evolúciós távolságokat tudnak mérni a már kapcsolatban lév®k között. Ahhoz, hogy két genom távolságát meg tudjuk mérni, szükségünk lesz egy mér®számra, ezeket hívjuk transzformációknak. A transzformációk egymás melletti gének sorozatának, úgynevezett génszekvenciának az elhelyezkedését változtatják meg a kromoszómán, egy-egy mutációnak tekinthet®k a DNS-láncon. A mutációkat többféleképp is csoportosíthatjuk. Aszerint, hogy mekkora DNS szakaszt érintenek, beszélhetünk lokális és globális mutációkról. A lokális mutációk érinthetnek egyetlen vagy néhány bázist, a globális mutációk nagyobb DNS szakaszokat, génszekvenciákat, esetleg egész kromoszómákat. Lokális mutációk közé soroljuk azokat a transzformációkat, melyek egyetlen gén beillesztéséért, helyettesítéséért illetve törléséért felel®sek. A globális mutációk egy bázisnál magasabb szinten lejátszódó történések, az egy kromoszómaszállal rendelkez® genomok esetében ide soroljuk az inverziókat, azaz a DNS-láncon egy génszekvencia átfordítását, illetve transzpozíciókat, azaz két szomszédos génszekvencia megcserélését. A több kromoszómaszállal rendelkez®, multikromoszómális genomokon létrejöv® globális mutációk a transzlokációk, ekkor a két kromoszómaszál végs® szegmense megcserél®dik, a hasadások és az összeolvadások, ekkor egy kromoszómaszál két kisebbre törik szét, illetve egy nagyobbá olvad össze. 1
Nightwish
: Endless forms most beautiful :
Shudder before the beautiful, 2015 13-18.
1
Természetesen felmerül® kérdés, hogy hány transzformációra van minimálisan szükségünk ahhoz, hogy az egyik faj genomjából megkapjuk a másikét. Ez a minimális szám egy egyértelm¶ távolságot határoz meg két faj között, a kés®bbiekben ezt fogjuk a két faj közti evolúciós távolságnak hívni. Az evolúciós távolság megmutatja, hogy hány transzformáció zajlott le az adott kromoszómaszálon, míg az egyik faj a másikból kifejl®dött. Segítségével össze tudunk hasonlítani olyan fajokat, amelyek már régen szétváltak az evolúció során, illetve meg tudjuk határozni, hogy ez a szétválás mikor történt, képet alkothatunk arról, hogy az evolúció milyen irányban zajlott egy-egy nemzetségen belül. Az evolúciós távolság és az ehhez szükséges transzformációk meghatározására számos algoritmus született és sok esetben derült ki, hogy a probléma nehéz. Ahhoz hogy a problémát matematikai eszközökkel tudjuk vizsgálni, egy matematikai modell felállítására lesz szükségünk. A genomokra úgy gondolunk majd, mint egy n génb®l álló sorozatokra. Mivel a kromoszómaszálakon a gének rendszerint egyetlen példányban szerepelnek, és a mutálódott géneket is könnyedén kezelni tujduk, a géneket számoknak feleltetjük meg 1-t®l n-ig, így az adott faj genomja reprezenáltható a számok 1-t®l n-ig vett permutációjával. A genomban elhelyezked® kromoszómaszálaknak két típusa létezik, a cirkuláris és a lineáris kromoszómák. Az cirkuláris kromoszómák esetében a DNS-lánc zárt, zikailag nincs szabad vége. A fejletlenebb organizmusok, például a prokarióták DNSében cirkuláris kromoszómák találhatóak. Ebben esetben az [1, 2, 3] [2, 3, 1] [3, 1, 2] permutációk mind ugyanazt a kromoszómát reprezentálják. Az evolúció el®rehaladtával a fejletlenebb organizmusok szervezetében megjelentek a telomeráz és a hiszton fehérjék, melyek lehet®vé tették a kromoszómaszál linearitását, és a génállomány megnövekedését. Így a fejlettebb organizmusok genomjában már lineáris kromoszómák találhatóak. A gének elhelyezkedése ekkor a kromoszómán lineáris, és az els® gén helye meghatározott. Ebben az esetben a fenti permutációk mindegyike különböz® kromoszómának felel meg. Mivel mindkét típus esetében a gének számozását mi választjuk meg, ezért a második faj genomját, azaz a cél genomot választhatjuk az [1, 2, . . . , n] sorozatnak. Most már minden genom egy-egy permutációnak felel meg, és a cél genom az identitás, így a fentebb megemlített kérdést a következ®képp fordíthatjuk le: Hány transzformáció szükséges ahhoz, hogy egy adott permutációt az identitásba vigyünk? Ebben a dolgozatban csak unikromoszómális genomokkal foglalkozunk, két transzformációt, és ezek pre x változatait vizsgáljuk meg részletesen. Az alapprobléma mindkét transzformációnál a lineáris és a cirkuláris kromoszómák esetében lényegében ekvivalens lesz. Az els® fejezetben a blokk-cserékkel foglalkozunk, felvázoljuk az alapproblémát, majd meghatározzuk a blokk-cseréknek megfelel® evolúciós távolságot. Ezután ismertetjük az eddigi lineáris és cirkuláris kromoszómákra vonatkozó algoritmusokat, bemutatjuk ezek gyorsításait egy speciális adatstruktúra, a permutációs fa segítségével és megmutatjuk a biológiában vett alkalmazásaikat. A második fejezetben a blokk-cserék egy speciálisabb fajtáját, a transzpozíciókat vizsgáljuk. Mivel maga a transzpozíciós távolság meghatározása NP-nehéz, ezért csak alsó és fels® korlátokat, illetve approximációs algoritmusokat adhatunk. El®ször mutatunk egy fels® és két alsó korlátot, majd ismertetjük az alapproblémára vonatkozó els® 1.5-approximációs algoritmust. Ezután mutatunk egy valamivel egy2
szer¶bb 1.5-approximációs, majd egy 1.375-approximációs algoritmust. A harmadik fejezetben a pre x transzpozíciókat vesszük alapul. A pre x transzpozíciós távolság ismeretlen, és az alapprobléma nehézsége nyitott. El®ször mutatunk egy alsó és egy fels® korlátot, majd ezek segítségével egy 2 és egy 3-approximációs algoritmust. Ezután ismertetjük a pre x transzpozíciós távolságra vonatkozó sejtést. Eszerint az identitástól legtávolabb álló permutáció az inverz permutáció, és ennek a rendezéséhez szükséges pre x transzpozíciók száma a pre x transzpozíciós távolság. A negyedik fejezetben bevezetünk egy új transzformációt, a pre x blokk-cserét, mely az el®z®nek lesz egy általánosítása. Mutatunk egy alsó és egy fels® korlátot, majd ezek segítségével egy 2approximációs algoritmust. A probléma nehézsége és a pre x blokk-csere távolság itt is ismeretlen marad.
3
1. fejezet
Blokk-cserék A blokk-csere fogalmát, illetve a blokk-cserékkel való rendezés alapproblémáját Christie de niálta el®ször 1996-ban [7]. A lineáris kromoszómaszállal rendelkez® genomok esetében a megoldásra szolgáló els® algoritmust is ® készítette el a törésponti gráfok felhasználásával. Az algoritmus m¶veletigénye O(n2 ), ahol n a genomban szerepl® gének száma. Ezt követ®en 2007-ben Fengh és Zhu egy új adatstruktúra, a permutációs fa bevezetésével tovább fejlesztette Christie algoritmusát O(n2 )-r®l
O(n log(n))-sé [14]. A cirkuláris kromoszómaszállal rendelkez® genomok esetében az els® algoritmust 2005-ben dolgozták ki az algebrai permutációs csoportok használatával. Ennek m¶veletideje O(nδ), ahol
δ a két genom közti blokk-csere távolság, mely O(n) id®ben számolható el®re. Ezt az algoritmust kisebb módosításokkal lineáris kromoszómákra is kiterjesztették, majd belátták, hogy a blokk-cserékkel való rendezés alapproblémája lineáris és cirkuláris kromoszómákra lényegében ekvivalens. Azaz ha tudunk találni egy optimális megoldást egy cirkuláris kromoszómaszál esetében, akkor létezik egy neki megfelel® optimális megoldás abban az esetben, amikor a kromoszómaszálat lineárisnak tekintjük. [24]. Kés®bb, a fentebb említett permutációs fa használatával, Huang, Lu és Tang adott egy javítást a cirkuláris kromoszómákra vonatkozó algoritmusra, lecsökkentve ezzel a m¶veletigényt O(nδ)-ról O(n + δ log(n))re [20]. Ez a máig ismert legjobb algoritmus a cirkuláris kromoszómákra vonatkozóan. Mi elvégezzük a javítást a lineáris kromoszómákra kiterjesztett algoritmuson is, eredményként a m¶veletigény itt is
O(n + δ log(n)) lesz. Az algoritmusok alkalmazása az egyes fajok közti evolúciós kapcsolat megállapítására is jelent®s. A 2005-ben kidolgozott algoritmust számítógépes programként is implementálták, majd alkalmazták három emberi vibrió kórokozó cirkuláris kromoszómájára, beleértve a V.vulni cus -t, V.parahaemolycticus t és a
V.cholerae -t.
V.vulni cus
és a
Az algoritmus által szolgáltatott eredmények szerint a blokk-csere távolság a
V.parahaemolycticus
V.parahaemolycticus
és a
V.cholerae
között kisebb, mint a
V.vulni cus
és a
V.cholerae,
illetve a
közti. Ezek az eredmények egybeestek a korábban Chen [5] és
Heidelberg [19] által tett összehasonlító genomikai meg gyelésekkel, ami azt jelzi, hogy a blokk-cserék jelent®s szerepet játszanak a vibrió fajok evolúciójában. Az els® fejezetet a következ®képpen fogjuk felépíteni: az els® részben bevezetjük a blokk-csere, blokk-csere távolság alapfogalmát, illetve de niáljuk a blokk-cserékkel való rendezés alapproblémáját. 4
Szerz®k
Lineáris kromoszóma
Körkörös kromoszóma
Év
Christie
O(n2 )
-
1996
Lin, Lu, Chang, Tang
O(nδ)
O(nδ)
2005
Fengh, Zhu
O(n log(n))
-
2007
Huang, Lu, Tang
-
O(n + δ log(n))
2010
1.1. táblázat. Eddig elért eredmények a blokk-cserékkel való rendezés alapproblémájában
A második részben bevezetjük a törésponti gráf, illetve a permutációs fa fogalmát, alaptulajdonságaikat és ismertetjük Christie lineáris kromoszómákra vonatkozó O(n2 )-es algoritmusát, illetve ennek
O(n log(n))-es továbbfejlesztését. A harmadik részben de niáljuk az algebrai permutációs csoportokhoz köthet® alapfogalmakat, kimondjuk az algoritmusok felírásához szükséges tételeket, majd ismertetjük a cirkuláris kromoszómákra vonatkozó O(nδ)-s algoritmust, illetve ennek O(n+δ log(n))-es továbbfejlesztését. A negyedik részben bemutatjuk az algoritmus kiterjesztését lineáris kromoszómákra, és belátjuk, hogy a feladat megoldása cirkuláris és lineáris kromoszómákra lényegében ekvivalens, majd bemutatjuk az általunk elvégzett javítást. A negyedik részben bemutatjuk az általunk elvégzett O(n + δ log(n))-es javítást a lineáris kromoszómákra vonatkozóan, az ötödik részben pedig a biológiai alkalmazásokat tárgyaljuk. 1.1. Alapfogalmak
Legyen adott a σ = [8, 6,-2, 1,-3, 4,-5, 7] permutáció.
1.1. De níció.
Egy adott π permutáció egy
blokkjának
nevezzük a permutációban lév® egymás
utáni számok meghatározott hosszú sorozatát. A fent megadott σ -ban egy 3 hosszú blokk pl. a [-2, 1,-3] vagy a [8, 6,-2].
1.2. De níció. Blokk-cserének nevezzük azt a transzformációt, amely egy adott π
permutációban
megcserél két nem feltétlenül szomszédos blokkot. Jelöljük b(i, j, k, h) -val azt a blokk-cserét, amely megcseréli a [πi , . . . , πj−1 ] és a [πk , . . . , πh−1 ] blokkokat (i < j ≤ k < h ≤ n). Speciálisan, j = k -ra visszakapjuk a transzpozíció de nícióját.
1.1. ábra. A π permutációra alkalmazott b(i, j, k, h) blokk-csere
5
Legyen pl. σ 0 = [8, 6,-5, 4,-2, 1,-3, 7] a σ -ból a [-5] és a [-2, 1,-3], σ 00 = [1,-3, 7, 6,-5, 4,-2, 8] pedig a
σ 0 -b®l a [8] és a [1,-3, 7] blokkok felcserélésével kapott permutáció. Mivel a blokk-cserék nem változtatják meg a számok el®jelét, csak az el®jel nélküli permutáció vihet® át az identitásba. Ebben a fejezetben ezért csak el®jel nélküli permutációkkal fogunk foglalkozni.
1.3. De níció.
Egy adott π permutáció
blokk-csere távolsága az a minimális szám, ahány blokk-
csere szükséges ahhoz, hogy a permutációt az identitásba vigyük. Jelölés : dBI (π). Legyen pl. π = [5, 2, 4, 1, 3], ekkor dBI (π) = 2. Valóban, nem létezik olyan blokk-csere, melyet alkalmazva egyb®l az identitást kapnánk. Cseréljük meg el®ször az [5] és a [1,3] blokkokat, majd az így kapott π 0 = [1, 3, 2, 4, 5]-ben, a [2] és a [3] blokkokat. Ekkor π 00 = [1, 2, 3, 4, 5] = Id. 1.2. Alapproblémára vonatkozó els® algoritmus 1.2.1. Christie eredeti algoritmusa
A lineáris kromoszómaszálakra vonatkozóan elkezdték vizsgálni, hogy mely génszekvenciák és az azoknak megfelel® blokkok szomszédosak egyszerre mindkét genomban, illetve a nekik megfelel® π , és identitás permutációban. Ezek a blokkok vannak már jó helyen. Ha azonban az identitásban nem szomszédosak, akkor úgynevezett töréspontokat de niálunk. Formálisan ezeket el®ször Bafna és Pevzner vezette be a transzpozícióknál [3].
1.4. De níció.
Legyen adott egy π permutáció. Egészítsük ki ezt π0 = 0 -val és πn+1 = n + 1-gyel.
Legyen 1 ≤ i ≤ n+1. Ekkor i -ben töréspont van, ha πi - πi−1 6= 1. Jelölje b(π) a π -ben lév® töréspontok számát. Tudjuk, hogy csak az identitásban nincs egy töréspont sem, tehát b(Id) = 0. Ahhoz, hogy az identitást elérjük, célunk olyan blokk-cseréket találni, amelyek csökkentik a töréspontok számát a permutációban. A következ®kben megvizsgáljuk, hogy egy-egy blokk-csere alkalmazása után hogyan változik a töréspontok száma a permutációban. Vegyük észre, hogy egy blokk-csere legfeljebb 4 töréspontot szüntethet meg, ekkor a megcserélend® 2 blokk mindkét vége a "rossz" helyr®l a "jó" helyre kerül.
1.2. ábra. Négy töréspont megszünése egy adott π permutációban
Négy töréspontot nem mindig tudunk majd megszüntetni, azonban akkor is optimális megoldáshoz jutunk, ha el tudjuk érni azt, hogy mindig legalább kett®vel csökkenjen a töréspontok száma.
6
1.5. Tétel.
Egy adott
π
permutációban mindig létezik olyan blokk-csere, mely legalább 2-vel csökkenti
a töréspontok számát.
A következ®kben ezeket
minimális blokk-cserének fogjuk hívni. Ezután belátjuk, hogy ha egy
olyan algoritmust készítünk, amiben csak ilyen blokk-cseréket alkalmazunk, akkor a minimális blokkcsere sorozatot és dBI (π)-t fogjuk megkapni. A tétel egy új struktúra bevezetésén, és két kisebb lemmán múlik. Egy élszínezett gráfot, a
törésponti gráfot
fogjuk használni modellként, ennek az el®állítása a
következ®képpen történik: Legyen π az [1, 2 . . . , n] számok egy adott permutációja. Legyen i a permutáció egy eleme (1 ≤ i ≤ n). Feleltessünk meg minden i-nek rendre két számot, a 2i − 1-t és a
2i-t, majd vegyük hozzá a permutációhoz a 0-t és az n + 1-t. Az így kapott számok lesznek a gráf csúcsai. Pl. a [3,1,2] permutációhoz a 0, 5, 6, 1, 2, 3, 4, 7 sorozat, a [1, 2, 5, 3, 4, 6] permutációhoz pedig a
0, 1, 2, 3, 4, 9, 10, 5, 6, 7, 8, 11, 12, 12 sorozat fog tartozni. Vezessen szürke él i és i + 1 között (0 ≤ i ≤ n) és fekete él πi és πi−1 között (1 ≤ i ≤ n + 1).
1.3. ábra. A [1, 2, 5, 3, 4, 6] permutációnak megfelel® törésponti gráf
Látjuk, hogy a keletkez® gráfban minden csúcs foka 2, és minden fekete élhez egyértelm¶en tartozik egy szürke él. Ennek a segítségével az egész gráfot körökre tudjuk bontani, és ez a felbontás a sorrendt®l eltekintve egyértelm¶. Jelölje c(π) a körök számát a gráfban. A következ®kben azt fogjuk vizsgálni, hogy egy blokk-csere alkalmazása után, hogyan változik a körök száma a gráfban. Vegyük észre, hogy csak az identitásnak van n + 1 köre, így célünk a körök számának növelése.
1.6. Tétel.
Egy minimális blokk-csere kett®vel növeli
1.7. Tétel.
Nem lehet a
c(π)-t
c(π)-t.
kett®nél többel növelni egy blokk-csere során.
Ezek alapján már meg tudjuk határozni dBI (π)-t.
1.8. Tétel. Bizonyítás.
Egy adott
π
permutációra
dBI (π) =
A 1.6. Tétel miatt dBI (π) ≤
n+1−c(π) . 2
n+1−c(π) , 2
a 1.7. Tétel miatt dBI (π) ≥
n+1−c(π) , 2
n+1−c(π) . 2
A minimális blokk-csere sorozatot a kövektkez® algoritmussal tudjuk megtalálni : 7
így dBI (π) =
while π
nem rendezett
do
keressük meg azt a legkisebb x értéket, amire πx 6= x ; keressük meg a legnagyobb y értéket x − 1 és π −1 (x) között ; alkalmazzuk a b(x, π −1 (y), π −1 (x), π −1 (y + 1)) blokk-cserét ;
end 1.4. ábra. Blokk-cserékkel való rendezés algoritmusa a lineáris kromoszómákra (Christie 1996) A while ciklusban minden lépés lineáris id® alatt végrehajtható, és maga a ciklus legfeljebb
n 2
alkalommal fut le.
1.9. Tétel.
A lineáris kromoszómákra vonatkozó blokk-cserékkel való rendezés algoritmusa
O(n2 )
m¶-
veletigény¶.
1.2.2. Gyorsított algoritmus
A fenti algoritmus javítására egy új adatstruktúrát vezetünk be, mellyel a permutációk rendezésében résztvev® blokk-cserék, illetve egy-egy intervallum maximális elemei gyorsabban kiszámolhatóak lesznek, így az algoritmus futásideje O(n log(n))-re csökkenthet®. A permutációs fa el®állítása a következ®képpen történik: Legyen T egy r gyöker¶ kiegyensúlyozott bineáris fa, ahol minden bels® csúcsnak 2 gyereke van. Legyen t egy tetsz®leges bels® csúcs, bal gyerekét jelölje L(t), a jobbot R(t). A t magassága legyen de níció szerint H(t) = max{H(L(t)), H(R(t))}, a leveleké 0, a permutációs fáé pedig H(r). A kiegyensúlyozottság miatt, minden t ∈ T csúcsra
|H(L(t)) − H(R(t))| ≤ 1. Tegyük fel, hogy T -nek n levele van, és feleltessük meg a π = [π1 , . . . , πn ] permutációnak a következ®képp : a leveleket címkézzük meg rendre a π1 , . . . , πn elemekkel, és minden
t ∈ T bels® csúcsot feleltessünk meg egy permutációbeli intervallumnak úgy, hogy a címkéje legyen az adott intervallumban lév® maximális szám, a neki megfelel® intervallum pedig legyen L(t) és R(t) csúcsoknak megfelel® intervallumok konkatenációja. A t címkéjének megfelel® számot t értékének fogjuk hívni, ez L(t) és R(t) értékének maximuma lesz.
1.5. ábra. A π = [9,6,1,4,7,5,2,3,8] permutációnak megfelel® T permutációs fa [14] A kiegyensúlyozottság miatt a permutációs fa magasságára tudunk fels® korlátot mondani. 8
1.10. Tétel. Ekkor
Legyen
H(t) = log(n),
π = [π1 , · · · , πn ] ahol
n
tetsz®leges permutáció,
T
az ennek megfelel® permutációs fa.
a permutációban szerepl® elemek száma.
A fenti példában szerepl® T fa magassága dlog(9)e = 4. A következ®ekben a permutációs fákra három operációt, majd az ezeket végrehajtó algoritmusokat fogjuk de niálni. Az els® az fát, a második az Vág (T, m),
Az
Épít (π),
amely felépíti az adott π permutációnak megfelel® permutációs
Összeolvaszt (t1 , t2 ),
amely összeolvasztja a t1 , t2 permutációs fákat, a harmadik a
amely két permutációs fára hasítja T -t az adott permutációban szerepl® m. elem mentén.
Épít (π)
algoritmusának els® lépésében a 0. szintre tesszük az adott π permutáció elemeit, ezek
lesznek a levelek. A következ® lépésben balról jobbra haladva kettesével párosítjuk össze a csúcsokat, közös szül®nek pedig az elemek maximumát vesszük, ezek lesznek az els® szint csúcsai. Ha páratlan sok csúcs van, akkor a legutolsó csúccsal az 1.5. ábrán látható módon bánunk el. Ezután a párosításokat elvégezzük a következ® rétegeken, addig amíg 2 csúcsunk nem marad, ezek közös szül®je lesz a permutációs fa gyökere.
1.11. Tétel. letigénye
Az Épít(π) mindig az adott
π
permutációnak megfelel® permutációs fát építi fel, m¶ve-
O(n).
Legyen t1 a p1 = [π1 , · · · , πm ], t2 a p2 = [πm+1 , · · · , πn ] permutációnak megfelel® permutációs fa. Ekkor t1 és t2 egyesítését az
Összeolvaszt (t1 , t2 )
algoritmusssal végezzük el a következ® módon:
Tegyük fel, hogy H(t1 ) ≥ H(t2 ), ellenkez® esetben t2 és t1 szerepét felcseréljük. Az algoritmust 3 esetre bontjuk: 1. eset :
Ha H(t1 ) − H(t2 ) ≤ 1, akkor vegyünk fel egy új t csúcsot, és legyen L(t) = t1 , R(t) = t2 .
1.6. ábra. Az
2. eset :
Összeolvaszt (t1 , t2 )
1. esete, H(t1 ) = k , H(t2 ) = k vagy k − 1 [14]
Ha H(t1 ) − H(t2 ) = 2, akkor ismét két esettel állunk szemben. Ha t1 -ben H(L(t1 )) ≥
H(R(t1 )), akkor vegyünk fel két új csúcsot, el®ször t0 -t és legyen L(t0 ) = R(t1 ), R(t0 ) = t2 , másodszor t-t és legyen L(t) = L(t1 ), R(t) = t0 . Ha t1 -ben H(L(t1 )) < H(R(t1 )), akkor vegyünk fel 3 új csúcsot. El®ször t0 -t, és legyen L(t0 ) = L(t1 ), R(t0 ) = L(R(t1 )), másodszor t00 -t, és legyen L(t00 ) = R(R(t1 )),
R(t00 ) = t2 , majd t-t, és L(t) = t0 , R(t) = t00 . 3. eset :
Ha H(t1 ) > H(t2 ), akkor rekurzív eljárással illesztjük össze R(t1 )-t és t2 -t, majd az így
kapott fát és L(t1 )-et. A képlet itt a következ®: t =
1.12. Tétel.
Legyen t1 a
p1 = [π1 , · · · , πm ], t2
p2 = [πm+1 , · · · , πn ]
a
tációs fa. Ekkor az Összeolvaszt(t1 , t2 ) mindig a
Összeolvaszt (L(t1 ), Összeolvaszt (R(t1 ), t2 )). permutációnak megfelel® permu-
p = [π1 , · · · , πm , πm+1 , · · · , πn ]
lel® permutációs fát hozza létre, és m¶veletigénye
permutációnak megfe-
O(H(t1 ) − H(t2 )) = O(log(n)). 9
1.7. ábra. Az
Összeolvaszt (t1 , t2 )
2. esete, H(t1 ) = k + 2, H(t2 ) = k és H(L(t1 )) > H(R(t1 )) [14]
1.8. ábra. Az
Összeolvaszt (t1 , t2 )
2. esete, H(t1 ) = k + 2, H(t2 ) = k és H(L(t1 )) = H(R(t1 )) [14]
1.9. ábra. Az
Összeolvaszt (t1 , t2 )
2. esete, H(t1 ) = k + 2, H(t2 ) = k és H(L(t1 )) < H(R(t1 )) [14]
Legyen T most a p = [π1 , · · · , πm−1 , πm , · · · , πn ]-nek megfelel® r gyöker¶ permutációs fa, P =
v0 , v1 , · · · , vk egy πm -t®l r-ig vett úton való csúcsok sorozata, ahol v0 = πm , vk = r. Legyen Ul = {L(vi )|vi−1 = R(vi ), 0 < i ≤ k}, és Ur = {v0 } ∪ {R(vi )|vi−1 = L(vi ), 0 < i ≤ k}. Ekkor az Ul -ben lév® csúcsoknak megfeleltetett intervallumok balról jobbra vett sorrendben elkészített konkatenációja a pl = [π1 , · · · , πm−1 ] intervallumnak felel meg, hasonlóan elkészítve az Ur csúcsainak megfelel® intervallumokra a konkatenációt az eredmény pr = [πm , · · · , πn ] lesz. Legyen példaként a fenti
π = [9,6,1,4,7,5,2,3,8] permutációban v0 = π4 , és vegyük a kékkel jelölt v1 , v2 , v3 csúcsok sorozatát a gyökérig. Ekkor Ur = {R(v1 ), R(v3 )} lesznek a lila, Ul = {L(v1 ), L(v2 )} pedig a barna csúcsok. Ur , illetve Ul csúcsainak balról jobbra vett sorrendben elkészített konkatenciója pedig valóban
pr = [π1 , π2 , π3 ] = [9,6,1], pl = [π4 , π5 , π6 , π7 , π8 , π9 ] = [4,7,5,2,3,8]. A
Vág (T, m)
algoritmus során a T -nek megfelel® permutációs fát fogjuk ketté vágni a πm elem
mentén tr és tl részfává. Az els® lépésében keresünk a fában egy πm -b®l r-be vezet® utat, az érintett csúcsokat jelöljük P = v0 , · · · vk -val, ahol kezdetben v0 = πm , vk = r, és tr = v0 . A második lépésben haladjunk végig P elemein, ha az L(vi ) = vi−1 feltétel teljesül, akkor alkalmazzuk az olvaszt (tr , R(vi ))-t,
ha pedig R(vi ) = vi−1 , akkor
Összeolvaszt (L(vi ), tl )-t,
10
Össze-
az így létrejöv® két új fa
1.10. ábra. Ul és Ur ábrázolása a π = [9,6,1,4,7,5,2,3,8] permutációnak megfelel® T permutációs fán
legyen rendre az új tr , illetve tl , ahol (1 ≤ i ≤ k).
1.13. Tétel. Legyen T mindig a
a
p = [π1 , · · · , πm−1 , πm , · · · , πn ]-nek megfelel® permutációs fa. Ekkor a Vág(T, m)
pl = [π1 , · · · , πm−1 ],
illetve
fákat hozza létre, és m¶veletigénye
pr = [πm , · · · , πn ]
permutációknak megfelel®
tl
és
tr
permutációs
O(log(n)).
Azt kell még meggondolnunk, hogyan tudjuk a permutációs fában egy adott πi elem pozícióját megmondani, és fordítva, egy adott i index esetén az annak megfelel® πi elemet megkeresni. A keresett pozíció meghatározásához induljunk el πi -b®l a gyökér felé és számoljuk meg a π elem bal oldalán elhelyezked® leveleket, a kapott számot eggyel növelve kapjuk a keresett pozíciót. Az adott i indexhez tartozó πi elem megkeresésének alapötlete az, hogy minden csúcshoz tároljuk el egy címkében azt, hogy hány elem van a neki megfelel® intervallumban. Induljunk el a gyökérb®l, és nézzük meg, hogy az adott csúcs címkéje nagyobb-e, mint az adott i index, ha igen, akkor a bal gyerek mentén, ha nem, akkor a jobb gyerek mentén menjünk le egy szintet, majd vizsgáljuk meg ismét a feltételt. A levél, amibe érkezünk, lesz a keresett πi . Mivel mindkét keresésben legfeljebb annyi lépést kell tennünk, amennyi a fa magassága, a m¶veletigény O(log(n)). Tekintsük most a Christie által adott algoritmust. A ciklus második lépésében az x − 1 és a π −1 (x) közti legnagyobb érték megkeresését a következ®képp végezzük el : vágjuk szét az aktuális permutációnak megfelel® permutációs fát el®ször x, majd π −1 (x) + 1 mentén, így a [π1 , · · · , πx−1 ], [πx , · · · , x],
[ππ−1 (x)+1 , · · · , πn] permutációknak megfelel® t1 , t2 , t3 fákhoz jutunk. A keresett érték t2 gyökerében lesz, ez pedig minden körben O(log(n)) id®ben meghatározható, az eredeti O(n) idej¶ maximum keresés helyett. Ezután a ciklus harmadik lépésében szerepl® b(x, π −1 (y), π −1 (x), π −1 (y + 1)) blokkcserét a következ®képp hajtsuk végre. Vágjuk szét az aktuális permutációnak megfelel® permutációs fát i = x, j = π −1 (y), k = π −1 (x), majd l = π −1 (y + 1) szerint. Ekkor a [π1 , · · · , πi−1 ], [πi , · · · , πj−1 ], [πj , · · · , πk−1 ], [πk , · · · , πl−1 ], [πl , · · · , πn ] permutációknak megfelel® t1 , t2 , t3 , t4 és t5 fákhoz jutunk. Ezután olvasszuk össze a kapott 5 fát a következ®képp : Összeolvaszt(Összeolvaszt(Összeolvaszt(Összeolvaszt(t1 , t4 ), t3 ), t2 ), t5 )
Mivel a négy vágás és a négy összeolvasztás is O(log(n)) id®t vesz igénybe, ezen a lépés m¶veletigénye is O(log(n)). 11
A fentiek alapján így a következ®t mondhatjuk:
1.14. Tétel. mentációja
A lineáris kromoszómákra vonatkozó algoritmus permutációs fák segítségével vett imple-
O(n log(n))
m¶veletigeny¶.
1.3. Cirkuláris kromoszómákra vonatkozó algoritmus 1.3.1. Eredeti algoritmus
Meidanis és Dias vette észre el®ször [24], hogy minden permutációs ciklus megfeleltethet® egy-egy genom cirkuláris kromoszómájának a következ®képpen : jelentsék a ciklus elemei a kromoszóma génjeit, az elemek sorrendje pedig a gének sorrendjét a kromoszómában. k gyelték meg azt a jelenséget is, hogy az olyan globális transzformációk, mint az összeolvadás és a hasadás egy-egy 2 elem¶ ciklussal, azaz 2-ciklussal vett kompozíciónak feleltethet®ek meg. A kompozícióval kapott permutáció reprezentálja a transzformáció utáni kromoszómát. Legyen α tetsz®leges permutáció α1 α2 · · · αr ciklusfelbontással, és p = (x, y) egy 2-ciklus. Tegyük fel, hogy x és y α felbontásában különböz® ciklusban voltak. Legyen αp = (a1 = x, a2 , . . . , ai ) és αq = (b1 = y, b2 , . . . , bj ), ahol 1 ≤ p < q ≤ r. A pα kompozíció αp -t és αq -t egy nagy (a1 =
x, a2 , . . . , ai , b1 = y, b2 , . . . , bj ) ciklussá egyesíti. Ekkor p
egyesítés operáció α-n, mely 2 kromoszóma
összeolvadásának felel meg. Példaként legyen
β = (7,9,8,5)(1,4,3,2) = (7,9,8,5)(3,2,1,4) ,p = (7,3) ekkor pβ = (1,4,7,9,8,5,3,2) = (7,9,8,5,3,2,1,4). Tegyük fel most, hogy x és y α felbontásában ugyanabban a ciklusban voltak. Legyen αp = (a1 =
x, a2 , . . . , ai = y, ai+1 , . . . , aj ), ahol 1 ≤ p ≤ r. A pα kompozíció αp -t 2 diszjunkt, (a1 , . . . , ai−1 ) és (ai , . . . , aj ) ciklusra vágja szét. Ekkor p
hasítás operáció α-n, mely az adott kromoszóma 2 cirkuláris
szállá való hasadásának felel meg. Példaként legyen:
β = (1,2,9,5,6,7,8,3) = (2,9,5,6,7,8,3,1) ,p = (2,7) ekkor pβ = (1,7,8,3)(2,9,5,6) = (2,9,5,6)(7,8,3,1) Kés®bb észrevették, hogy két jól megválasztott 2-ciklus egymás utáni kompozíciója egy α-n végbemen® blokk-cserének felel meg. Legyen α = (a1 , · · · , ak ), p1 = (a1 , ax ) hasítás α-n (1 ≤ x ≤ k), p2
= (ay , az ) egyesítés p1 α-n. Alkalmazva p1 -t, p1 α = (a1 , · · · , ax−1 )(ax , · · · , ak ). Mivel p2 egyesítés volt p1 α-n ezért ay -nak és az -nek különböz® ciklusokban kell lenniük, így feltehet®, hogy 1 ≤ y ≤ x − 1, valamint x ≤ z ≤ k .
p1 α = (a1 , · · · , ay , · · · ax−1 )(ax , · · · , az , · · · , ak ) = (ay , · · · , ax−1 , a1 , · · · , ay−1 )(az , · · · , ak , · · · , ax , · · · , az−1 )
12
Alkalmazzuk most p2 -t.
p2 p1 α = (ay , · · · , ax−1 , a1 , · · · , ay−1 , az , · · · , ak , · · · , ax , · · · , az−1 ) = (a1 , · · · , ay−1 , az , · · · , ak , · · · , ax , · · · , az−1 , ay , · · · , ax−1 ). Ez éppen (az , · · · , ak ), (ay , · · · , ax−1 ) blokkok megcserélését jelenti. Példaként legyen β = (3,4,6,1,7,2,9,5,8), célunk a (3,4,6) és a (9,5,8) blokkokat megcserélni. Válasszuk a p1 hasítást és a p2 egyesítést a következ®képp :
p1 = (a1 , ax ) = (3,7) ,p2 = (ay , az ) = (4,9) ekkor p1 β = (1,3,4,6)(2,9,5,8,7) = (3,4,6,1)(7,2,9,5,8) p2 p1 β = (1,3,9,5,8,7,2,4,6) = (3,9,5,8,7,4,6,1), épp ezt akartuk elérni.
1.15. Tétel. és
x ≤ z ≤ k.
1.16. Tétel.
α = (a1 , a2 · · · , ak ), p1 = (a1 , ax ), p2 = (ay , az ),
Legyen
Ekkor mindig tudunk olyan blokk-cserét találni, ami Legyen
α
ahol
1 < x ≤ k , 1 ≤ y ≤ x − 1,
α-t, p2 p1 α-ba
viszi.
egy cirkuláris kromoszómának megfeleltetett permutáció. Ekkor tetsz®leges
blokk-cseréhez tudunk találni
p1 , p2
ciklusokat, hogy
p1
hasítás
α-n, p2
egyesítés
p1 α-n
és
σα
=
σ
p2 p1 α.
Tehát, minden jól megválasztott két 2-ciklusnak megfelel egy-egy blokk-csere, és fordítva. Legyen α, β két cirkuláris kromoszómának megfelel® permutáció. A lineáris kromoszómák esetéhez hasonlóan β = Id itt is feltehet®. Célunk itt is azt a minimális számot, és az ehhez tartozó σ1 , σ2 , · · · , σk blokk-csere sorozatot, illetve az ezeknek rendre megfelel® p12 , p11 , · · · , pk2 , pk1 2-ciklusokat megtalálni,
p1k−1 · · · p12 p11 α = Id. Innen melyekkel α Id-be transzformálható, azaz σk σk−1 · · · σ2 σ1 α = pk2 pk1 pk−1 2 · · · p12 p11 = Idα−1 . Ez egyben azt is jelenti, hogy Idα−1 tartalmazza pk−1 σk σk−1 · · · σ2 σ1 = pk2 pk1 pk−1 1 2 azt az összes információt ami σ1 , σ2 , · · · , σk kiszámításához kell. Láttuk, hogy Idα−1 felbomlik páros sok 2-ciklus szorzatára. Egy adott permutáció 2-ciklus felbontása nem egyértelm¶, de ha α1 α2 · · · αm , és β1 β2 · · · βn két tetsz®leges 2-ciklus felbontása egy adott permutációnak, akkor vagy m és n is páros, vagy mindketten páratlanok.
1.17. Tétel.
Idα−1
tetsz®leges 2-ciklus felbontása páros sok elemb®l áll.
Célünk Idα−1 minimális darabszámú 2-ciklusfelbontását megtalálni, ugyanis ekkor a minimális darabszám fele lesz a blokk-csere távolság Id és α között. Legyen β = (b1 , b2 , · · · , bk ) tetsz®leges permutáció, ekkor β felírható 2-ciklusok szorzataként a következ® alakban : β = (b1 , bk )(b1 , bk−1 ) · · · (b1 , b2 ) =
C1 C2 · · · Ck−1 . Nevezzük ezt β
egyszer¶ 2-ciklusfelbontásának, és jelöljük sim2 (β)-val. Jelölje l(Ci )
a Ci ciklus hosszát (1 ≤ i ≤ k) , és legyen λ =
P
(l(Ci ) − 1), azaz az egyszer¶ 2-ciklusfelbontásban
1≤i≤k
szerepl® ciklusok darabszáma, illetve f (β) a β -ban szerepl® diszjunkt ciklusok darabszáma. Ekkor igaz a következ® két tétel :
1.18. Tétel.
Legyen
C1 C2 · · · Cp
tetsz®leges ciklusfelbontása
13
Idα−1 -nek.
Ekkor
p ≥ λ.
Tehát az egyszer¶ 2-ciklusfelbontás minimális is.
1.19. Tétel. és
n=
Legyen
f (Idα−1 )
α = (a1 , a2 , · · · , an ),
és
Idα−1 = sim2 (Idα−1 ) = (αλ αλ−1 · · · α1 ),
ekkor
λ
páros,
+ λ.
Tehát λ kifejezhet® az elemek és a diszjunkt ciklusok számával. Innen pedig:
1.20. Tétel.
A blokk-csere távolság
α
és
Id
között
δ=
n−f (Idα−1 ) . 2
Mivel Idα−1 tartalmazza az összes információt, ami a minimális blokk-cserék kiszámításához kell, ebben fogunk hasítás és egyesítés operációkat keresni úgy, hogy ezek Idα−1 egyszer¶ 2-ciklusfelbontását adják, majd az ezeknek megfelel® blokk-cserékkel rendezzük α-t. A 1.18. Tétel szerint az egyszer¶ 2-ciklusfelbontás minimális is, az ezeknek megfelel® blokk-csere sorozat optimális megoldás lesz. A minimális blokk-csere sorozatot, illetve az ezeknek megfelel® két 2-ciklusokat a 1.11 ábrán látható algoritmussal tudjuk megtalálni.
Input : Egy tetsz®leges α = (a1 , a2 , · · · , an ) permutáció ; Output : Egy minimális σ1 , σ2 , · · · , σδ blokk-csere sorozat ; Legyen δ =
for
n−f (Idα−1 ) ; 2
i = 1 to
δ
do
válasszunk ki tetsz®legesen két szomszédos x és y elemet Idα−1 -ben ((x, y) hasítás lesz α-n) ; forgassuk el α = (a1 , · · · , an )-t úgy, hogy a1 = x, és tegyük fel, hogy y = ak ;
for
j = 1 to n
do
index(aj ) = j ;
end keressünk két olyan u, v szomszédos elemet Idα−1 (x, y)-ban, hogy index(u) ≤ k − 1, és index(v) ≥ k ( (u, v) egyesítés lesz (x, y)α-n) ;
σi = (u, v)(x, y); α = (u, v)(x, y)α; Idα−1 = Idα−1 (x, y)(u, v);
end 1.11. ábra. Blokk-cserékkel való rendezés algoritmusa a cirkuláris kromoszómákra (Lin, Lu, Chang, Tang 2005) Az algoritmusban δ , (u, v), (x, y) meghatározása O(n) lépést vesz igénybe, maga a küls® ciklus pedig δ alkalommal fut le, így :
1.21. Tétel.
A cirkuláris kromoszómákra vonatkozó blokk-cserékkel való rendezés algoritmusa
m¶veletigény¶.
14
O(δn)
1.3.2. Gyorsított algoritmus
A fenti algoritmus legnehezebb lépése az, hogy megtaláljuk az egyesítés operációt a ciklus végén, erre kés®bb kidolgoztak egy hatékonyabb módszert. Az ötlet az, hogy az egyesítés operációt annak a segítségével keressük meg, hogy meghatározzuk az aktuális permutáció két ciklusának maximális elemeit, ez pedig a permutációs fák használatával konstans id®ben megtehet®, ugyanis a maximális elemek az aktuális részfák gyökerében lesznek. Az egyesítés operáció megtalálása két fontos észrevételen múlik :
1.22. Tétel. hogy és
z
és
Id(z)
(α0 (z), Id(z))
1.23. Tétel. a
Legyen
α0
az
L = {1,2, · · · , n}
számok egy tetsz®leges permutációja,
0 különböz® ciklusokban vannak α -ben. Ekkor egyesítés
Legyen
α0
az
α0 (z) és
Id(z)
z ∈ L.
szomszédosak
Tegyük fel,
Idα0−1 -ben,
α0 -n L = {1,2, · · · , n} számok egy tetsz®leges permutációja, C
egy ciklus
α0 -ben, z
C -ben lév® elemek maximuma. Tegyük fel, hogy z 6= n. Ekkor α0 (z) és Id(z) szomszédosak Idα0−1 -ben,
és
(α0 (z), Id(z))
egyesítés
α0 -n.
Legyen α0 az L = {1,2, · · · , n} számok egy tetsz®leges C1 és C2 ciklusokból álló permutációja. Legyenek m1 és m2 rendre C1 és C2 maximális elemei, és tegyük fel, hogy m1 < m2 . Az el®z®ek alapján
α0 (m1 ) és I(m1 ) szomszédosak Idα0−1 -ben és (α0 (m1 ), Id(m1 )) egyesítés α0 -n. Így, a fenti algoritmusban az egyesítés operáció megtalálása helyettesíthet® azzal a lépéssel, hogy az aktuális permutáció két ciklusának maximális elemeit megkeressük, majd ezeknek vesszük a minimumát, legyen ez z = min(m1 , m2 ). Válasszuk ezután u-t α0 (z)-nek, v -t pedig Id(z)-nek. Ekkor a módosított algoritmus 1.12. ábrán látható. Az els® lépésben δ meghatározásakor építsük is fel az α-nak megfelel® T permutációs fát, ez ismét végrehajtható O(n) id®ben. Ezután nyomon kell követnünk, hogyan változik a permutációs fa az egyes operációk végrehajtása után. A cikluson belül a hasítás operációt kétféleképpen hajthatjuk végre : vagy egy Vágást, vagy két Vágást és egy Összeolvasztást alkalmazunk T -re, ezek O(log(n)) m¶veletigény¶ek. A hasítás alkalmazása után a maximális elemek megtalálása konstans id®ben megy, mivel ezek a ciklusoknak megfelel® permutációs fák gyökerében lesznek. Az egyesítés operációt is kétféleképpen hajthatjuk végre a permutációs fákon, vagy egy Összeolvasztást vagy három Vágást és három Összeolvasztást alkalmazunk T -n, ezek mindegyike O(log(n)) m¶veletigény¶. Így a ciklus lefutásakor
O(log(n)) lépést végzünk, maga a ciklus pedig δ -szor fut le, tehát:
1.24. Tétel. sa
A cirkuláris kromoszómákra vonatkozó blokk-cserékkel való rendezés gyorsított algoritmu-
O(n + δ log(n))
m¶veletigény¶.
Vegyük példaként α = (7,1,4,6,2,5,3,8) cirkuláris kromoszómának megfeleltetett permutációt. Alkalmazzuk erre a gyorsított algoritmust.
Idα−1 = (1,8,4,2,7)(3,6,5) , δ =
15
8−2 n − f (Idα−1 ) = =3 2 2
Input : Egy tetsz®leges α = (a1 , a2 , · · · , an ) permutáció ; Output : Egy minimális σ1 , σ2 , · · · , σδ blokk-csere sorozat ; Legyen δ =
for
n−f (Idα−1 ) ; 2
i = 1 to
δ
do
válasszunk ki tetsz®legesen két szomszédos x és y elemet Idα−1 -ben ((x, y) hasítás lesz α-n) ;
α0 = (x, y)α ; keressük meg a maximális m1 ill. m2 elemeket rendre C1 -ben és C2 -ben ; legyen z = min(m1 , m2 ) ; legyen u = α0 (z) és v = Id(z) (u és v ekkor szomszédos Idα0−1 -ban, és (u, v) egyesítés α0 -n) ;
σi = (u, v)(x, y); α = (u, v)(x, y)α; Idα−1 = Idα−1 (x, y)(u, v);
end 1.12. ábra. Blokk-cserékkel való rendezés gyorsított algoritmusa a cirkuláris kromoszómákra (Huang, Huang, Tang, Lu 2010) Azaz α 3 blokk-cserével már az identitásba vihet®, jelölje ezeket
σ1 = p12 p11 , σ2 = p22 p21 , σ3 = p32 p31 Legyen p11 = (x, y) = (1,8), α0 = (1,8)(7,1,4,6,2,5,3,8) = (1,4,6,2,5,3)(7,8). Itt a kezdeti permutációs fára két
Vágást,
majd egy
Összeolvasztást
alkalmaztunk.
(7,1,4,6,2,5,3,8) → (7,1,4,6,2,5,3), (8) → (7), (8), (1,4,6,2,5,3) (7), (8), (1,4,6,2,5,3) → (7,8)(1,4,6,2,5,3). Ekkor m1 = 6, m2 = 7, z = min(6,7) = 6, és α0 (6) = 2, I(6) = 7, p12 = (u, v) = (2,7). Így az els® blokk-cserét alkalmazva
σ1 = p12 p11 = (2,7)(1,8) α = (2,7)(1,4,6,2,5,3)(7,8) = (1,4,6,7,8,2,5,3) Iα−1 = (1,8,4,2,7)(3,6,5)(2,7)(1,8) = (1,4,2)(3,6,5)(7)(8) Ekkor a permutációs fára három
Vágást,
majd három
Összeolvasztást
alkalmaztunk:
(1,4,6,7,8,2,5,3) → (1,4,6), (2,5,3), (7), (8) (1,4,6), (2,5,3), (7), (8) → (1,4,6,7), (2,5,3), (8) → (1,4,6,7,8), (2,5,3) → (1,4,6,7,8,2,5,3)
16
A második lépésben legyen p21 = (1,4), α0 = (1,4)(1,4,6,7,8,2,5,3) = (1)(2,5,3,4,6,7,8). Ekkor az aktuális permutációs fára két
Vágást,
majd egy
Összeolvasztást
alkalmaztunk.
(1,4,6,7,8,2,5,3) → (1), (4,6,7,8,2,5,3) → (1), (4), (6,7,8,2,5,3) (1), (4), (6,7,8,2,5,3) → (1), (4,6,7,8,2,5,3) Ekkor m1 = 1, m2 = 8, z = min(1,8) = 1, α0 (1) = 1, Id(1) = 2, p22 = (1,2). Így a második blokk-cserét alkalmazva
σ2 = p22 p21 = (1,4)(1,2) α0 = (1,2)(1)(2,5,3,4,6,7,8) = (1,2,5,3,4,6,7,8) Iα−1 = (1,4,2)(3,6,5)(1,4)(1,2) = (1)(2)(3,6,5)(4)(7)(8) Ekkor a permutációs fára egy
Összeolvasztást
alkalmaztunk.
(1), (2,5,3,4,6,7,8) → (1,2,5,3,4,6,7,8) A harmadik lépésben legyen p31 = (3,6), α0 = (3,6)(1,2,5,3,4,6,7,8) = (1,2,5,6,7,8)(3,4). Ekkor két Vágást,
majd egy
Összeolvasztást
alkalmaztunk.
(1,2,5,3,4,6,7,8) → (1,2,5,3,4), (6,7,8) → (1,2,5), (6,7,8), (3,4) (1,2,5,6,7,8), (3,4) Ekkor m1 = 8, m2 = 4, így z = min(4,8) = 4, α0 (4) = 3, Id(4) = 5, p32 = (3,5). Így a harmadik blokk-cserét alkalmazva:
σ3 = p32 p31 = (3,5)(3,6) α = (3,5)(1,2,5,6,7,8)(3,4) = (1,2,3,4,5,6,7,8) = Id A legutolsó lépésben Idα−1 -t már felesleges kiszámolnunk. Végül három
Vágást,
és 3
Összeolvasztást
alkalmaztunk.
(1,2,5,6,7,8)(3,4) → (1,2,5,6,7,8)(3), (4) → (1,2), (5,6,7,8), (3), (4) (1,2), (5,6,7,8), (3), (4) → (1,2,3), (5,6,7,8), (4) → (1,2,3,4), (5,6,7,8) → (1,2,3,4,5,6,7,8).
1.4. Lineáris kromoszómákra vonatkozó kiterjesztett algoritmus 1.4.1. Eredeti algoritmus
A fenti algoritmus kiterjeszthet® lineáris kromoszómákra is, azaz arra azt esetre, amikor α =
(a1 , · · · , an ) permutációt egy genom lineáris kromoszómájának feleltetjük meg, cirkuláris helyett. Az ötlet az, hogy illesszünk egy szeparátorként szolgáló 0-t α elejére, majd jelöljük az így kapott permutációt α0 = (0, a1 , · · · , an )-nel, ezután gondoljunk úgy α0 -re mint egy cirkuláris kromoszómára. Ahhoz 17
hogy megtaláljuk azt az optimális blokk-csere sorozatot, amely α0 -t az identitásba transzformálja, vigyáznunk kell, hogy ne alkalmazzunk olyan blokk-cseréket, amelyek tartalmazzák a 0-t, ugyanis ezek kiválasztott 2 blokkja közül valamelyik a lineáris kromoszómában már nem alkot blokkot. Viszont, ha csak olyan blokk-cseréket alkalmazzunk, amelyek nem tartalmazzák a 0-t, akkor azok optimális blokk-cserék lesznek α-n is, így α-ra is megkapjuk az optimális megoldást. Figyelnünk kell tehát a 0 elhelyezkedését a permutációban. Ha a kiválasztott blokk-csere nem tartalmazza a 0-t, akkor végrehajthatjuk, ha tartalmazza, akkor pedig belátjuk, hogy tudunk olyan blokk-cserét találni, amelyet alkalmazva eredményül ugyanazt a permutációt kapjuk, viszont egyik blokk sem tartalmazza a 0-t. Célunk tehát egy olyan algoritmust készíteni, amib®l megkapott σ10 , · · · , σδ0 minimális blokk-csere sorozatra teljesül, hogy az egyik operációnál megcserélt két blokk se tartalmazza a 0-t. A következ®ekben leírjuk, hogyan módosítjuk az eredeti algoritmust úgy, hogy egyik σi0 kiválasztott 2 blokkja se tartalmazza 0-t. Ha az eredeti algoritmus által kiválasztott σi0 = (u, v)(x, y) blokk-csere két,
B1 , B2 blokkja közül egyik sem tartalmazza a 0-t, akkor hajtsuk végre a blokk-cserét. Ha valamelyik blokk tartalmazza, akkor két eset lehetséges : 1.eset :
B1 és B2 nem szomszédosak. Tegyük fel, hogy (x, y) = (ai , aj ), (u, v) = (ak , al ). Ekkor
(u, v)(x, y)α0 = (ak , · · · , aj−1 , ai , · · · , ak−1 , al , · · · , an , a0 , a1 , · · · , ai−1 , aj , · · · , al−1 ) = (ai , · · · , ak−1 , al , · · · , an , a0 , a1 , · · · , ai−1 , aj , · · · , al−1 , ak , · · · , aj−1 ) Tegyük fel, hogy B1 = (al , · · · , an , a0 , a1 , · · · , ai−1 ), B2 = (ak , · · · , aj−1 ), ekkor B1 tartalmazza a 0-t. Jelöljük a permutáció másik két szegmensét A1 = (ai , · · · , ak−1 )-gyel, illetve A2 = (aj , · · · , al−1 )-gyel. Az ötlet az, hogy cseréljük meg A1 -t és A2 -t, mivel a α0 -re cirkuláris kromoszómaként tekintünk, ezért eredményként ugyanazt a permutációt fogjuk kapni. Ezt úgy érjük el, hogy felcseréljük (u, v) és (x, y) szerepét abban az értelemben, hogy (u, v) legyen a hasítás operáció (x, y) pedig az egyesítés, majd alkalmazzuk (x, y)(u, v)-t (u, v)(x, y) helyett. Mivel (u, v) és (x, y) diszjunkt ciklusok és α0 -re mint cirkuláris kromoszómára tekintünk, ezért (x, y)(u, v)α0 = (u, v)(x, y)α0 .
(x, y)(u, v)α0 = (ai , · · · , al−1 , ak , · · · , ai−1 , aj , · · · , an , al , · · · , a0 , a1 , · · · , aj−1 ) = (ak , · · · , aj−1 , ai , · · · , ak−1 , al , · · · , an , a0 , a1 , · · · , ai−1 , aj , · · · , al−1 ) Eredményként ugyanazt a permutációt kaptuk, és az (x, y)(u, v) által megcserélt blokkok egyike sem tartalmazza 0-t. 2.eset :
B1 , B2 szomszédosak. Tegyük fel, hogy B1 tartalmazza 0-t, és α0 = (B2 , B1 , B3 ) =
(ai , ai+1 , · · · , ak−1 , al , al−1 , · · · , an , a0 , a1 , · · · , ai−1 , aj , aj+1 , · · · , al−1 , ak , ak+1 , · · · , aj−1 ) B2 = (ai , ai+1 , · · · , ak−1 ) , B1 = (al , al−1 , · · · , an , a0 , a1 , · · · , ai−1 ) , B3 = (aj , · · · , al−1 , ak , · · · , aj−1 ) Mivel α0 -re mint cirkuláris kromoszómára tekintünk, az ötlet az, hogy B1 és B2 cseréje helyett hajtsuk végre B2 és B3 cseréjét. Mivel a blokkok szomszédosak voltak, ezért feltehet®, hogy x = u vagy y = v . Ha x = u, akkor (u, v)(x, y) = (x, v)(x, y) = (x, y)(v, y), (x, y)(v, y)-t alkalmazva B2 és B3 cseréjéhez 18
jutunk. Ha y = v , akkor (u, v)(x, y) = (u, y)(x, y) = (u, x)(u, y), (u, x)(u, y)-t alkalmazva pedig szintén
B2 és B3 fog megcserél®dni. Ezek után a teljes algoritmus a 1.13. ábrán látható. Mivel minden lineáris kromoszómán alkalmazott blokk-csere ugyanannak a blokk-cserének felel meg cirkuláris kromoszómán, és mivel minden cirkuláris kromoszómán alkalmazott blokk-cseréhez tudunk olyan blokk-cserét találni lineáris kromoszómán, hogy a transzformáció utáni permutáció ugyanaz lesz, ezért a lineáris kromoszómáknak megfeleltetett α0 és Id permutációk blokk-csere távolsága egyenl® lesz a cirkuláris kromoszómáknak megfeleltetett α és Id permutációk δ blokk-csere távolságával. Másrészt, ha tudunk találni cirkuláris kromoszómák esetében egy optimális megoldást, akkor lineárisak esetében is fogunk tudni, és fordítva. Az optimális blokk-csere sorozat azonban csak akkor fog megegyezni, ha az a lineáris kromoszómákra volt megoldás. Ha a cirkuláris kromoszómákra találtunk egy optimális megoldást, akkor csak egy neki megfelel®t tudunk találni lineáris kromoszómákra vonatkozóan. Így azaz algoritmus, ami megoldja a blokk-csere problémát lineáris kromoszómákra, megoldja cirkuláris kromoszómákra is.
1.25. Tétel.
A blokk-cserékkel való rendezés problémája a cirkuláris, illetve a lineáris kromoszómákra
vonatkozó esetben lényegében ekvivalens egymással.
1.4.2. Gyorsított algoritmus
A permutációs fák segítségével itt is alkalmazhatunk gyorsítást. A teljes algoritmus a 1.14. ábrán látható. Azt kell csak meggondolnunk, hogy a permutációs fa hogyan változik egy-egy lépés után, illetve, hogy hogyan és hány lépés alatt tudjuk nyomon követni a szeparátorként szolgáló 0 elem helyzetét. Mivel csak olyan blokk-cseréket fogunk alkalmazni, amelyek nem tartalmazzák a 0-t, ezért a permutációs fa úgy fog változni, ahogy a cirkuláris kromoszómákra vonatkozóan változott volna. Másrészt, egy adott elem pozícióját a permutációs fában O(log(n)) lépésben meg tudjuk mondani, így:
1.26. Tétel.
A lineáris kromoszómákra vonatkozó blokk-cserékkel való rendezés gyorsított algoritmusa
O(n + δ log(n))
m¶veletigény¶.
Legyen példaként α = (2,1,4,3,5) egy lineáris kromoszómának megfeleltetett permutáció, és alkalmazzuk rá a gyorsított algoritmust. Egészítsük ki, majd tekintsünk α0 = (0,2,1,4,3,5)-re egy cirkuláris kromoszómának megfeleltetett permutációként.
6−2 n − f (Idα−1 ) = =2 2 2 Azaz α már 2 blokk-cserével az identitásba transzformálható, jelölje ezeket Idα0−1 = (0)(1,3,5,4,2), δ =
σ1 = p12 p11 , σ2 = p22 p21 Az els® lépésben legyen p11 = (x, y) = (1,3), és α0 = (1,3)(0,2,1,4,3,5) = (0,2,3,5)(1,4). Itt a permutációs fában két
Vágást,
és egy
Összeolvasztást
alkalmaztunk.
(0,2,1,4,3,5) → (0,2,1,4), (3,5) → (1,4), (0,2), (3,5) 19
(1,4), (0,2), (3,5) → (1,4)(0,2,3,5) Ekkor m1 = 5, m2 = 4, z = min(4,5) = 4, α0 (4) = 1, I(4) = 5, p21 = (u, v) = (1,5). Ekkor az x = u eset áll fent, így az els® blokk-cserét alkalmazva
σ1 = (x, y)(v, y) = (1,3)(5,3) α0 = (x, y)(v, y)α = (1,3)(5,3)(0,2,1,4,3,5) = (0,2,3,1,4,5) Idα0−1 = (x, y)(v, y)Idα0−1 = (1,3)(5,3)(0)(1,3,5,4,2) = (0)(1,5,4,2,3) Ekkor (3), (1,4) blokkokat cseréltük meg, amik egyike se tartalmazza a 0-t, illetve a permutációs fára két
Vágást,
majd 3
Összeolvasztást
alkalmaztunk.
(0,2,3,5)(1,4) → (0,2,3), (5), (1,4) → (0,2,3), (5), (1), (4) (0,2,3), (5), (1), (4) → (0,2,3,1), (4), (5) → (0,2,3,1,4), (5) → (0,2,3,1,4,5) A második lépésben legyen p21 = (x, y) = (4,2), α0 = (4,2)(0,2,3,1,4,5) = (0,4,5)(1,2,3). Ekkor két Vágást,
és egy
Összeolvasztást
alkalmaztunk.
(0,2,3,1,4,5) → (0,2,3,1), (4,5) → (0), (2,3,1), (4,5) (0), (2,3,1), (4,5) → (0,4,5)(1,2,3) Ekkor m1 = 5, m2 = 3, ekkor z = min(3,5) = 3, α0 (3) = 1, I(3) = 4, p22 = (u, v) = (1,4) = (4,1). Ekkor ismét az x = u eset áll fent, és a második blokk-cserét alkalmazva :
σ2 = (4,2)(1,2) α0 = (4,2)(1,2)(0,2,3,1,4,5) = (0,1,2,3,4,5) = Id Ekkor a (2,3), (1) blokkokat cseréltük meg, végeredményként pedig az identitást kaptuk. A permutációs fában pedig három
Vágást,
és 3
Összeolvasztást
alkalmaztunk.
(0,2,3,1,4,5) → (0,2,3), (1,4,5) → (0), (2,3)(1,4,5) → (0), (1), (4,5), (2,3) (0), (1), (4,5), (2,3) → (0,1), (4,5), (2,3) → (0,1,2,3), (4,5) → (0,1,2,3,4,5)
1.5. Alkalmazás a vibrió fajok evolúciójában
A
V. vulni cus
sérülések, illetve tengeri ételek által terjesztett fert®zések kórokozója, amely sok
morfológiai és biokémiai hasonlóságot mutat más emberi vibrió kórokozókkal, köztük a val és a cholerae
V. parahaemolyticus -szal.
El Tor 416961,
El®ször 2003-ban hozták nyilvánosságra a
V. parahaemolyticus
V. cholerae -
V. vulni cus
YJ016,
V.
RIMD 2210633 törzsek teljes genomját, melyek mind-
egyikében két-két cirkuláris kromoszóma található, a következ® információtartalommal: 20
Törzs
Kromoszóma
Méret (Mbps)
V.vulni cus YJ016
1 (VV1)
3.4
V.vulni cus YJ016
2 (VV2)
1.9
V.parahaemolyticus RIMD 2210633
1 (VP1)
3.3
V.parahaemolyticus RIMD 2210633
1 (VP2)
1.9
V.cholerae El Tor N16961
1 (VC1)
3.0
V.cholerae El Tor N16961
2 (VC2)
1.0
1.2. táblázat. A három vibrió törzs cirkuláris kromoszómáinak információ tartalma Chen hasonlította össze el®ször a három vibrió fajban a konzervált génszekvenciák pozícióját, illetve az örökít®anyagok mozgását a vibriók két kromoszómája között. Eredményként a V. vált génszakaszai nagyobb fokú hasonlóságot mutattak a
V.parahaemolyticus -szal,
val, amib®l azt a következtetést vonták le, hogy evolúciós szempontból a V.parahaemolyticus -hoz,
és elhelyezkedését a
mint a
V.cholerae -hoz.
V.vulni cus
illetve a
vulni cus
mint a
V.vulni cus
konzer-
V.cholerae -
közelebb áll a
Chen ezután megvizsgálta a gének számát, eloszlását
V.cholerae
genomjaiban, amib®l kimutatható volt, hogy a
duplikációk és transzpozíciók, mint mutációk számos alkalommal felléptek a két faj evolúciója során. Mivel a transzpozíció a blokk-csere egy speciális esete, a fenti összehasonlító genomikai eredmények támogatására számítógépes programként implementálták a cirkuláris kromoszómákra vonatkozó algoritmust. Az alkalmazás el®tt azonban meghatározták a duplikált, illetve konzervált génszakaszokat a vibriók els®, illetve második kromoszómájában a COSINE nev¶ program segítségével. Mivel a konzervált génszakaszok az evolúció során nem, vagy csak alig változnak egy nemzetségen belül az így megtalált szekvenciákat törölték a megfelel® kromoszómákból. A megmaradt szakaszokat szekvenciálisan egy új, nagy réteggé olvasztották össze, majd erre alkalmazták a cirkuláris kromoszómákra vonatkozó algoritmus programként implementált változatát. Az összehasonlítást páronként elvégezték a vibriók megfelel® kromoszómáin, meghatározva a megfelel® blokk-csere távolságokat.
VV1
VP1
VC1
VV2
VP2
VC2
VV1
-
39
69
VV2
-
3
6
VP1
39
-
65
VP2
3
-
7
VC1
69
65
-
VC2
6
7
-
1.3. táblázat. Blokk-csere távolság VV1, VP1, VC1 illetve VV2, VP2 és VC2 között Az így kapott adatok egybevágnak Chen eredeti genomikai megközelítéseivel, amivel újabb bizonyítékot adtak a három vibrió faj között megsejtett evolúciós kapcsolatra.
21
Input : A módosított α0 = (0, a1 , · · · , an ) permutáció ; Output : Egy minimális σ10 , σ20 , · · · , σδ0 blokk-csere sorozat, azzal a feltétellel, hogy egyik σi által megcserélt 2 blokk sem tartalmazza 0-t; Legyen δ =
for
n−f (Idα−1 ) ; 2
i = 1 to
δ
do
válasszunk ki tetsz®legesen két szomszédos x és y elemet Idα−1 -ben ((x, y) hasítás lesz α-n) ; forgassuk el α = (a1 , · · · , an )-t úgy, hogy a1 = x és tegyük fel, hogy y = ak ;
for
j = 1 to n
do
index(aj ) = j ;
end keressünk két olyan u, v szomszédos elemet Idα−1 (x, y)-ban, hogy index(u) ≤ k − 1, és index(v) ≥ k ( (u, v) egyesítés lesz (x, y)α-n ;
if
ha (u,v)(x,y) tartalmazza 0-t
if
x=u
if
or
x=u
y=v
then
then
then
σi = (x, y)(v, y); α = (x, y)(v, y)α; Idα−1 = Idα−1 (x, y)(v, y);
else σi = (u, x)(u, y); α = (u, x)(u, y)α; Idα−1 = Idα−1 (u, x)(u, y);
end else σi = (x, y)(u, v); α = (x, y)(u, v)α; Idα−1 = Idα−1 (x, y)(u, v);
end else σi = (u, v)(x, y); α = (u, v)(x, y)α; Idα−1 = Idα−1 (u, v)(x, y);
end end 1.13. ábra. Módosított algoritmus lineáris kromoszómákra (Lin, Lu, Chang, Tang 2005)
22
Input : A módosított α0 = (0, a1 , a2 , · · · , an ) permutáció ; Output : Egy minimális σ10 , σ20 , · · · , σδ0 blokk-csere sorozat, azzal a feltétellel, hogy egyik σi0 által megcserélt 2 blokk sem tartalmazza 0-t ; Legyen δ =
for
n−f (Idα−1 ) ; 2
i = 1 to δ do válasszunk ki tetsz®legesen két szomszédos x és y elemet Idα0−1 -ben ((x, y) hasítás lesz α0 -n)
;
α0 = (x, y)α0 ; keressük meg a maximális m1 ill. m2 elemeket rendre C1 -ben és C2 -ben ; legyen z = min(m1 , m2 ) ; legyen u = α0 (z) és v = Id(z) (u és v ekkor szomszédos Iα01 -ban, és (u, v) egyesítés α0 -n) ;
if
ha (u,v)(x,y) tartalmazza a 0-t
if
x=u
if
or
x=u
y=v
then
then
then
σi0 = (x, y)(v, y); α0 = (x, y)(v, y)α0 ; Idα0−1 = Idα0−1 (x, y)(v, y);
else σi0 = (u, x)(u, y); α0 = (u, x)(u, y)α0 ; Idα0−1 = Idα0−1 (u, x)(u, y);
end else σi0 = (x, y)(u, v); α0 = (x, y)(u, v)α0 ; Idα0−1 = Idα0−1 (x, y)(u, v);
end else σi0 = (u, v)(x, y); α0 = (u, v)(x, y)α0 ; Idα0−1 = Idα0−1 (u, v)(x, y);
end end 1.14. ábra. Blokk-cserékkel való rendezés gyorsított algoritmusa a lineáris kromoszómákra
23
2. fejezet
Transzpozíciók A transzpozíciók fogalmát, illetve a transzpozíciókkal való rendezés alapproblémáját Bafna és Pevzner de niálta 1998-ban [3]. A lineáris kromoszómaszállal rendelkez® genomok esetében pontos megoldást nem, de egy 1.5-approximációs algoritmust is adott, mely O(n2 ) m¶veletigény¶, ahol n a genomban szerepl® gének számát jelenti. Az algoritmust ezt követ®en sokan egyszer¶sítették. El®ször Christie dolgozott ki 1999-ben egy javított 1.5-approximációs algoritmust, melynek m¶veletigénye O(n4 ) [8], majd az algoritmus m¶veletigényét Walter csökkentette le O(n3 )-re 2003-ban [27], az approximációs arányt megtartva. A második javítást Hartman végezte el 2003-ban, az általa kidolgozott algoritmus szintén 1.5approximációs, m¶veletigénye O(n2 ) [17]. Hartman és Shamir látta be 2006-ban el®ször, hogy az alapprobléma megoldása lineáris és cirkuláris kromoszómákra lényegében ekvivalens. Kidolgoztak egy új egyszer¶sített, O(n2 ) m¶veletigény¶ 1.5-ös approximációs algoritmust, melynek futásideje egy speciális p adatstruktúrával [21] O(n3/2 log(n))-re csökkenthet® [18]. Ez az eddig ismert leggyorsabb algoritmus a transzpozíciókkal való rendezésre. A máig létez® legjobb, 1.375-approximációs algoritmust Elias és Hartman dolgozta ki 2006-ban [12]. Az algoritmus helyességének bizonyítása számítógépes segítséggel történt, az els® matematikai bizonyítást Dias adta 2010-ben [9] A probléma nehézsége egészen 2010-ig nyitott maradt, amikor Fertin és Rusu belátta, hogy NP-nehéz [4]. A legújabb eredmények a biológiai alkalmazásokban játszanak fontos szerepet. Dias és Dias vette észre, hogy egy-egy permutációban bizonyos struktúrák gyakrabban fordulnak el®, így bizonyos feltételeknek megfelel® transzpozíciók gyakrabban alkalmazhatóak. Ha ezeket a feltételeket vizsgáljuk el®ször, akkor a már meglév® algoritmusok gyakorlatban sokkal hatékonyabbá tehet®k úgy, hogy közben a m¶veletid®t és az approximációs arányt is megtartják. Dias és Dias el®ször Bafna és Pevzner 1.5-approximációs, majd ugyanezt a gondolatot követve Elias és Hartman 1.375-approximációs algoritmusát terjesztette ki 2010-ben [9], [10] egy gyakorlatban sokkal hatékonyabban m¶köd® algoritmussá. A második fejezetet a következ®képpen fogjuk felépíteni : az els® részben de niáljuk a transzpozíció, transzpozíciós távolság fogalmát, bevezetjük az transzpozíciókkal való rendezés alapproblémáját, és belátjuk, hogy ez lineáris és cirkuláris kromoszómák esetében lényegében ekvivalens. A második részben adunk egy alsó és két fels® korlátot a távolságra, megvizsgáljuk a törésponti gráf köreinek struktúráját. 24
Szerz®k
M¶veletigény
Approximációs arány
Év
Bafna, Pevzner
O(n2 )
1.5
1998
Christie
O(n4 )
1.5
1999
Walter
O(n3 )
1.5
2003
Hartman, Shamir
O(n2 )
1.5
2003
Hartman, Shamir
O(n3/2
1.5
2006
Elias, Hartman
-
1.375
2006
Dias, Dias
-
1.375
2010
Dias, Dias
O(n2 )
1.5
2010
p log(n))
2.1. táblázat. Eddig elért eredmények a transzpozíciókkal való rendezés alapproblémájában Bevezetjük az irányított, irányítatlan körök fogalmát, megnézzük milyen transzpozíciók alkalmazása nyújtana mindig optimális megoldást, majd ezek segítségével ismertetjük az els®, Bafna és Pevzner által adott 1.5-approximációs algoritmust. A harmadik részben tovább vizsgáljuk a törésponti gráf köreinek struktúráját, bevezetjük a keresztez® és illeszked® körök fogalmát, megnézzük, hogy az adott genomnak megfelel® permutációt képesek vagyunk-e úgy szebb alakra transzformálni, hogy közben az optimális megoldás ne változzon. Ezek segítségével ismertetjük Hartman és Shamir egyszer¶sített 1.5p approximációs algoritmusát, melynek m¶veletigénye egy speciális adatstruktúrával O(n3/2 log(n))-re csökkenthet®. Ez az algoritmus a máig ismert leggyorsabb. A harmadik részben adunk egy alsó korlátot a szimmetriacsoport, fels® korlátot a 3-permutációk, illetve egy-egy pontos értéket a 2-permutációk és az egyszer¶ permutációk transzpozíciós átmér®jére, melyek segítségével ismertetjük Elias és Hartman 1.375-approximációs algoritmusát, mely az eddig ismert legjobb approximációs algoritmus. 2.1. Alapfogalmak
Legyen adott egy lineáris kromoszómának megfelel® σ = [11,12,9,8,4,2,3,5,6,7,1,13] permutáció.
2.1. De níció. Transzpozíciónak
nevezzük azt a transzformációt, mely egy adott π = [1, · · · , n]
permutációban felcserél két szomszédos blokkot. Jelöljük p(i, j, k)-val azt a transzpozíciót, amely megcseréli a [πi , · · · , πj−1 ] és a [πj , · · · , πk−1 ] blokkokat (1 ≤ i < j < k ≤ n + 1, k ∈ / [i, j]), azaz a
[πi , · · · , πj−1 ] blokknak megfelel® génszekvenciát egy új helyre, a πk−1 és πk gének közé közé illeszti az adott kromoszómában. Legyen p(i, j, k) = p(5,7,11), ez a transzpozíció σ -ban megcseréli a [4,2] és [3,5,6,7] blokkokat, azaz [4,2]-t [7] és [1] közé illeszti. A transzformáció utáni kromoszómának megfelel® permutáció pσ =
[11,12,9,8,3,5,6,7,4,2,1,13]. A feladat az els® fejezetben kit¶zött problémához hasonló. Szerenténk meghatározni azt a minimális számot, és a hozzá tartozó transzpozíció sorozatot, mellyel két adott genom közül az egyik a másikba 25
2.1. ábra. A π permutációra alkalmazott p(i, j, k) transzpozíció
transzformálható. Mivel a gének címkézése az adott genomban itt is tetsz®leges, ezért a célgenomnak megfelel® permutációt választhatjuk az identitásnak.
2.2. De níció.
Egy adott π permutáció transzpozíció távolsága az a minimális szám, ahány transz-
pozíció szükséges ahhoz, hogy az adott permutációt az identitásba vigyük. Jelölés: dT (π). Mivel maga a feladat megoldása NP-nehéz, ezért csak alsó és fels® korlátot tudunk mondani a keresett távolságra, illetve csak approximációs algoritmusokat adhatunk. A feladat megoldásáról azonban a blokk-cserékhez hasonlóan a következ®t tudjuk mondani:
2.3. Tétel.
A transzpozíciókkal való rendezés problémája a lineáris és cirkuláris kromoszómákra vo-
natkozóan lényegében ekvivalens. Bizonyítás.
Azt kell csak meggondolnunk, hogy minden lineáris kromoszómán vett transzpozíció ugyan-
annak a transzpozíciónak felel meg cirkuláris kromoszómán, és hogy minden cirkuláris kromoszómán vett transzpozícióhoz tudunk találni egy olyan transzpozíciót, hogy a transzformáció utáni kromoszóma ugyanaz lesz, és ez lineáris kromoszómán ugyanannak a transzpozíciónak felel meg. Vegyünk egy
n elem¶ lineáris kromoszómának megfelel® π permutációt. Adjunk hozzá egy n + 1. elemet, legyen ez πn+1 = x, majd zárjuk be a kört, az így keletkezett cirkuláris kromoszómának megfelel® permutációt jelölje π 0 . Tudjuk, hogy minden π -n végrehajtott transzpozíció ugyanannak a transzpozíciónak felel meg π 0 -n. Vegyünk most π 0 -n egy p transzpozíciót, ha ennek egyik blokkja sem tartalmazta x-et, akkor ez ugyanannak a transzpozíciónak felel meg π -n is. Tekintsük azt az esetet, amikor p tartalmazta x-et. Ekkor p π 0 -t 3 olyan szegmensre vágja, hogy bármelyik két szegmens szomszédos, így minden olyan transzpozícióhoz π 0 -n, ami tartalmazza x-t, tudunk találni egy olyan p0 transzpozíciót, amely nem tartalmazza, és a két transzpozíciót végrehajtva ugyanazt az eredményt kapjuk, p0 pedig ugyanannak a transzpozíciónak felel meg π 0 -n, mint π -n. Az approximációs algoritmusok ismertetésében a kromoszómatípusok nem fognak szerepet játszani, mindig azt a típust fogjuk választani, amely szerinti tárgyalásmód az egyszer¶bb. 2.2. 1.5-approximációs algoritmus
Az 1.5-approximációs algoritmus ismertetéséhez el®ször alsó, majd fels® korlátokat fogunk adni a transzpozíciós távolságra. Az alsó korlátot meg tudjuk adni azzal, ha csak a körök paritását vizsgáljuk.
26
Itt azonban nem lesz igaz a blokk-cseréknél érvényben lév® fels® korlát, a körök számát nem minden lépésben tudjuk majd kett®vel növelni. Ahhoz, hogy a fels® korlátot is megadjuk azt kell megvizsgálnunk, hogy milyen körstruktúrák engednek meg olyan transzpozíciókat, melyekkel kett®vel tudjuk növelni a körök számát. Célunk az lesz, hogy a legtöbb ilyet alkalmazzuk egy adott hosszúságú lépéssorozatban. Az, hogy milyen gyakran tudunk ilyen transzpozíciókat alkalmazni, a körök hosszúságától fog függeni. Ennek segítségével egy 1.75-approximációs algoritmust adható. Ahhoz, hogy ezt az arányt 1.5-re javítsuk, olyan speciális transzpozíciókat kell alkalmaznunk, amik a páratlan körök számát növelik. 2.2.1. Alsó korlátok
Az els® fejezetben bevezetett törésponti gráfot fogjuk használni modellként. A következ®ekben azt fogjuk vizsgálni, hogyan változik a körök száma a gráfban egy-egy transzpozíció alkalmazása után. Mivel csak az identitásnak van n + 1 köre, célunk itt is a körök számának növelése lesz. Legyen adott π permutáció, a neki megfelel® G(π) törésponti gráf és a p transzpozíció. Jelölje
∆c(π) = c(πp) − c(π) a körök számának megváltozását a G(π)-ben p alkalmazása után.
2.4. Tétel.
Egy adott
π
permutációban
∆c(π) ∈ {−2,0, +2}.
Mivel egy tetsz®leges transzpozíció legfeljebb 2-vel növelheti a körök számát, a következ® alsó korlátot kapjuk:
2.5. Tétel.
dT (π) ≥
n+1−c(π) . 2
Legyen C egy tetsz®leges kör G(π)-ben. C
páros,
ha páros sok fekete élt tartalmaz,
páratlan
egyébként. Jelölje codd (π) a páratlan, ceven (π) a páros körök számát G(π)-ben. Mivel az identitásnak csak páratlan körei vannak, jobb alsó korláthoz juthatunk, ha csak ezeket próbáljuk növelni.
2.6. Tétel.
Egy adott
π
permutációban
∆codd (π) ∈ {−2,0, +2}.
Így a jobb alsó korlát :
2.7. Tétel.
dT (π) ≥
n+1−codd (π) . 2
2.2.2. Fels® korlátok
Legyen x ∈ {−2, 0, 2}. Egy transzpozíciót x-mozgásnak hívunk, ha ∆c(π) = x. Ahhoz, hogy minél gyorsabban rendezzünk, célunk minél több 2-mozgást használni. Az fogja adni a transzpozíciós távolságra vonatkozó fels® korlátot, hogy hány 2-mozgást tudunk biztosan használni egy adott hosszúságú lépéssorozatban.
2.8. Tétel.
Tetsz®leges
π
permutációra vagy létezik egy 2-mozgás vagy létezik egy 0-mozgás, melyet
egy 2-mozgás követ.
Mivel két lépésben mindig tudjuk legalább kett®vel növelni a körök számán, így a következ® fels® korlátot kapjuk: 27
2.9. Tétel.
dT (π) ≤ n + 1 − c(π).
A 2.5. Tétel és a 2.9. Tétel segítségével már tudunk egy 2-es approximációs algoritmust adni. A következ®ekben egy jobb approximációs arányt próbálunk elérni úgy, hogy növeljük a 2-mozgások számát. Az ötlet az, hogy nem engedünk meg -2-mozgást, továbbá elérjük, hogy bármely két 0-mozgás között legyen legalább két 2-mozgás. Mivel a p(i, j, k) transzpozíció az i,j ,k éleket vágja ketté, azt mondjuk, hogy p az i,j ,k éleken
hat.
Legyen C egy adott kör G(π)-ben. Azt mondjuk, hogy p(i, j, k) C -n hat, ha az i,j ,k élek mindegyike
C -hez tartozik. Tegyük fel, hogy C k -hosszú, ha k > 3, akkor C -t
rövid körnek nevezzük. 2.10. Tétel.
Ha
G(π)
hosszú körnek, ellenkez® esetben
tartalmaz hosszú kört, akkor vagy létezik 2-mozgás vagy létezik egy 0-mozgás,
melyet két egymás utáni 2-mozgás követ.
A 2.10. Tétel miatt tetsz®leges három egymás utáni lépésben a körök számát legalább 4-gyel tudjuk növelni, tehát átlagosan ∆c(p) =
4 3,
ami jobb, mint a 2.8. Tétel által szolgáltatott ∆c(p) = 1. Ez
azonban csak akkor alkalmazható, ha G(π)-nek vannak hosszú körei. Ha nincsenek, akkor a legjobb, melyet csinálhatunk, ha egy 0-mozgás után egy 2-mozgás-t alkalmazunk. Ez 4 db 1-hosszú kört csinál 2 db 2-hosszú körb®l. Ekkor ∆c(p) =
4−2 2
= 1 ugyan, de ∆codd (p) =
4−0 2
= 2, amivel maximálisan
megnöveltük a páratlan körök számát. A fentiek alapján a következ® algoritmust készíthetjük el :
TRendezés(π) ; Input : Egy tetsz®leges π = [π1 , · · · , πn ] permutáció ; Output : Egy p1 , p2 , · · · , pk transzpozíció sorozat ; while G(π)-nek van hosszú köre do alkalmazzunk vagy egy 2-mozgást vagy egy 0,2,2 mozgást ;
end if G(π)-nek már csak rövid körei vannak then alkalmazzunk egy 0-mozgást majd egy 2-mozgást ;
end 2.2. ábra. TRendezés(π) algoritmusa a lineáris kromoszómák rendezésére (Bafna, Pevzner 1998)
2.11. Tétel.
A TRendezés(π) 1.75-approximációs.
Mivel a 2.10 tétel nem garantálja a páratlan körök növelését minden 2-mozgásnál, célunk ezt a feltételt er®síteni. Ha jól megválasztott 2-mozgásokat alkalmazunk, akkor elérhet®, hogy minden egyes lépésben a páratlan körök száma legalább 2-vel n®. Nevezzünk p transzpozíciót
2.12. Tétel.
Ha
G(π)
érvényesnek, ha ∆c(p) = ∆codd (p).
tartalmaz hosszú kört, akkor vagy létezik egy érvényes 2-mozgás, vagy létezik
egy érvényes 0-mozgás, melyet két egymás utáni érvényes 2-mozgás követ.
28
A fentiek alapján már tudjuk kezelni azt a helyzetet, amikor G(π)-nek csak hosszú körei vannak. A rövid körök kezelésére a következ® ötletet alkalmazzuk : próbáljuk elérni, hogy egy 0-mozgás is növelje a páratlan körök számát a gráfban. Egy p 0-mozgást
jónak
nevezünk, ha kett®vel növeli a páratlan
körök számát.
2.13. Tétel.
Ha
G(π)
csak rövid köröket tartalmaz, akkor egy jó 0-mozgás után mindig tudunk egy
érvényes 2-mozgást végrehajtani.
A fenti következtetések után az algoritmus :
TranszpozíciósRendezés1(π) ; Input : Egy tetsz®leges π = [π1 , · · · , πn ] permutáció ; Output : Egy p1 , p2 , · · · , pk transzpozíció sorozat ; while G(π)-nek van hosszú köre do alkalmazzunk vagy egy érvényes 2-mozgást vagy egy érvényes 0,2,2 mozgást ;
end if G(π)-nek már csak rövid körei vannak then alkalmazzunk egy jó 0-mozgást majd egy érvényes 2-mozgást ;
else end 2.3. ábra. TranszpozíciósRendezés1(π) algoritmusa a lineáris kromoszómák rendezésére (Bafna, Pevzner 1998)
2.14. Tétel.
TranszpozíciósRendezés1(π) 1.5-approximációs, és egy tetsz®leges
3 séhez legfeljebb 4 (n
+ 1 − codd (π))
π
permutáció rendezé-
transzpozíciót használ.
2.3. Egyszer¶sített 1.5-approximációs algoritmus
A tételek és a de níciók egyszer¶bb kimondása érdekében ebben a részben csak cirkuláris kromoszómákkal fogunk foglalkozni. A 2.3. Tétel miatt a lineáris kromoszómákra vonatkozó eddigi eredmények érvényben maradnak, illetve az itt elért eredmények a lineáris esetre is átvihet®ek lesznek. A törésponti gráfot ennek megfelel®en kör alakban fogjuk felrajzolni úgy, hogy a fekete élek a körvonalon fognak elhelyezkedni, a szürke élek pedig a kör húrjai lesznek. Bafna és Pevzner algoritmusában a nehézség az volt, hogy egyszerre kellett kezelnünk hosszú és rövid köröket. A feladat megoldását próbáljuk meg úgy egyszer¶síteni most, hogy csak rövid körökkel kelljen dolgoznunk.
2.15. De níció.
Egy adott π permutációt és a neki megfelel® G(π) törésponti gráfot
nevezzük, ha G(π) csak rövid köröket tartalmaz. 29
egyszer¶nek
A következ®kben megmutatjuk, hogyan tudunk egy tetsz®leges permutációt egy egyszer¶ permutációba transzformálni úgy, hogy közben a permutáció transzpozíciós távolságára vonatkozó alsó korlát nem változik. Legyen adott π = (π1 , · · · , πn ) permutáció, készítsük el a neki megfelel® G(π) törésponti gráfot. Vegyünk egy b = (vb , wb ) fekete és egy g = (vg , wg ) szürke élt ugyanazon a C = (· · · , vb , wb , · · · , vg , wg · · · ) körön belül. A következ® m¶veletsorozatot
(g,b)-vágásnak fogjuk hívni. Távolítsuk el el®ször a b és
g éleket, majd vegyünk fel két új v , w csúcsot. Kössük össze fekete éllel vb -t és v -t, illetve w-t és wb -t, ezután szürke éllel wg -t és w-t, illetve v -t és vg -t. A keletkez® új G0 (π) gráfban C -t két kisebb, C1 , C2 körré vágtuk szét.
2.4. ábra. Egy (g, b)-vágás [18]
Hannenhali és Pevzner mutatta meg [16], hogy adott π = (π1 , · · · , πn ) permutáción végrehajtott tetsz®leges (g,b)-vágáshoz mindig létezik olyan π 0 n+1 elem¶ permutáció, ami π -b®l keletkezett egy elem hozzávételével, és a neki megfelel® G(π 0 ) törésponti gráf megegyezik G0 (π)-vel. Azaz, minden (g,b)-vágás tekinthet® egy-egy olyan transzformációnak, amely π -t π 0 -be viszi. Egy (g,b)-vágást bizton-
ságosnak, π és π0 permutációkat pedig ekvivalensnek nevezzük, ha n(π) − codd (π) = n(π0 ) − codd (π), ahol n(π) a π -ben szerepl® elemek száma.
2.16. Tétel.
Minden
π
Legyen
π0
permutáció áttranszformálható egy
π0
egyszer¶ permutációba biztonságos (g,b)-
vágásokkal.
2.17. Tétel. felel
π
egy
π -vel
ekvivalens egyszer¶ permutáció. Ekkor
π0
minden rendezésének meg-
egy olyan rendezése, mely ugyanannyi transzformációt vesz igénybe.
A tételek teljes bizonyítása rendre [16]-ben illetve [23]-ban találhatóak. Az eddigiek alapján az egyszer¶sített 1.5-approximációs algoritmust a következ® lépésekb®l fogjuk felépíteni : a kapott π permutációt áttranszformáljuk egy neki ekvivalens π 0 egyszer¶ permutációba, majd ezen elvégezzük a transzpozíciókkal való rendezést, végül megkeressük a megfelel® rendezést az eredeti permutáción. Mivel a rendezést elég a π 0 egyszer¶ permutáción elvégezni, a neki megfelel® G(π 0 ) törésponti gráf csak 1, 2 és 3-hosszú köröket fog tartalmazni. A célunk, hogy n + 1 darab 1-hosszú kört hozzunk létre, ugyanis ekkor a kapott permutáció az identitás lesz. A feladat így a gráfban található a 2 és 3-hosszú körök 1-hosszú körökre való szétvágása. El®ször megvizsgáljuk a 2-hosszú, azután a 3-hosszú körök esetét. A 2-hosszú körök esetében a következ®t tudjuk mondani : 30
2.18. Tétel.
Ha
G(π)-ben
létezik 2-hosszú kör, akkor mindig létezik 2-mozgás.
A 3-hosszú körök vizsgálatához két új fogalmat vezetünk be. Legyen C k -hosszú kör G(π)-ben, fekete élei legyenek rendre i1 , · · · , ik . Címkézzük meg a fekete éleit bejárási sorrendben 1-t®l k -ig úgy, hogy a kezd® él legyen a legjobboldalibb a gráfban. A bejárás után ha (i1 , · · · , ik ) csökken® sorozatot alkot, akkor C -t
irányítatlan, ellenkez® esetben irányított.
2.5. ábra. (A) Irányítatlan kör (B) Irányított kör [18]
2.19. Tétel.
Ha egy transzpozíció hoz létre 3-hosszú kört, akkor az vagy irányított, vagy irányítatlan.
Az el®z® tétel alapján a 3-hosszú körök esetében két esetet kell csak megvizsgálnunk, ha a kör irányított, illetve ha irányítatlan.
2.20. Tétel.
Ha
G(π)-ben
létezik 3-hosszú irányított kör, akkor mindig létezik 2-mozgás.
Tegyük fel, hogy a G(π 0 )-ben szerepl® összes 2-hosszú és 3-hosszú irányított kört szétvágtuk már, így a következ®kben elég csak az irányítatlan 3-hosszú körökkel foglalkoznunk. Azt fogjuk megmutatni, hogy az ilyen struktúrájú körök mindig megengednek (0,2,2)-mozgást. Egy-egy ilyen m¶velet során 3 lépés alatt 4-gyel tudjuk növelni a körök számát, ez a maximális hatnál másfélszer rosszabb, így ha
(0,2,2)-mozgásokat hajtunk végre egymás után, az 1.5-approximációs arányt fog biztosítani. Egy adott π = (π1 , · · · , πn ) permutáció egy intervallumát
ívnek nevezzük. Két tetsz®leges (πi , πj )
elem (i 6= j) két diszjunkt (πi , · · · , πj−1 ) és (πi−1 , · · · , πj ) ívet határoz meg. Azt mondjuk, hogy 2-2 pár fekete él, (a, b) és (c, d)
keresztezik egymást, ha a és b különböz® ívekben vannak (c, d) pár szerint.
Legyenek C és D tetsz®leges körök G(π)-ben. Azt mondjuk, hogy (a, b) és C keresztezik egymást, ha
C -nek létezik olyan fekete élpárja, ami (a, b)-vel keresztezi egymást. C -t és D-t keresztez®
köröknek hívjuk, ha C -nek létezik olyan fekete élpárja, ami keresztezi D-t. Két fekete élhármast illeszked®nek hívunk, ha az egyik hármas minden éle páronként különböz® ívben van a második hármas szerint. Két 3-hosszú kört
illeszked® köröknek
nevezünk, ha éleik illeszked®ek. A keresztez®, nem keresztez®,
illetve az illeszked® 3-hosszú körök példaként a 2.6. ábrán láthatók.
2.21. Tétel.
Ha
G(π)-ben
létezik két 3-hosszú irányítatlan illeszked® kör, akkor mindig létezik (0,2,2)-
mozgás. Bizonyítás.
A keresett (0,2,2)-mozgás a 2.7. ábrán látható.
31
2.6. ábra. (A) Keresztez® 3-hosszú körök (B) Nem keresztez® 3-hosszú körök (C) Illeszked® 3-hosszú körök [18]
2.7. ábra. A keresett (0,2,2)-mozgás, ami a két irányítatlan, illeszked® 3-hosszú kört hat 1-hosszú körré transzformálja. Minden lépésben az alkalmazott transzpozíciók a csillagozott fekete éleken hatnak. [18]
2.22. Tétel.
Legyen
C
és
D
két olyan irányítatlan, keresztez® kör, amelyek nem illeszked®ek. Ekkor
mindig létezik egy olyan transzpozíció, ami Bizonyítás.
C -t és D-t egy 1-hosszú és egy 5-hosszú körré transzformálja.
Legyenek C fekete élei c1 , c2 , c3 , és tegyük fel, hogy (c1 , c2 ) és D keresztezi egymást.
Egy er®sebb állítást fogunk bizonyítani, amib®l már következik a tétel. Belátjuk, hogy akárhogyan választunk D-b®l egy d fekete élt úgy, hogy (d, c3 ) és (c1 , c2 ) keresztezi egymást, az a transzpozíció, ami a c1 , c2 , d éleken hat, megfelel a tételnek. Három különböz® esetet kell megvizsgálnunk, ezek a 2.8. ábrán láthatóak. Az els® transzpozíció, amely a c1 , c2 és d éleken hat, áttranszformálja C -t és D-t egy 1-hosszú és egy 5-hosszú irányított körré. A második transzpozíció az 5-hosszú körre alkalmazott 2-mozgás, ami egy 3-hosszú irányítatlan és egy két 1-hosszú kört eredményez. Azt mondjuk, hogy az E kör a C és D körök által törhet®, ha E bármely fekete élpárja vagy C -vel vagy D-vel keresztezi egymást. Vegyük példának a 2.9. ábrán lév® köröket. Ekkor az A kör B és C által törhet®, de sem C nem törhet® A és B , sem B nem törhet® A és C által.
2.23. Tétel. és
D
Ha
G(π)-ben
létezik három 3-hosszú irányítatlan
C, D
és
E
kör úgy, hogy
E
törhet®
C
által, akkor mindig létezik (0,2,2)-mozgás.
Bizonyítás.
Ha a három körb®l létezik két olyan, ami illeszked®, akkor a 2.21. Tétel miatt tudunk
alkalmazni egy (0,2,2)-mozgást. Ha nem léteznek illeszked® körök, akkor két esetet különböztetünk meg.
32
2.8. ábra. A 2.22. Tétel három lehetséges esete. [18]
2.9. ábra. 3-hosszú irányítatlan törhet® körök [18]
1. eset :
Létezik két olyan kör, ami nem keresztezi egymást. Ekkor a három körnek csak háromféle
elhelyezkedése lehetséges, ezek a 2.10 ábrán láthatóak. Minden lehetséges esetben mutatunk egy (0,2,2)mozgást. 2. eset :
A három kör kölcsönösen keresztezi egymást, ez a 2.11 ábrán látható. Mivel a C és D
körök irányítatlanok, keresztez®ek és nem illeszked®ek, ezért a 2.22. Tétel feltételei teljesülnek, így tudunk alkalmazni a c1 , c2 és d éleken egy 0-mozgást, ami egy új F irányított körhöz vezet, és E -t irányítottá teszi. Alkalmazzunk E -re egy 2-mozgást, ezután F irányított marad. Mivel F irányított ismét alkalmazhatunk egy 2-mozgást, amivel egy (0,2,2)-mozgáshoz jutunk. Két fekete élt
2.24. Tétel.
összefügg®nek nevezünk, ha össze vannak kötve szürke éllel.
Legyen
olyan körök, melyeket
(bi , bj)
egy irányítatlan kör összefügg® fekete élpárja, ekkor a
(bi , bj)
keresztez.
33
G(π)-ben
léteznek
2.10. ábra. A 2.22. Tétel 2. esetében a három kölcsönösen keresztez® kör lehetséges elhelyezkedései, illetve az alkalmazott (0,2,2)-mozgások. Az egyszer¶ség kedvéért az 1-hosszú köröket csak akkor tüntetjük fel, ha azok az alkalmazott transzpozíció eredményei, ugyanis a kés®bbi lépésekben ezek nem játszanak szerepet [18]
2.11. ábra. Páronként keresztez® körökre alkalmazott 0, majd egy 2-mozgás. A szaggatott vonal vagy egy szürke élet, vagy egy olyan 3-hosszú utat jelöl, amely két fekete és egy szürke élt tartalmaz. [18]
A fenti tételekkel minden esetet lefedtünk, ami az irányítatlan körökre vonatkozik, a tetsz®leges permutációkra vonatkozó algoritmus a 2.12. ábrán látható. Mivel egyik while cikluson belül sem hozhatunk létre hosszú köröket, a permutáció végig egyszer¶ marad az algoritmus futása során. Emeljük ki a két ciklust egy új algoritmusba, és jelöljük EgyszeruTranszpozíciósRendezés(π)-vel. Ekkor ez algoritmus lesz az egyszer¶ permutációk rendezésére. 34
TranszpozíciósRendezés2(π) ; Input : Egy tetsz®leges π = [π1 , · · · , πn ] permutáció ; Output : Egy p1 , p2 , · · · , pk transzpozíció sorozat ; Transzformáljuk át π -t egy vele ekvivalens π 0 egyszer¶ permutációba ;
while G(π)-nek van 2-hosszú köre do alkalmazzunk 2-mozgást ;
end while G(π)-nek van 3-hosszú köre do válasszunk ki egy összefügg® c fekete élpárt egy tetsz®leges C körb®l ;
if
C
irányított
then
alkalmazzunk 2-mozgást ;
else válasszunk ki egy összefügg® d fekete élpárt egy tetsz®leges D körb®l ;
if
C
és
D
illeszked®
then
alkalmazzunk (0,2,2)-mozgást ;
else
ha C és D nem volt illeszked®, akkor létezik egy olyan c0 pár C -ben, ami nem keresztezik D-vel. Válasszunk ki egy tetsz®leges e élpárt E -b®l, ami keresztezik c0 -vel. Ekkor C törhet® E és D által, tehát ; alkalmazzunk (0,2,2)-mozgást ;
end end end 2.12. ábra. TranszpozíciósRendezés2(π) algoritmusa a cirkuláris kromoszómák rendezésére (Hartman, Shamir 2006)
2.25. Tétel.
A EgyszeruTranszpozíciósRendezés(π) 1.5-approximációs algoritmus az egyszer¶ permu-
tációk rendezésére, melynek futásideje Bizonyítás.
O(n2 ).
Mivel az algoritmus során csak 2, illetve (0,2,2)-mozgásokat alkalmazunk, bármelyik három
lépésben tudjuk legalább 4-gyel növelni a körök számát a gráfban. Ez másfélszer rosszabb, mint az optimális, hat körrel vett növelés, így az approximációs arány 1.5. Az els® while ciklus lineáris id®ben végrehajtható, és mivel a második ciklusban nem hozunk létre 2-hosszú köröket, az el®z® ciklust már nem kell iterálnunk. A második ciklus iterációinak száma lineáris, mivel minden iterációban egy 3-hosszú kört vágunk szét három 1-hosszú körre. A ciklus egy iterációja során a legnehezebb feladat megtalálni azt az összefügg® fekete élpárt, mely keresztezi a kiválasztott élpárunkat, majd alkalmazni a transzpozíciót. Ez lineáris, a ciklusban található többi m¶velet pedig 35
konstans id®ben végrehajtható. Így az algoritmus m¶veletigénye O(n2 ) A tétel igaz lesz az eredeti, tetsz®leges permutációkat rendez® algoritmusra is.
2.26. Tétel.
A TranszpozíciósRendezés2(π) 1.5-approximációs algoritmus tetsz®leges permutációk ren-
dezésére, futásideje Bizonyítás.
O(n2 ).
A 2.25. Tétel szerint dT (π 0 ) ≤ 1.5dT (π 0 ), innen 2.7. Tétel szerint
dT (π 0 ) ≤ 1.5dT (π 0 ) ≤ 1.5
n(π 0 ) − codd (π 0 ) n(π) − codd (π) = 1.5 ≤ 1.5dT (π). 2 2
A 2.17. Tétel szerint π -t tudjuk dT (π 0 ) transzpozícióval rendezni, így az approximációs arány 1.5. Mivel az algoritmus els® és utolsó lépése is lineáris id®ben végrehajtható, a két ciklus m¶veletigénye pedig az el®z® tétel miatt O(n2 ), a teljes algoritmus m¶veletigénye is O(n2 ) lesz. A m¶veletigény csökkentésést egy új adatstruktúra bevezetésével érték el, a teljes leírás [21]-ben található. Ez az els® fejezetben leírtakhoz hasonlóan egy kiegyensúlyozott bineáris keres®fa, és a m¶p veletek, melyek az összeolvasztásokat és a vágásokat biztosítják O( n log(n)) id®ben végrehajthatóak lesznek. Ezek segítségével képesek vagyunk az algoritmus legnehezebb lépésének m¶veletidejét csökp kenteni, azaz megtalálni a második ciklusban az összefügg® fekete élpárt O( n log(n)) id®ben. Mivel p maga a ciklus legfeljebb n iteráció után véget ér, így az algoritmus teljes m¶veletideje O(n3/2 log(n)). 2.4. 1.375-approximációs algoritmus
Az el®z® részhez hasonlóan itt is cirkuláris kromoszómákkal fogunk foglalkozni. Elias és Hartman algoritmusában az 1.5-approximációs arányt a (0,2,2)-mozgások biztosították. A következ®ekben olyan transzpozíció sorozatokat fogunk keresni, amelyek nagyobb mértékben növelik a körök számát a gráfban adott hosszúságú lépéssorozat után. Az approximációs arányt ilyen transzpozíció sorozatok egymás utáni végrehajtásával fogjuk nomítani. Mivel továbbra is egyszer¶ permutációkkal foglalkozunk, célunk alsó illetve fels® korlátokat mondani olyan permutációk transzpozíciós átmér®jére, melyek csak 2 és 3-hosszú ciklusokat tartalmaznak.
2.27. De níció.
Egy adott π permutáció 2-permutáció (3-permutáció), ha a neki megfelel® törés-
ponti gráf csak 2-hosszú (3-hosszú) köröket tartalmaz.
2.28. De níció.
Egy X halmaz összes permutációinak csoportját X
szimmetriacsoportjának hív-
juk. Ha a halmaz véges és n eleme van, akkor Sn -nel jelöljük. Mivel minden n darab génnel rendelkez® cirkuláris kromoszóma Sn egy-egy elemének felel meg, így az n elem¶ szimmetriacsoport
transzpozíciós átmér®je dT (π) értékek maximumának felel meg,
ahol a maximumot az összes n elem¶ π permutáción nézzük. Jelölés : T D(n) Hasonlóan értelmezhet® a 2-, 3-, illetve egyszer¶ permutációk transzpozíciós átmér®je, jelöljük ®ket rendre T D2(n), T D3(n),
T DS(n)-nel. 36
Sn transzpozíciós átmér®je ismeretlen, az els® melyet Eriksson csökkentett le
2n 3 -ra
3n 4 -es
alsó korlátot Bafna és Pevzner adták [3],
[13]. Sokáig az volt a sejtés, hogy az identitástól "legtávolabb"
álló permutáció a sorrend megfordításával kapott (n, n − 1, · · · , 1) inverz permutáció, a transzpozíciós + 1. Ugyanis ennyi transzpozícióból már tudjuk rendezni az inverz permutációt. átmér® pedig n−1 2 Ez volt a legjobb alsó korlát 2006-ig, ekkor az értéket Elias és Hartman csökkentette tovább n2 + 1 re [18]. Az egyszer¶ és 2-permutációk transzpozíciós átmér®je ismert, T D2(n) = n2 , T DS(n) = n2 . Az 1.375-approximációs algoritmus alapját pedig a 3-permutációk transzpozíciós átmér®jére vonatkozó fels® korlát fogja adni. A könnyebb tárgyalásmód érdekében a következ®kben bevezetünk pár formális de níciót.
Kon gurációnak
nevezzük a törésponti gráf egy vagy több kör által alkotott részgráfját. A 3-
hosszú körök kétféle kon gurációját különböztetjük meg, az els® esetben a kör irányított, a másodikban
részkon gurációja a B kon guráció összefügg®, ha
irányítatlan. Egy A kon guráció
kon gurációnak, ha A körei B köreinek
részhalmazát alkotják. Egy A
tetsz®leges két c1 és ck köréhez léteznek
olyan c2 , · · · , ck−1 körök, hogy ci és ci+1 keresztezi egymást (i ∈ {1, k −1}). Komponensnek nevezzük
nagynak nevezünk, ha legalább 8 körrel rendelkezik, ellenkez® esetben kicsinek. Egy kon gurációban nyílt gátnak nevezzük
a maximális összefügg® kon gurációt a törésponti gráfban. Egy komponenst
egy 2-hosszú vagy egy irányítatlan 3-hosszú kör fekete élpárját, ha az semmilyen másik körrel nem
teljesnek nevezünk, ha nem tartalmaz nyílt gátat. Transzpozíciók egy sorozatát (x,y)-sorozatnak (x ≥ y) nevezzük, ha adott x darab egymás utáni
keresztezi egymást. Egy kon gurációt
transzpozícióból legalább y 2-mozgás, és egy adott π 0 egyszer¶ permutációra alkalmazva π 0 továbbra is egyszer¶ marad. Azt mondjuk, hogy egy adott π permutációnak van (x,y)-sorozata, ha az alkalmazható a neki megfelel® törésponti gráf körein. Az el®z® részben látott (0,2,2)-mozgás például egy (3,2)-sorozat, így:
2.29. Tétel.
Tetsz®leges
π
permutációban, amely nem az identitás vagy létezik 2-mozgás vagy egy
(3,2)-sorozat.
2.30. Tétel.
Egy olyan legalább 3 körrel rendelkez®
π
permutációban, amely tartalmaz irányított kört
is, létezik (4,3)-sorozat.
Célunk belátni, hogy minden legalább 8 körrel rendelkez® 3-permutációnak van olyan (x,y)-sorozata, hogy x ≤ 11 és
x y
≤
11 8
= 1.375. Egy ilyen sorozatot (11,8)-sorozatnak nevezünk. A 2.30. Tétel
miatt elég csak az olyan permutációkat vizsgálnunk, amelyek csak irányítatlan köröket tartalmaznak, ugyanis minden (4,3)-sorozat egyben (11,8)-sorozat is. Az els® lépésben megmutatjuk, hogy minden nagy komponensnek van (11,8) sorozata, a második lépésben az olyan legalább 8 körrel rendelkez® permutációkat fogjuk vizsgálni, melyek csak kis komponenseket tartalmaznak, majd belátjuk, hogy az ilyen permutációknak is mindig van (11,8)-sorozata. A teljes bizonyítás [12]-ben található. A komponensek felsorolását a legkisebb épít®kövekt®l kezdjük. Vegyük tehát azt az összefügg® kon gurációt, amely két irányítatlan kört tartalmaz. Két lehetséges kon guráció létezik ilyenkor : ha a két kör illeszked®, illetve ha a két kör keresztez®. Ebb®l a két kon gurációból minden további összefüg37
g®, irányítatlan komponens felépíthet® új, irányítatlan körök hozzáadásával. Az új kör éleit ekkor a kon guráció tetsz®leges részeibe illesztjük bele, majd kötjük ®ket össze a megfelel® szürke élekkel. Azt mondjuk, hogy egy B kon guráció kiterjesztése A-nak, ha A-hoz megfelel® köröket hozzávéve
B -t kapunk. Például két illeszked® és két keresztez® kör kiterjesztése egy 3-hosszú irányítatlan körnek. Legyen C egy teljes kon guráció, A pedig egy részkon gurációja. Ekkor létezik A-nak egy olyan B kiterjesztése, ami még mindig részkon gurációja lesz C -nek. Ha A-ban van nyílt gát, akkor tudunk mondani egy olyan B kiterjesztést, ami bezárja ezt a gátat. Vegyük azt a fekete élpárt A-ban, ami a nyílt gátat alkotja. Ha ez B -vel keresztezi egymást, akkor a gát bezárul, ha nem, akkor viszont létezik egy olyan B kiterjesztés, ami legfeljebb egy nyílt gátat tartalmaz, és részkon gurációja C-nek. Ezek alapján a kiterjesztéseknek elég csak két fajtáját vizsgálnunk ahhoz, hogy tetsz®leges komponenseket fel tudjunk építeni. Ezek a kiterjesztések vagy bezárnak egy nyílt gátat, vagy egy teljes kon guráció olyan kiterjesztései, amik legfeljebb egy nyílt gátat tartalmaznak. Ezeket elégséges
kiterjesztéseknek hív-
juk. Azokat a kon gurációkat, melyek elégséges kiterjesztésekkel megvalósíthatók vagy egy irányítatlan illeszked® vagy egy irányítatlan keresztez® körpárból,
2.31. Tétel.
elégséges kon gurációknak nevezzük.
Minden 9 körrel rendelkez® irányítatlan elégséges kon gurációnak létezik (11,8)-sorozata.
De níció szerint, minden nagy komponensnek létezik olyan elégséges kiterjesztése, amely 9 kört tartalmaz. A fenti tétel tehát azt állítja, hogy ha egy permutációnak van nagy komponense, akkor (11,8)-sorozata is. A tétel egy bizonyítása az lehetne, ha felsoroljuk az összes 9 körrel rendelkez® kon gurációt, és megadunk rájuk egy rendezést. Ehhez nagyon sok esetet kellene végignéznünk, többet, mint az el®z® fejezetekben. Ezért kihasználva az elégségesség fogalmát és azt, hogy egy kon guráció rendezése részrendezése minden kiterjesztésének is, egy számítógépes programot fejlesztettek ki arra, hogy szisztematikusan feldolgozza a lehetséges eseteket. Az esetfeldolgozás algoritmusa 2.13. ábrán látható. Soroljuk fel az összes 9 körrel rendelkez® elégséges kon gurációt egy listába ;
while Amíg a lista nem üres do Töröljük az els® A kon gurációt a listából ;
for minden B elégséges kiterjesztésére A-nak do if B tartalmaz (11,8)-sorozatot then Adjuk hozzá a listához ;
else Adjuk meg B egy rendezését ;
end end end 2.13. ábra. Az esetfeldolgozás algoritmusa
38
Végrehajtva azt fogjuk eredményül kapni, hogy egyetlen 10 körrel rendelkez® kon guráció sem lett hozzáadva a listához, tehát minden elégséges 9 körrel rendelkez® kon gurációnak létezett (11,8)sorozata. Maga a program azonban még nem bizonyítás a tételre, a bizonyítás a program outputja, mely egy-egy (11,8)-sorozatot, illetve sorozatokat tartalmazó rendezés minden lehetséges kon gurációra. Ezeket kézzel is leellen®rizhetnénk, habár közel 80000 esetet kellene megvizsgálnunk. Az output helyességének ellen®rzésére egy kisebb ellen®rz® programot is írtak, mely ellen®rzi, hogy minden rendezés tényleg az identitást adja, illetve, hogy minden lehetséges 9 körrel rendelkez® elégséges kon gurációt számba vettünk. Mindkét program, a lehetséges esetek, illetve az output megtalálható egy felhasználóbarát honlapon. Az eredmény ilyen fajta megadása, illetve egy tétel bizonyítása a genom átrendezési problémákban nem ritka, a matematika történetében el®forduló leghíresebb példa pedig a négyszíntétel bizonyítása [2], mely szintén számítógépes program segítségével történt. Egyéb bizonyítások [29]-ben találhatóak. Most már csak azokat az eseket kell megvizsgálnunk, amikor a permutációban csak kis komponensek vannak. Azokat a kis komponenseket, melyeknek nincs (11,8)-sorozata
rossz kis komponenseknek
nevezzük. Számítógépes segítséggel felsorolható, hogy öt ilyen komponens van.
2.32. Tétel.
Legyen
π
egy tetsz®leges legalább 8 körrel rendelkez® permutáció, mely csak kis rossz
komponenseket tartalmaz. Ekkor
2.33. Tétel.
π -nek
van (11,8)-sorozata.
Tetsz®leges legalább 8 körrel rendelkez®
π
3-permutációnak van (11,8)-sorozata.
Ezek után a teljes algoritmus a 2.14. ábrán látható.
2.34. Tétel.
A TranszpozíciósRendezés3(π) m¶veletigénye
O(n2 ).
Ahhoz, hogy az approximációs arányt belássuk, fels® korlátot kell adnunk a 3-permutációk transzpozíciós átmér®jére. Ennek teljes bizonyítása [12]-ben található. Vegyünk egy tetsz®leges n elem¶ k j 8) , és 3-permutációt, köreinek számát jelöljük c-vel. Nyilván c = n3 . Legyen g(c) = 8c + 3(c mod 2 de niáljuk f -et a következ®képpen :
g(c) + 1 ha c mod 8 = 1 f (c) = g(c) különben 3( n mod 8) 3 2
2.35. Tétel.
T D3(n) ≤ f ( n3 ) ≤
2.36. Tétel.
A TranszpozíciósRendezés3(π) 1.375-approximációs algoritmus a permutációk transzpo-
n 24
+
j
k
zíciókkal való rendezésére. Bizonyítás.
A második lépést®l függ®en két esetet különböztetünk meg : ha van (2,2)-sorozat, illetve
ha nincs. Jelölje a 2-hosszú (3-hosszú) körök számát G(π 0 )-ben c2 (c3 ). 1.eset :
Létezik (2,2)-sorozat. A 2.7. Tétel miatt az optimális rendezésben csak 2-mozgásokat hasz-
nálunk, ez itt azt jelenti, hogy π 0 nem rendezhet® jobban annál, ha el®ször alkalmazunk két 2-mozgást, 39
TranszpozíciósRendezés3(π) ; Input : Egy tetsz®leges π = (π1 , · · · , πn ) permutáció ; Output : Egy p1 , p2 , · · · , pk transzpozíció sorozat ; Transzformáljuk át π -t egy vele ekvivalens π 0 egyszer¶ permutációba ;
if
Létezik (2,2)-sorozat
π 0 -ben
then
alkalmazzuk azt ;
else end while G(π0 ) legalább 8 körb®l áll do alkalmazzunk (11,8)-mozgást ;
end while G(π0 )-nek van 3-hosszú köre do alkalmazzunk (3,2)-mozgást ;
end Utánozzuk π 0 rendezését, és rendezzük π -t ; 2.14. ábra. TranszpozíciósRendezés3(π) algoritmusa a cirkuláris kromoszómák rendezésére (Elias, Hartman 2010) majd a megmaradt körökre még c2 + c3 darabot. Így c2 + c3 + 2 darab transzpozícióra mindenképp szükségünk lesz. A második lépés során tehát 2, a harmadik lépés során pedig nálunk, és
f (c3 +
c2 2)
c2 2
c2 2
transzpozíciót hasz-
darab 3-hosszú kört hozunk létre. A harmadik lépésben a 2.35. Tétel szerint legfeljebb
transzpozíciót használhatunk. Így az algoritmusban az alkalmazott transzpozíciók száma
összesen:
2+
c2 c2 + f (c3 + ) 2 2
Ezzel az approximációs arány :
2+ ahol x = c3 + 2.eset :
c2 2
és y =
c2 2.
c2 2
+ f (c3 + c2 + c3 + 2
c2 2)
=
2 + y + f (x) f (x) + 2 ≤ , x+y+2 x+2
A 2.2. táblázat alapján az utolsó egyenl®tlenség felülr®l becsülhet®
11 8 -dal.
Nem létezik (2,2)-sorozat. Ekkor c2 + c3 körünk marad a második lépés után, és a 2.7. Tétel
miatt c2 + c3 + 1 transzpozícióra mindenképp szükségünk lesz, hogy π 0 -t rendezzük. Egy 0-mozgásra, majd még c2 + c3 darab 2-mozgásra. Az alkalmazott transzpozíciók száma ebben az esetben összesen:
c2 c2 + f (c3 + ). 2 2 Ezzel az approximációs arány : c2 2
+ f (c3 + c22 ) y + f (x) f (x) = ≤ , c2 + c3 + 1 x+y+1 x+1 40
ahol x = c3 +
c2 2
és y =
c2 2.
A táblázat alapján az utolsó egyenl®tlenség felülr®l becsülhet®
r
0
1
2
3
4
5
6
7
f (r)
0
2
3
4
6
7
9
10
f (x)+2 x+2 f (x) x+1
11l+2 8l+2 11l 8l+1
11l+4 8l+3 11l+2 8l+2
11l+5 8l+4 11l+3 8l+3
11l+6 8l+5 11l+4 8l+4
11l+8 8l+6 11l+6 8l+5
11l+9 8l+7 11l+7 8l+6
11l+11 8l+8 11l+9 8l+7
11l+12 8l+9 11l+10 8l+8
11 8 -dal.
2.2. táblázat. Függvénytáblázat az 1.375-ös approximációs arány bizonyításához, ahol x = 8l + r, f(x) = 11l + f(r)
41
3. fejezet
Pre x transzpozíciók A pre x transzpozíciók fogalmát, illetve a pre x transzpozíciókkal való rendezés alapproblémáját Dias és Meidanis de niálta el®ször 2004-ben [11]. Magát a pre x transzpozíciós távolságot nem sikerült meghatározniuk, de alsó és fels® korlátot adtak a távolságra. Az alsó korlát n2 , a fels® pedig n − 1, ahol
n a genomban szerepl® gének száma. A probléma megoldására egy 2-es és egy 3-as approximációs algoritmust dolgoztak ki, illetve megmutatták, hogy az inverz permutáció [n, n − 1, n − 2, · · · 1] rendezhet® 3n 4
lépésb®l. Sejtés, hogy ez a permutáció áll a legtávolabb az identitástól, és ezzel együtt ez a pre x
transzpozíciós távolság. A meghatározott korlátokat kés®bb Chitturi és Sudborough javította tovább 2008-ban [6]. Az alsó korlátot 2n -ra emelték, a fels® korlátot pedig n−log8 (n)-re csökkentették. Az alsó 3n3 korlátot 2012-ben Labarre 4 -re emelte [22], ez a máig ismert legjobb eredmény, ami tovább er®síti a pre x transzpozíciós távolságra vonatkozó sejtést. A transzpozíciós távolság és a probléma nehézsége máig nyitott. A harmadik fejezetet a következ®képpen fogjuk felépíteni. Az els® részben bevezetjük a pre x transzpozíció és a pre x transzpozíciós távolság fogalmát és de niáljuk a pre x transzpozíciókkal való rendezés alapproblémáját. Mivel a transzformáció, melyet ismertetni fogunk pre x, ezért ebben a fejezetben csak lineáris kromoszómákkal rendelkez® genomokkal fogunk foglalkozni. A második részben ismertetjük az alapproblémára vonatkozó 3-approximációs és 2-approximációs algoritmust, a harmadik részben a Dias és Meidanis által meghatározott alsó, illetve fels® korlátokat, a negyedik részben pedig az inverz permutáció rendezésére vonatkozó algoritmust, illetve a pre x transzpozíciós távolságra vonatkozó sejtést.
Szerz®k
Alsó korlát
Fels® korlát
Év
Dias, Meidanis
n/2
n−1
2002
Chitturi, Sudíborough
2n/3
n − log8 (n)
2008
Labarre
3n/4
-
2012
3.1. táblázat. Eddig elért eredmények a pre x transzpozíciókkal való rendezés alapproblémájára
42
3.1. Alapfogalmak
Legyen adott a σ = [7,5,8,3,2,4,1] permutáció.
3.1. De níció. Pre x transzpozíciónak
nevezzük azt a transzformációt, amely egy adott π =
[π1 , π2 , . . . , πn ] permutációban megcserél két olyan szomszédos blokkot, melyek közül az egyik mindig pre x, azaz a permutáció els® elemét®l kezd®d® blokk. Egy p(1, j, k) paraméterekkel megadott pre x transzpozíció megcseréli a [π1 , . . . , πj−1 ] és a [πj , . . . , πk−1 ] blokkokat (1 ≤ j < k ≤ n), azaz a
[π1 , . . . , πj−1 ] blokknak megfelel® génszekvenciát egy új helyre, a πk−1 elemnek megfelel® gén mögé illeszti.
3.1. ábra. A π permutációra alkalmazott p(1, j, k) pre x transzpozíció
Legyen p(1, j, k) = (1,4,7). Ez a transzformáció megcseréli σ -ban a [7,5,8] és a [3,2] blokkokat, azaz [7,5,8]-at [2] mögé illeszti. A transzformáció utáni kromoszómának megfelel® permutáció pσ =
[3,2,7,5,8,4,1]. A feladat az el®z® fejezetekben kit¶zött problémákhoz hasonló. Célunk meghatározni azt a minimális számot és a hozzá tartozó pre x transzpozíció sorozatot, mellyel két adott genom közül az egyik a másikba transzformálható. Mivel a gének címkézése az adott genomban itt is tetsz®leges, ezért a célgenomnak megfelel® permutációt választhatjuk az identitásnak.
3.2. De níció.
Egy adott π permutáció
pre x transzpozíciós távolsága
az a minimális szám,
ahány pre x transzpozíció szükséges ahhoz, hogy az adott permutációt az identitásba vigyük. Jelölés:
dP T (π). Legyen pl. π = [4,2,3,1], ekkor dP T (π) = 2. Valóban, nem létezik olyan pre x transzpozíció, amellyel egyb®l az identitást kapnánk. Cseréljük meg el®ször a [4] és a [2,3] blokkokat, majd az így kapott
π 0 = [2,3,4,1]-ben a [2,3,4] és az [1] blokkokat. Ekkor π 00 = [1,2,3,4] = Id. 3.2. Approximációs algoritmusok 3.2.1. 3-approximációs algoritmus
A 3-approximációs algoritmus ismertetéséhez két fontos tulajdonságot kell észrevennünk. Az els®, hogy minden pre x transzpozíció egyben transzpozíció is, ezért a pre x transzpozíciós távolság legalább annyi lesz, mint a transzpozíciós távolság.
3.3. Tétel.
Tetsz®leges
π
permutáció esetén
dP T (π) ≥ dT (π). 43
A második, hogy minden transzpozíció helyettesíthet® két pre x transzpozícióval.
3.4. Tétel. p2 (1, t, u)
Tetsz®leges
úgy, hogy
t(x, y, z)
transzpozícióhoz mindig létezik két pre x transzpozíció
p1 (1, r, s)
és
p2 p1 π = tπ .
A fenti két tulajdonság miatt igaz a következ® tétel:
3.5. Tétel.
Minden olyan
k -approximációs
algoritmus, amely megoldja a transzpozíciókkal való ren-
dezés alapproblémáját, áttranszformálható egy
2k -approximációs
algoritmussá, ami megoldja a pre x
transzpozíciókkal való rendezés alapproblémáját.
Ezután a Christie [8] és a Bafna és Pevzner [3] által adott 1.5-approximációs algoritmusokat könnyedén áttranszformálhatjuk úgy, hogy a pre x transzpozíciókkal való rendezés alapproblémájára adjanak egy-egy 3-approximációs algoritmust. 3.2.2. 2-approximációs algoritmus
Ebben a részben módosítjuk a töréspontok fogalmát annyival, hogy az els® helyen álló elemben mindig töréspontot de niálunk. Az el®z® de nícióhoz hasonlóan, minden π permutációra bp (π) ≥ 1, csak az identitásnak van pontosan egy töréspontja, illetve egyetlen permutációnak sincs pontosan két töréspontja. Legyen adott π permutáció és τ pre x transzpozíció. Jelölje ∆bp (π, τ ) = bp (τ π) − bp (π) a töréspontok számának megváltozását π -ben τ alkalmazása után. A következ®ekben megvizsgáljuk, hogyan változik a töréspontok száma az adott permutációban egy-egy pre x transzpozíció alkalmazása után, illetve mennyivel tudjuk biztosan csökkenteni a töréspontok számát.
3.6. Tétel. Bizonyítás.
Legyen adott
π
permutáció és
τ
pre x transzpozíció. Ekkor
−2 ≤ ∆bp (π, τ ) ≤ 2.
Tudjuk, hogy egy transzpozíció három elem szomszédságát változtatja meg. A legrosszabb
eset az, ha mind a három elem rossz helyre kerül, így legfeljebb három töréspontot hozhatunk létre. A pre x transzpozíció az els® elem szomszédságát mindig megváltoztatja, de ebben az elemben a szomszédságától függetlenül mindig töréspontot de niáltunk, így legfeljebb két töréspontot hozhatunk létre. Visszafelé, ha egy pre x transzpozíció legalább két töréspontot szüntetne meg, akkor ezt visszafelé alkalmazva legalább két töréspontot hoznánk létre, de ez ellentmond az el®z® állításunknak. Így minden
π permutációra és τ pre x transzpozícióra −2 ≤ ∆bp (π, τ ) ≤ 2.
3.7. Tétel. Legyen adott egy π n elem¶ permutáció, mely nem az identitás. Ekkor mindig tudunk találni olyan
τ
pre x transzpozíciót, amely legalább eggyel csökkenti a töréspontok számát, azaz
Bizonyítás.
∆bp (π, τ ) ≤ −1.
Vegyük az els® töréspontot π -ben a második elemt®l kezdve, legyen ez πk -ban. Ha k < n,
−1 akkor πk+1 -ben is töréspont van, és πk+1 πk után helyezkedik el, azaz πk−1 < πk+1 . Illesszük ekkor a −1 [π1 , · · · , πk ] blokkot πk+1 elé, azaz alkalmazzuk τ = τ (1, πk−1 + 1, πk+1 ) pre x transzpozíciót, ekkor
a πk+1 -ben lév® töréspont megsz¶nik. Ha k = n, akkor illesszük a [π1 , · · · πk1 ] blokkot a permutáció 44
végére, azaz alkalmazzuk τ = τ (1, πk−1 + 1, n + 1) pre x transzpozíciót, ekkor a πk = n jó helyre kerül, így a permutáció végén lév® töréspont megsz¶nik. A következ®kben alsó, illetve fels® korlátokat fogunk meghatározni a pre x transzpozíciós távolságra a töréspontok számának segítségével, illetve megmutatjuk, hogy ha csak bizonyos tulajdonsággal rendelkez® pre x transzpozíciókat alkalmazunk egymás után, akkor az 2-approximációs algoritmus lesz. l m 3.8. Tétel. Minden π permutációra dT P (π) ≥ bp (π)−1 . 2 Bizonyítás.
Az, hogy az adott π permutációt az identitásba rendezzük ekvivalens azzal, hogy a törés-
pontok számát egyre csökkentsük. Mivel a 3.6. Tétel miatt minden lépésben legfeljebb kett®vel tudunk l m b (π)−1 csökkenteni, így legalább p 2 darab pre x transzpozícióra szükségünk lesz.
3.9. Tétel. Bizonyítás.
Legyen
π
olyan permutáció, amelynek 3 töréspontja van. Ekkor
dT P (π) = 1.
A 3.7. Tétel szerint mindig tudjuk csökkenteni a töréspontok számát legalább eggyel.
Ebben az esetben, ha pontosan eggyel csökkentenénk, akkor π -ben két darab töréspont maradna, ez egy korábbi észrevétel miatt nem fordulhat el®. A 3.6. Tétel miatt legfeljebb kett®vel csökkenthetünk, és ha kett®vel csökkentünk, akkor π -ben egy darab töréspont marad, tehát π az identitás.
3.10. Tétel. Bizonyítás.
Legyen
π
adott, az identitástól különböz® permutáció. Ekkor
dT P (π) ≤ bp (π) − 2.
Ha π nem az identitás, akkor a 3.7. Tétel szerint tudjuk úgy rendezni π -t, hogy min-
dig eggyel csökkentjük a töréspontok számát, addig amíg három töréspontunk nem marad, ez eddig
bp (π) − 3 transzpozíció. Ezután a 3.9. Tétel miatt egy lépésben tudunk kett®vel csökkenteni, ekkor egy töréspontunk maradt, tehát π az identitás. Így legfeljebb bp (π) − 3 + 1 = bp (π) − 2 darab pre x transzpozícióra lesz szükségünk.
3.11. Tétel.
Legyen
π
adott, az identitástól különböz® permutáció. Ekkor
l
bp (π)−1 2
m
≤ dT P (π) ≤
bp (π) − 2.
3.12. Tétel.
Minden olyan algoritmus, ami a 3.9. Tételnek és a 3.7. Tételnek megfelel® pre x transz-
pozíciókat alkalmaz egymást után, egy 2-approximáxiós algoritmus lesz a pre x transzpozíciókkal való rendezés alapproblémájára.
A genomátrendezési feladatoknál fontos probléma még, hogy tudunk-e úgy rendezni egy permutációt, hogy közben ne növeljük a töréspontok számát. Christie bizonyította be [8], hogy ez igaz a transzpozíciókkal való rendezésre, a bizonyítás pedig hasonlóan átvihet® pre x transzpozíciókra is, a teljes bizonyítás [11]-ben található.
3.13. Tétel. dP T (π) = k . és
Legyen
π
egy tetsz®leges
Ekkor létezik olyan
k
n
elem¶ permutáció, melynek pre x transzpozíciós távolsága,
hosszú pre x transzpozíció sorozat,
∆bp (τi−1 , · · · τ1 π, τi ) ≥ 0) (1 ≤ i ≤ k).
45
τ1 , · · · , τk ,
hogy
τk · · · τ1 π = Id,
3.3. Alsó és fels® korlátok
A könnyebb tárgyalásmód érdekében bevezetünk egy új de níciót. Ennek és két korábbi eredménynek a segítségével adunk alsó, illetve fels® korlátot.
3.14. De níció. Transzformációs átmér®nek nevezzük azt a legnagyobb transzformációs távolságot, mely két n elem¶ permutáció között található. Transzformáció alatt az összes evolúciós történést - beleértve a blokk-cseréket, pre x blokk-cseréket, transzpozíciókat, illetve pre x transzpozíciókat -, transzformációs távolság alatt pedig az ezek által meghatározott evolúciós távolságot - blokk-csere, pre x blokk-csere, transzpozíciós, pre x transzpozíciós távolságot - értjük. Jelöljük Dp (n)-nel a pre x transzpozíciós, D(n)-el pedig a transzpozíciós átmér®t. Az el®z® fejezetben a Bafna és Pevzner által a transzpozíciós távolságra meghatározott alsó és fels® korlát [3] a transzpozíciós átmér®re a következ®képp fogalmazható át:
3.15. Tétel.
Minden
n
n elem¶ permutáció transzpozíciós átmér®jére : 2
3.16. Tétel.
Minden
n
n elem¶ permutáció pre x transzpozíciós átmér®jére : 2
Bizonyítás.
≤ D(n) ≤
3n 4 .
≤ Dp (n) ≤ n − 1.
A 3.3. Tétel miatt minden π n elem¶ permutációra dP T (π) ≥ dT (π), ezért az alsó korlát az
el®z® tétel miatt Dp (n) ≤ D(n) ≤ n2 . A fels® korlát bizonyításához felhasználjuk az Aigner és West [1] által elért eredményt, miszerint ha egy permutációt csak τ = τ (1,2, x) alakú pre x transzpozíciókkal rendezünk - tehát ha csak az els® elemet mozgatjuk - akkor legfeljebb n − 1 transzpozícióra van szükségünk. 3.4. Inverz permutációk rendezése
Ahhoz, hogy az inverz permutációk rendezésére vonatkozó algoritmust és a pre x transzpozíciós átmér®re vonatkozó sejtést ismertetni tudjuk, néhány permutációcsaládot formálisabb módon kell bevezetnünk. Ebben a részben a permutációkat, mint szekvenciákat kezeljük majd, és egy új, konkatenációs operátort vezetünk be.
3.17. De níció.
Legyen az a b szekvencia az a szekvencia b szekvenciával vett konkatenációja.
De niáljuk az általánosított konkatenációs operátort a következ®képp: bj=a f (j) szekvencia legyen az
f (j) szekvenciák konkatenációja, ahol j végigfut rendre a-tól b-ig a szekvenciákon. Vegyük szemléltetésként a következ® két példát :
a = [1,2,3], b = [4,5,6], a b = [1,2,3,4,5,6]
4j=0 [1 + 3j, 2 + 3j] = [1,2,4,5,7,8,10,11,13,14]
46
3.18. De níció.
n−1 Legyen Rn permutációcsalád a következ® : j=0 [n − j] = [n, n − 1, n − 2, · · · , 2,1].
Ekkor az n elem¶ Rn permutációt inverz permutációnak nevezzük. Az inverz permutációk transzpozíciós átmér®jére vonatkozó következ® eredményt egymástól függetlenül Christie [8] és Meidanis, Walter és Dias is [25] belátta :
3.19. Tétel.
n≥3
esetén
d(Rn ) =
n 2
+ 1.
A pre x transzpozíciós átmér®re a 3.11. Tétel miatt a következ® teljesül :
3.20. Tétel.
n 2
≤ dp (Rn ) ≤ n − 1.
A következ®kben egy olyan algoritmust fogunk megadni, ami n −
n 4
pre x transzpozíciót felhasz-
nálva rendezi az n elem¶ Rn inverz permutációt. Az algoritmus helyességét azzal fogjuk igazolni, hogy különböz® fázisokra bontjuk az algoritmust, és megmutatjuk, hogy az els® fázisbeli permutációból hogyan tudjuk megkapni a második fázisbeli permutációt, a második fázisbelib®l a harmadikbelit, és így tovább. Végül, a legutolsó fázisból az identitásba transzformálunk. A teljes algoritmus a 3.2. ábrán található, példaként végigkísérjük majd, hogyan transzformáljuk át R14 = [14,13,12,11,10,9,8,7,6,5,4,3,2,1] permutációt az identitásba. Öt fázist fogunk megkülönböztetni. A
0. fázisban
elérjük azt, hogy egy olyan permutációt kelljen rendeznünk, amelynek az elemszáma
négy többszöröse. Megnézzük a néggyel vett osztási maradékot, majd a legnagyobb fölösleges elemeket a végs® helyükre, a permutáció végére tesszük. Ezekkel már nem kell foglalkoznunk, így elhagyhatjuk ®ket, és a továbbiakban feltesszük, hogy a rendezend® inverz permutáció elemszáma négy többszöröse. A 0. fázisban R14 -re a következ® lépéseket hajtjuk végre:
[14,13,12,11,10,9,8,7,6,5,4,3,2,1] → [12,11,10,9,8,7,6,5,4,3,2,1,13,14] Ezzel visszavezettük a problémát arra az esetre, amikor R12 -t kell rendeznünk. A következ®kben három permutációcsaládot fogunk de niálni, F1 , F2 , F3 , melyek rendre az els®, második, illetve a harmadik fázis eredményei lesznek. Annak a bizonyítása, hogy tényleg ezek az eredményül kapott permutációk, [15]-ben található.
3.21. De níció.
Az F1 (n) permutációt a következ® formula adja meg :
F1 (n) = [2]
n/4−2
n/4−2
K
K
[n − 4j, n − 1 − 4j] [4,3]
j=0
3.22. De níció.
[6 + 4j, 5 + 4j] [1].
j=0
Az F2 (n) permutációt a következ® formula adja meg : n/4−2
F2 (n) = [3]
K
[6 + 4j, 7 + 4j, 4 + 4j, 5 + 4j] [1,2, n].
j=0
47
3.23. De níció. F3 (n) =
Az F3 (n) permutációt a következ® formula adja meg :
dn/8e−2 3 K K
[10−n
j=0
3.24. Tétel.
mod 8+8j+k] [1,2,3,4,5]
j=0
k=0 Az els® fázis az
bn/8c−2 3 K K
Rn (n ≥ 4)
permutációt az
[6+n
mod 8+8j+k] [n−2, n−1, n]
k=0
F1 (n)
permutációba transzformálja.
Az els® fázisban az R12 -re a következ® lépéseket hajtjuk végre : el®ször alkalmazzuk a ciklusban szerepl® két, τ1 , τ2 pre x transzpozíciót, τ1 = τ1 (1,5,12), τ2 = τ2 (1,5,10). Ekkor
τ1 R12 = [8,7,6,5,4,3,2,12,11,10,9,1] τ2 τ1 R12 = [4,3,2,12,11,8,7,6,5,10,9,1] Másodszor pedig a cikluson kívül lév® τ3 = τ3 (1,3,8) pre x transzpozíciót. Ekkor
τ3 τ2 τ1 R12 = [2,12,11,8,7,4,3,6,5,10,9,1]. Ez pedig éppen F1 (12).
3.25. Tétel.
Az második fázis az
F1 (n) (n ≥ 4)
permutációt az
F2 (n)
permutációba transzformálja.
A második fázisban F1 (12)-vel dolgozunk tovább, és alkalmazzuk a ciklusban szerepl® három τ1 ,
τ2 , τ3 pre x transzpozíciót, τ1 = τ1 (1,3,13), τ2 = τ2 (1,3,9), τ3 = τ3 (1,3,5). τ1 F1 (12) = [11,8,7,4,3,6,5,10,9,1,2,12] τ2 τ1 F1 (12) = [7,4,3,6,5,10,11,8,9,1,2,12] τ3 τ2 τ1 F1 (12) = [3,6,7,4,5,10,11,8,9,1,2,12] Ez pedig éppen F2 (12).
3.26. Tétel.
Az harmadik fázis az
F2 (n) (n ≥ 8)
permutációt az
F3 (n)
permutációba transzformálja.
A harmadik fázisban F2 (12)-b®l indulunk ki, és alkalmazzuk a ciklusban szerepl® τ1 pre x transzpozíciót, τ1 = τ1 (1,8,12).
τ1 F2 (12) = [8,9,1,2,3,6,7,4,5,10,11,12] Mivel 12 mod 8 6= 0, ezért az else ágban szerepl® τ2 = τ2 (1,6,8) pre x transzpozíciót fogjuk alkalmazni:
τ2 τ1 F2 (12) = [6,7,8,9,1,2,3,4,5,10,11,12] Ez pedig éppen F2 (13).
3.27. Tétel.
A negyedik fázis az
F3 (n) (n ≥ 8)
permutációt az identitásba transzformálja.
48
A negyedik fázisban az F2 (13)-ra alkalmazott utolsó τ1 = τ1 (1,5,10) pre x transzpozícióval az identitást fogjuk kapni.
τ1 F3 (12) = [1,2,3,4,5,6,7,8,9,10,11,12] = Id. Az alkalmazott pre x transzpozíciók számára a következ® állítást teljesül:
3.28. Tétel.
Az InverzPermutációRendezés(π) az
Rn
inverz permutációt
n−
n 4
pre x transzpozíció
felhasználásával rendezi. Bizonyítás.
Számoljuk össze a felhasznált pre x transzpozíciókat. Legyen n0 = n − (n mod 4), mivel
n0 4 többszöröse, ezért
n0 8
=
n0 − n0
mod 8 8
,
n0 8
=
n0 + n0
mod 8 8
.
Így az összesen felhasznált pre x transzpozíciók száma: 0 0 n0 n0 n n n mod 4 + +( +1 )+( − 1) = 4 4 8 8
3n0 +n 4
3.29. Sejtés.
A
Dp (n)
mod 4 =
jnk 4n − (n − n mod 4 =n− . 4 4
pre x transzpozíciós átmér®
49
Dp (n) = dp (Rn ) = n −
n 4
InverzPermutációRendezés(π) ; Input : π = Rn permutáció, ahol n ≥ 4 ; Output : Egy τ1 , τ2 , · · · , τk pre x transzpozíció sorozat, ahol k = n − n4 ; 0. fázis :
for
n 4 többszörösére való lecsökkentése ;
i = 1 to
n
mod 4 − 1
do
π = τ (1,2, n + 1 − i)π ;
end n = n − (n mod 4) ; 1. fázis :
for
- itt π = Rn , ahol n a 4 többszöröse ;
i = 1 to
n/2 − 1
do
π = τ (1,5, n − 2i)π ;
end π = τ (1,3, n/2 + 2)π ; 2. fázis :
for
- itt π = F1 (n) ;
i = 1 to
n/4 − 1
do
π = τ (1,3, n + 1 − 4i)π ;
end 3. fázis :
for
- itt π = F2 (n) ;
i = 1 to
bn/8c − 1
do
π = τ (1, n − 4 − 4i, n − 4i)π ;
end if n
mod 8 = 0
then
π = τ (1,3, n/2 + 2)π ;
else π = τ (1, n/2, n/2 + 2)π ;
end 4. fázis :
for
- itt π = F3 (n) ;
i = 1 to
dn/8e − 2
do
π = τ (1,5, 4 bn/8c + 6 + 4i)π ;
end Itt már π = Id ; 3.2. ábra. InverzPermutációRendezés(π) algoritmusa Rn rendezésére (Dias, Meidanis 2002)
50
4. fejezet
Pre x blokk-cserék Ebben a fejezetben a pre x transzpozíciók általánosításával, a pre x blokk-cserékkel fogunk foglalkozni. Az els® részben bevezetjük a pre x blokk-csere és a pre x blokk-csere távolság fogalmát és de niáljuk a pre x blokk-cserékkel való rendezés alapproblémáját. Mivel a transzformáció, melyet ismertetni fogunk pre x, ezért az el®z® fejezethez hasonlóan itt is csak lineáris kromoszómákkal rendelkez® genomokkal fogunk foglalkozni. A második részben ismertetjük az alapproblémára vonatkozó 2-approximációs algoritmust, a harmadik részben pedig a töréspontok számának segítségével adunk alsó, illetve fels® korlátot. 4.1. Alapfogalmak
Legyen adott a σ = [3,6,5,1,4,2] permutáció.
4.1. De níció. Pre x blokk-cserének nevezzük azt a transzformációt, amely egy adott π
permu-
tációban megcserél két olyan nem feltétlenül szomszédos blokkot, melyek közül az egyik mindig pre x. Egy p(1, j, k, l) paraméterekkel megadott pre x blokk-csere megcseréli a [π1 , . . . , πj−1 ] és a [πk , . . . , πl−1 ] blokkokat (1 ≤ k ≤ l ≤ n + 1). Speciális esetben, j = k -ra visszakapjuk a pre x transzpozíció de nícióját.
4.1. ábra. A π permutációra alkalmazott p(1, j, k, l) pre x blokk-csere
Legyen p(1, j, k, l) = (1,3,4,6). Ez a transzformáció megcseréli σ -ban a [3,6] és az [1,4] blokkokat. A transzformáció utáni kromoszómának megfelel® permutáció pσ = [1,4,5,3,6,2]. A feladat az el®z® fejezetekben kit¶zött problémákhoz hasonló. Célunk meghatározni azt a minimális számot és a hozzá tartozó pre x blokk-csere sorozatot, mellyel két adott genom közül az egyik 51
a másikba transzformálható. Mivel a gének címkézése az adott genomban itt is tetsz®leges, ezért a célgenomnak megfelel® permutációt választhatjuk az identitásnak.
4.2. De níció.
Egy adott π permutáció
pre x blokk-csere távolsága az a minimális szám, ahány
pre x blokk-csere szükséges ahhoz, hogy az adott permutációt az identitásba vigyük. Jelölés : dP BI (π). Legyen pl. π = [4,6,1,2,3,5], ekkor dP BI (π) = 2. Valóban, nem létezik olyan pre x blokk-csere, amellyel egyb®l az identitást kapnánk. Cseréljük meg el®ször a [4] és a [6,1,2,3] blokkokat, majd az így kapott π 0 = [6,1,2,3,4,5]-ben a [6] és az [1,2,3,4,5] blokkokat. Ekkor π 00 = [1,2,3,4,5,6] = Id. 4.2. 2-approximációs algoritmus
A 2-approximációs algoritmus ismertetéséhez, az el®z® fejezethez hasonlóan itt is két fontos tulajdonságot kell észrevennünk. Az els®, hogy minden pre x blokk-csere egyben blokk-csere is, ezért a pre x blokk-csere távolság legalább annyi lesz, mint a blokk-csere távolság.
4.3. Tétel.
Tetsz®leges
π
permutáció esetén
dP BI (π) ≥ dBI (π).
A második, hogy minden blokk-csere helyettesíthet® két pre x blokk-cserével.
4.4. Tétel.
Tetsz®leges
p2 (1, t, u, n)
úgy, hogy
Bizonyítás.
Vegyük példának a π = [π1 , · · · , πi , · · · , πj , · · · , πk , · · · , πl , · · · πn ] = [B, C, D, E, F ] per-
p(i, j, k, l)
blokk-cseréhez mindig létezik két pre x blokk-csere
p1 (1, r, s, m)
és
p2 p1 π = pπ .
mutációt, ahol B = [π1 , · · · , πi−1 ], C = [πi , · · · , πj−1 ], D = [πj , · · · , πk−1 ], E = [πk , · · · , πl−1 ], F =
[πl , · · · , πn ]. Ekkor a p(i, j, k, l) blokk-cserét alkalmazva, amely a [πi , · · · , πj−1 ] = C és a [πk , · · · , πl−1 ] = E blokkokat cseréli meg, a pπ = [π1 , · · · , πi−1 , πk , · · · , πl−1 , πj , · · · , πk−1 , πi , · · · , πj−1 , πl , · · · , πn ] = [B, E, D, C, F ] permutációt kapjuk. Helyettesítsük a p(i, j, k, l) blokk-cserét a következ® két pre x blokk-cserével : cseréljük meg el®ször a B = [π1 , · · · , πi−1 ] és D = [πj , · · · , πk−1 ] blokkokat, a p1 (1, i, j, k) pre x blokk-cserével, ekkor
p1 π = [πj , · · · , πk−1 , πi , · · · , πj−1 , π1 , · · · , πi−1 , πk , · · · , πl · · · , πn ] = [D, C, B, E, F ] Cseréljük meg utána a [D, C] = [πj , · · · , πk−1 , πi , · · · , πj−1 ] és az [B, E] = [π1 , · · · , πi−1 , πk , · · · , πl ] blokkokat a p2 (1, k − i + 2, i + l − k) transzpozícióval. Ekkor
p2 p1 π = [π1 , · · · , πi−1 , πk , · · · , πl−1 , πj , · · · , πk−1 , πi , · · · , πj−1 , πl , · · · , πn ] = [B, E, D, C, F ] = pπ.
A fenti két tulajdonság miatt igaz a következ® tétel:
4.5. Tétel.
Minden olyan
k -approximációs
alapproblémáját, áttranszformálható egy
algoritmus, amely megoldja a blokk cserékkel való rendezés
2k -approximációs
cserékkel való rendezés alapproblémáját.
52
algoritmussá, ami megoldja a pre x blokk-
Mivel a blokk-csere távolságot meg tudjuk határozni, ezért minden olyan algoritmus, ami ezt megadja, 2-approximációs lesz a pre x blokk-cserékkel való rendezés alapproblémájára. Ezután a Christie [8] és a Lin, Lu, Chang, Tang [3] által adott algoritmusokat könnyedén áttranszformálhatjuk úgy, hogy a pre x blokk-cserékkel való rendezés alapproblémájára adjanak egy-egy 2-approximációs algoritmust. 4.3. Alsó és fels® korlátok
Ebben a részben a töréspontok segítségével fogunk mutatni alsó, illetve fels® korlátot a pre x blokk-csere távolságra. Az el®z® fejezethez hasonlóan módosítjuk a töréspontok fogalmát annyival, hogy az els® helyen álló elemben mindig töréspontot de niálunk. Az el®z® de nícióhoz hasonlóan, minden π permutációra bp (π) ≥ 1, csak az identitásnak van pontosan egy töréspontja, illetve egyetlen permutációnak sincs pontosan két töréspontja. Legyen adott π permutáció és τ pre x blokk-csere. Jelölje ∆bp (π, τ ) = bp (τ π) − bp (π) a töréspontok számának megváltozását π -ben τ alkalmazása után. A következ®ekben megvizsgáljuk, hogyan változik a töréspontok száma az adott permutációban egy-egy pre x blokk-csere alkalmazása után, illetve mennyivel tudjuk biztosan csökkenteni a töréspontok számát.
4.6. Tétel. Bizonyítás.
Legyen adott
π
permutáció és
τ
pre x blokk-csere. Ekkor
−3 ≤ ∆bp (π, τ ) ≤ 3.
Egy pre x blokk-csere az els® elem szomszédságát mindig megváltoztatja, de ebben az
elemben a szomszédságától függetlenül mindig töréspontot de niáltunk, így legfeljebb három töréspontot hozhatunk létre. Visszafelé, ha egy pre x blokk-csere legalább három töréspontot szüntetne meg, akkor ezt visszafelé alkalmazva legalább három töréspontot hoznánk létre, de ez ellentmond az el®z® állításunknak. Így minden π permutációra és τ pre x blokk-cserére −3 ≤ ∆bp (π, τ ) ≤ 3. Mivel minden pre x transzpozíció egyben pre x blokk-csere is, ezért igaz a következ® két állítás:
4.7. Tétel. Legyen adott egy π n elem¶ permutáció, mely nem az identitás. Ekkor mindig tudunk találni olyan
τ
pre x blokk-cserét, amely legalább eggyel csökkenti a töréspontok számát, azaz
4.8. Tétel.
Legyen
π
olyan permutáció, amelynek 3 töréspontja van. Ekkor
∆bp (π, τ ) ≤ −1.
dP BI (π) = 1.
A következ®kben alsó, illetve fels® korlátokat fogunk mondani a töréspontok számának segítségével. m l . 4.9. Tétel. Minden π permutációra dP BI (π) ≥ bp (π)−1 3 Bizonyítás.
Az, hogy az adott π permutációt az identitásba rendezzük ekvivalens azzal, hogy a tö-
réspontok számát egyre csökkentsük. Mivel a 4.6. Tétel miatt minden lépésben legfeljebb hárommal l m b (π)−1 tudunk csökkenteni, így legalább p 3 darab pre x blokk-cserére szükségünk lesz.
4.10. Tétel.
Legyen
π
adott, az identitástól különböz® permutáció. Ekkor
53
dP BI (π) ≤ bp (π) − 2.
Bizonyítás.
Ha π nem az identitás, akkor a 4.7. Tétel szerint tudjuk úgy rendezni π -t, hogy mindig
eggyel csökkentjük a töréspontok számát, addig amíg három töréspontunk nem marad, ez eddig bp (π)−3 pre x blokk-csere. Ezután a 4.8. Tétel miatt egy lépésben tudunk kett®vel csökkenteni, ekkor egy töréspontunk maradt, tehát π az identitás. Így legfeljebb bp (π) − 3 + 1 = bp (π) − 2 darab pre x blokk-cserére lesz szükségünk.
4.11. Tétel.
Legyen
π
adott, az identitástól különböz® permutáció. Ekkor
bp (π) − 2.
54
l
bp (π)−1 3
m
≤ dP BI (π) ≤
Ábrák jegyzéke 1.1. A π permutációra alkalmazott b(i, j, k, h) blokk-csere . . . . . . . . . . . . . . . . . . .
5
1.2. Négy töréspont megszünése egy adott π permutációban . . . . . . . . . . . . . . . . . .
6
1.3. A [1, 2, 5, 3, 4, 6] permutációnak megfelel® törésponti gráf . . . . . . . . . . . . . . . . .
7
1.4. Blokk-cserékkel való rendezés algoritmusa a lineáris kromoszómákra (Christie 1996) . .
8
1.5. A π = [9,6,1,4,7,5,2,3,8] permutációnak megfelel® T permutációs fa [14] . . . . . . . . .
8
1.6. Az
Összeolvaszt (t1 , t2 )
1. esete, H(t1 ) = k , H(t2 ) = k vagy k − 1 [14] . . . . . . . . . .
9
1.7. Az
Összeolvaszt (t1 , t2 )
2. esete, H(t1 ) = k + 2, H(t2 ) = k és H(L(t1 )) > H(R(t1 )) [14]
10
1.8. Az
Összeolvaszt (t1 , t2 )
2. esete, H(t1 ) = k + 2, H(t2 ) = k és H(L(t1 )) = H(R(t1 )) [14]
10
1.9. Az
Összeolvaszt (t1 , t2 )
2. esete, H(t1 ) = k + 2, H(t2 ) = k és H(L(t1 )) < H(R(t1 )) [14]
10
1.10. Ul és Ur ábrázolása a π = [9,6,1,4,7,5,2,3,8] permutációnak megfelel® T permutációs fán
11
1.11. Blokk-cserékkel való rendezés algoritmusa a cirkuláris kromoszómákra (Lin, Lu, Chang, Tang 2005) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.12. Blokk-cserékkel való rendezés gyorsított algoritmusa a cirkuláris kromoszómákra (Huang, Huang, Tang, Lu 2010) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
1.13. Módosított algoritmus lineáris kromoszómákra (Lin, Lu, Chang, Tang 2005) . . . . . .
22
1.14. Blokk-cserékkel való rendezés gyorsított algoritmusa a lineáris kromoszómákra . . . . .
23
2.1. A π permutációra alkalmazott p(i, j, k) transzpozíció . . . . . . . . . . . . . . . . . . .
26
2.2. TRendezés(π) algoritmusa a lineáris kromoszómák rendezésére (Bafna, Pevzner 1998) .
28
2.3. TranszpozíciósRendezés1(π) algoritmusa a lineáris kromoszómák rendezésére (Bafna, Pevzner 1998) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
2.4. Egy (g, b)-vágás [18] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
2.5. (A) Irányítatlan kör (B) Irányított kör [18] . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.6. (A) Keresztez® 3-hosszú körök (B) Nem keresztez® 3-hosszú körök (C) Illeszked® 3hosszú körök [18] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.7. A keresett (0,2,2)-mozgás, ami a két irányítatlan, illeszked® 3-hosszú kört hat 1-hosszú körré transzformálja. Minden lépésben az alkalmazott transzpozíciók a csillagozott fekete éleken hatnak. [18] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
32
2.8. A 2.22. Tétel három lehetséges esete. [18] . . . . . . . . . . . . . . . . . . . . . . . . .
33
2.9. 3-hosszú irányítatlan törhet® körök [18] . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
55
2.10. A 2.22. Tétel 2. esetében a három kölcsönösen keresztez® kör lehetséges elhelyezkedései, illetve az alkalmazott (0,2,2)-mozgások. Az egyszer¶ség kedvéért az 1-hosszú köröket csak akkor tüntetjük fel, ha azok az alkalmazott transzpozíció eredményei, ugyanis a kés®bbi lépésekben ezek nem játszanak szerepet [18] . . . . . . . . . . . . . . . . . . .
34
2.11. Páronként keresztez® körökre alkalmazott 0, majd egy 2-mozgás. A szaggatott vonal vagy egy szürke élet, vagy egy olyan 3-hosszú utat jelöl, amely két fekete és egy szürke élt tartalmaz. [18] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
2.12. TranszpozíciósRendezés2(π) algoritmusa a cirkuláris kromoszómák rendezésére (Hartman, Shamir 2006) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
2.13. Az esetfeldolgozás algoritmusa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
2.14. TranszpozíciósRendezés3(π) algoritmusa a cirkuláris kromoszómák rendezésére (Elias, Hartman 2010) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.1. A π permutációra alkalmazott p(1, j, k) pre x transzpozíció . . . . . . . . . . . . . . .
43
3.2. InverzPermutációRendezés(π) algoritmusa Rn rendezésére (Dias, Meidanis 2002) . . .
50
4.1. A π permutációra alkalmazott p(1, j, k, l) pre x blokk-csere . . . . . . . . . . . . . . .
51
56
Táblázatok jegyzéke 1.1. Eddig elért eredmények a blokk-cserékkel való rendezés alapproblémájában . . . . . . .
5
1.2. A három vibrió törzs cirkuláris kromoszómáinak információ tartalma . . . . . . . . . .
21
1.3. Blokk-csere távolság VV1, VP1, VC1 illetve VV2, VP2 és VC2 között . . . . . . . . .
21
2.1. Eddig elért eredmények a transzpozíciókkal való rendezés alapproblémájában . . . . .
25
2.2. Függvénytáblázat az 1.375-ös approximációs arány bizonyításához . . . . . . . . . . . .
41
3.1. Eddig elért eredmények a pre x transzpozíciókkal való rendezés alapproblémájában . .
42
57
Irodalomjegyzék [1] M. Aigner and D. B. West. Sorting by insertion of leading elements. Theory, Series A,
Journal of Combinatorial
45(2) :306309, 1987. 46
[2] K. Appel, W. Haken, et al. Every planar map is four colorable. part i: Discharging. Journal of Mathematics,
Illinois
21(3) :429490, 1977. 39
[3] V. Bafna and P. A. Pevzner. Sorting by transpositions.
SIAM Journal on Discrete Mathematics,
11(7):224240, 1998. 6, 24, 37, 44, 46, 53 [4] L. Bulteau, G. Fertin, and I. Rusu. Sorting by transpositions is di cult. Mathematics,
SIAM Journal on Discrete
26(12) :11481180, 2012. 24
[5] C.-Y. Chen, K.-M. Wu, Y.-C. Chang, C.-H. Chang, H.-C. Tsai, T.-L. Liao, Y.-M. Liu, H.-J. Chen, A. B.-T. Shen, J.-C. Li, et al. Comparative genome analysis of vibrio vulni cus, a marine pathogen. Genome research,
13(5) :25772587, 2003. 4
[6] B. Chitturi and I. H. Sudborough. Bounding pre x transposition distance for strings and permutations. In
Hawaii International Conference on System Sciences, Proceedings of the 41st Annual,
pages 468468. IEEE, 2008. 42 [7] D. A. Christie. Sorting permutations by block-interchanges.
Information Processing Letters,
60(1):165169, 1996. 4 [8] D. A. Christie.
Genome rearrangement problems.
PhD thesis, University of Glasgow, 1998. 24,
44, 45, 47, 53 [9] U. Dias and Z. Dias. Extending bafna-pevzner algorithm. In Symposium on Biocomputing,
Proceedings of the International
number 13, page 23. ACM, 2010. 24
[10] U. Dias and Z. Dias. An improved 1.375-approximation algorithm for the transposition distance problem. In Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology,
pages 334337. ACM, 2010. 24
[11] Z. Dias and J. Meidanis. Sorting by pre x transpositions. In Retrieval,
pages 6576. Springer, 2002. 42, 45 58
String Processing and Information
[12] I. Elias and T. Hartman. A 1.375-approximation algorithm for sorting by transpositions. utational Biology and Bioinformatics, IEEE/ACM Transactions on,
Comp-
3(11) :369379, 2006. 24, 37,
39 [13] H. Eriksson, K. Eriksson, J. Karlander, L. Svensson, and J. Wästlund. Sorting a bridge hand. Discrete Mathematics,
241(1) :289300, 2001. 37
[14] J. Feng and D. Zhu. Faster algorithms for sorting by transpositions and sorting by block interchanges.
ACM Transactions on Algorithms (TALG),
3(2) :25, 2007. 4, 8, 9, 10, 55
[15] V. Fortuna and J. Meidanis. Sorting the reverse permutation by pre x transpositions. 2004. 47 [16] S. Hannenhalli and P. A. Pevzner. Transforming cabbage into turnip : polynomial algorithm for sorting signed permutations by reversals.
Journal of the ACM (JACM),
46(1):127, 1999. 30
[17] T. Hartman. A simpler 1.5-approximation algorithm for sorting by transpositions. In torial pattern matching,
Combina-
pages 156169. Springer, 2003. 24
[18] T. Hartman and R. Shamir. A simpler and faster 1.5-approximation algorithm for sorting by transpositions.
Information and Computation,
204(10):275290, 2006. 24, 30, 31, 32, 33, 34, 37,
55, 56 [19] J. F. Heidelberg, J. A. Eisen, W. C. Nelson, R. A. Clayton, M. L. Gwinn, R. J. Dodson, D. H. Haft, E. K. Hickey, J. D. Peterson, L. Umayam, et al. Dna sequence of both chromosomes of the cholera pathogen vibrio cholerae.
Nature,
406(6) :477483, 2000. 4
[20] Y.-L. Huang, C.-C. Huang, C. Y. Tang, and C. L. Lu. An improved algorithm for sorting by blockinterchanges based on permutation groups.
Information Processing Letters,
110(4) :345350, 2010.
4 [21] H. Kaplan and E. Verbin. E cient data structures and a new randomized approach for sorting signed permutations by reversals. In
Combinatorial Pattern Matching,
pages 170185. Springer,
2003. 24, 36 [22] A. Labarre. Lower bounding edit distances between permutations. Mathematics,
SIAM Journal on Discrete
27(3):14101428, 2013. 42
[23] G.-H. Lin and G. Xue. Signed genome rearrangement by reversals and transpositions: models and approximations.
Theoretical Computer Science,
259(1) :513531, 2001. 30
[24] Y. C. Lin, C. L. Lu, H.-Y. Chang, and C. Y. Tang. An e cient algorithm for sorting by blockinterchanges and its application to the evolution of vibrio species. Biology,
12(3) :102112, 2005. 4, 12
59
Journal of Computational
[25] J. Meidanis, M. Walter, and Z. Dias. Transposition distance between a permutation and its reverse. In Proceedings
of the 4th South American Workshop on String Processing (WSP'97),
pages 7079,
1997. 47 [26] P. A. Penny D. The nature of the last universal common ancestor. 1999. 1 [27] M. E. M. Walter, L. R. A. Curado, and A. G. Oliveira. Working on the problem of sorting by transpositions on genome rearrangements. In
Combinatorial pattern matching,
pages 372383.
Springer, 2003. 24 [28] G. N. K. E. Wolf YI, Rogozin IB. Genome trees and the tree of life. 2002. 1 [29] U. Zwick. Computer assisted proof of optimal approximability results. In thirteenth annual ACM-SIAM symposium on Discrete algorithms,
dustrial and Applied Mathematics, 2002. 39
60
Proceedings of the
pages 496505. Society for In-
