Simulering av parallellreducering av signerade grafer

Simulering av parallellreducering av signerade grafer

Sebastian Skogman

Seminarieuppsats Informationsbehandling Matematisk-naturvetenskapliga fakulteten Åbo Akademi Oktober 2005

Abstrakt

Ciliater är uråldriga encelliga organismer som finns praktiskt taget i alla miljöer där det finns vatten. Dessa är intressanta för att de använder sig av den mest avancerade DNA manipulation känd i någon organism. En unik egenskap hos ciliater är deras nukleära dualism dvs. att i en enda cell finns två olika sorters kärnor, en makronukleus som sköter om cellens aktivitet och mikronukleus som bara är aktiv vid könlig förökning (meios).

Vid celldelning transformeras en mikronukleus till en makronukleus och detta är genfusion. Vid genfusioner sker en omfattande eliminering och defragmentering av genetiskt material, denna process är speciellt intressant ur datatekniskt perspektiv för den använder sig av datastrukturen länkade listor. Vid genfusion används tre molekylära operationer ld, hi och dlad.

Jag kommer här att närmare gå in på parallellism vid genfusion i ciliater och kommer att använda mig av grafer för att representera gener. Vid genfusion kan flera molekylära operationer utföras parallellt. Jag kommer att förklara hur och när molekylära operationer kan utföras parallellt samt hur många parallellsteg krävs för att transformera en

mikronukleär gen till en makronukleär gen. Det intressanta med antalet parallellsteg är att man får ett mått på hur komplex genfusionen är.

Nyckelord: Ciliater, parallellism, DNA-molekyler, genfusion

Abstrakt

Kapitel__________________________________________________________ sida 1. Inledning

1.1 Introduktion 1

2. Bakgrundsfakta

2.1 Ciliater 1

2.2 Nukleär dualism 2

2.2 Mikronukleus struktur 4

3. Molekylära operationer

3.1 Homologisk rekombination 6

3.2 Rekombination av loopar 7

3.3 Hårnålsrekombination 8

3.4 Rekombination av dubbla loopar 9 4. MDS-arrangemang, MDS-deskriptorer och strängar

4.1 MDS-arrangemang och MDS-deskriptorer 10

4.2 Strängar 11

5. Överlappningsgrafer

5.1 Från strängar till grafer 11

5.2 Grafreducerings regler 13

5.3 Parallellreducering av grafer 16

6. Genfusionssimulator

6.1 Allmänt 18

6.2 Parallellreduceringsalgoritmer 19

6.3 Problem 20

7. Avslutning 21

Litteraturförteckning

1 Inledning

1.1 Introduktion

Biocomputing (på svenska ungefär bioberäkning) kom igång år 1994 när Dr. Leonard Adleman använde sig av DNA för att för att lösa det kända matematiska problemet, en handelsresandes problem. En handelsresandes problem handlar om hur en försäljare skall kunna besöka alla utsatta städer på kortaste möjliga tid, han skall med andra ord finna den kortaste vägen så att alla städer blir besökta. Genom att använda DNA-sekvenser för att representera alla möjliga rutter kunde Dr. Adleman finna den kortaste vägen. En handelsrensandes problem kan vara tungt för en superdator att beräkna om antalet städer är stort men betydligt enklare för DNA som beräknar stora mängder data parallellt [1].

Organismer har otroliga egenskaper att behandla information som t.ex.

mönsterigenkänning, anpassning, att spara information samt mycket mera. På senare tid har intresset och forskningen inom detta område ökat, för man ser stora möjligheter i framtiden. Biologer, biokemister och datavetenskapsmän jobbar tillsammans inom detta område och man tänker sig cellen som en dator. Ciliater är encelliga organismer som har visat sig väldigt intressanta för forskningen för de använder sig av datastrukturen länkade listor [2].

2 Bakgrunds fakta

2.1 Ciliater

Ciliater är encelliga organismer som tros vara 2.5 miljarder år gamla och de finns överallt på jorden där det finns vatten. I en kvadratmeter gyttja finns förekommer det mera ciliater än vad det finns invånare i Finland. Det finns omkring 8000 kända genetiskt olika ciliater och deras storlek kan vara ända upp till två mm eller mera men medelstorleken är 40 till

50 µm. (1/20 av ett sockerkorn). Ciliater kan skilja sig väldigt mycket genetiskt, t.ex.

vissa ciliater skiljer sig mera genetisk än vad bananflugan skiljer sig från människan.

Trots stora genetiska skillnader så är de lika på två punkter, alla ciliater har cilia (relativt korta hårliknande hår) på ytan vilka de använder för att förflytta sig samt att föra näring till sin orala öppning. Det andra som alla ciliater har gemensamt är att de har två cellkärnor, mikronukleus och makronukleus och detta är unikt för ciliater. Mikronukleus används bara under könlig förökningen mellan två ciliater som hör till samma art.

Makronukleus används för att producera proteiner som behövs för cellstrukturen och andra celloperationer. Förökning kan ske genom könlös delning (kloning) eller sexuell förökning (konjugation) [3, 4].

Figur 2.1. Stichotrich [3].

2.2 Nukleär dualism

Det unika med ciliater är deras nukleära dualism, det betyder att de har två kärnor, en mikronukleus som är mindre och en makronukleus som är större. De flesta ciliater har en mikronukleus och en makronukleus men det finns arter som har flera. Stichotrichciliater

har två eller flera mikronuklei och makronuklei och det är dessa som forskningen har fokuserats mest på. Alla mikronuklei är sinsemellan genetiskt identiska likaså alla makronuklei, orsaken till det är ännu idag okänt [5].

Mikronukleus är endast aktiv under den könliga förökningen, den bidrar inte till cellens tillväxt eller andra funktioner. Vid könlig förökning transformeras en mikronukleus till en makronukleus och detta kallas genfusion. Makronukleus gener kodar för de proteiner som cellen behöver för att överleva [5]. När det finns gott om mat växer stichotrichciliater och förökar sig genom könlös celldelning men när det blir ont om mat finns det tre olika alternativ. Första alternativet är att den kan bilda en cysta runt sig själv samt att den minskar i storlek och cellens aktivitet avstannar. Som cysta kan en stichotrich överleva i torra områden i flera år och återupplivas när det igen finns vatten runt den. Andra alternativet för att överleva är att bli kannibalisk. När det finns gott om mat är vissa gener inaktiva men när det blir ont om mat aktiveras dessa kannibalgener, stichotrich ciliaterna blir kannibaliska och äter upp andra ciliater av samma art. Tredje alternativet för en svältande stichotrich är att den kan para sig med en annan svältande stichotrich, troligen för att förbättra diversiteten [3].

DNA-mutationer i gener kan ske genom att de blir utsatta för kemikalier, radioaktivitet eller fel som uppstår när DNA replikeras i en organism. Dessa mutationer hör till evolutionen och för det mesta är de ofarliga för cellen, de påverkar inte cellens funktioner men de kan också påverka cellens funktioner så den t.o.m. dör. Det är ganska ovanligt att dessa mutationer medför att cellen får nya funktioner eller påverkar andra funktioner till cellens nytta. Mutationer som gör cellen bättre kan föras vidare i encelliga organismer genom att de utbyter DNA vid könlig förökning. Bilden nedan visar hur två stichotrich ciliater fusioneras. Allt börjar med att de två organismerna sammanfogar sig och en förbindande kanal upprättas mellan dem (figur 2.2a). Varje stichotrich har två diploida (två kromosomuppsättningar) mikronukleus och dessa undergår meios, av fyra diploida mikronukleus blir det åtta haploida (en kromosomuppsättning) mikronukleus (figur 2.2b).

En haploid mikronukleus ur varje cell förs över till den andra genom förbindelsekanalen och skapar en ny diploid mikronukleus i varje cell genom att fusionera sig med en annan

haploid nukleus. Efter detta är klart separerar cellerna (figur 2.2c). De sex oanvända haploida mikronuklei samt båda makronuklei förstörs och samtidigt delar sig varje diploid mikronukleus genom mitos i varje cell(figur 2.2d). Därefter blir den ena mikronukleus en ny makronukleus och den andra blir den nya diploida mikronukleus (figur 2.2d). I slutskedet av cellfusionen delar sig mikronukleus och makronukleus så att det blir två av varje (figur 2.2e-f) [6].

Figur 2.2. Cellreproduktion [6].

2.3 Mikronukleus struktur

Kromosomerna finns i mikronukleus. Generna är utspridda längs med molekylen och är åtskilda med icke kodande DNA. Generna i mikronukleus hos strichotrich har en struktur som inte observerats i gener hos andra organismer. Generna innehåller icke kodande DNA-segment eller IES (interna eliminerade segment). Förutom IES element så innehåller generna MDS (makronukleära destinerade element) segment som innehåller

kodande DNA. Figur 2.3 visar hur en mikronukleär gen ser ut. Alla segment med siffror ovanför är MDS segment och dessa skiljs åt med IES segment. Vid transformationen från mikronukleus till makronukleus, klipps IES segmenten bort och MDS segmenten ordnas i rätt ordning [7].

Figur 2.3. Mikronukleära gen som kodar βTP protein [6].

MDS segment använder sig av pekare för att vet hur gensegmenten skall ordnas. I varje ända av ett gensegment finns korta sekvenser av nukleotider som illustreras i figur 2.4. Ur figuren framgår att i slutet av MDS 2 finns en sekvens som är likadan som i början av MDS 3, dessa är pekare som säger att MDS 2 följs av MDS 3. Vid genfusion tas IES segmentet samt en pekare från ett MDS segment bort och efter det har MDS 2 och MDS 3 fusionerats [6].

Figur 2.4. Sekvens av en mikronukleär gen [6].

I de flesta mikronukleära gener är MDS segmenten i rätt ordning men det finns exempel där MDS segmenten är i fel ordning. Förutom att MDS segmenten är i fel ordning så kan också de vara inverterade. Vanligen läses MDS segmenten sekvenser från vänster till höger men inverterade segment läses från höger till vänster. För att få dessa mikronukleära gener transformerade till makronukleära, måste MDS segmenten ordnas i rätt ordning samt inverterade segment måste inverteras så att deras sekvens kan läsas från

vänster till höger som alla andra. Figur 2.5 är ett exempel där MDS segmenten är i fel ordning samt MDS segment 2 är inverterat. För att få genen i rätt ordning måste MDS segmenten 5, 2, 1 och 8 flyttas om och MDS segment 2 måste inverteras. Det sista som händer efter att alla IES segment är avlägsnade och alla MDS segment är i rätt ordning är att de nya generna kopieras flera tusen gånger. Orsaken till att det bildas så många kopior är att ju fler kopior det finns desto fortare kan cellen producera de proteiner genen kodar för [8].

Figur 2.5. Mikronukleär gen som kodar actin protein i strichotrich Sterkilla nova [8].

3 Molekylära operationer

3.1 Homologisk rekombination

Under genfusionerna vid bildningen av makronukleus från mikronukleus i stichotricher sker homologisk rekombination mellan pekare. Homologisk rekombination sker mellan två DNA-molekyler som har identiska baspar. När de två molekyler som har identiska baspar har identifierats läggs de bredvid varandra. Efter att de har placerat sig sida vid sida så kommer ett restriktionsenzym att skära i molekylerna och efter det byter molekylerna delar med varandra och ett ligasenzym lappar ihop molekylerna igen.

Resultatet är att två DNA-molekyler har bytt delar med varandra [3].

(a) (b) (c)

Figur 3.1. a-c Homologisk rekombination: a Två identiska baspar placerar sig bredvid varandra. b Klipp utförs där pilarna markerar. c De båda molekylerna sätts ihop igen i omkastad ordning [3].

3.2 Rekombination av loopar

Det finns tre molekylära operationer rekombination av loopar med beteckningen ld, hårnålsrekombination med beteckningen hi och rekombination av dubbla loopar med beteckningen dlad. Vilka molekylära operationer som används vid genfusionsprocessen är beroende på MDS-IES strukturen.

Ld är en enkel molekylär operation som utförs på IES segment som finns mellan två MDS segment som har pekare som pekar på varandra. Figur 3.2 är ett exempel på hur en ld operation går till och där framgår hur MDS 2 pekar på MDS 3 och dessa skiljs åt med ett IES segment. Detta IES segment tas bort med hjälp av ld operationen. Efter att pekarna har identifierats gör DNA-molekylen en enkel loop så de båda pekarna ligger sida vid sida. Efter det sker homologisk rekombination och MDS 2 och MDS 3 kommer att fusioneras [3].

Figur 3.2. Looprekombination.

3.3 Hårnålsrekombination

Hi operationen utförs på molekyler som har par av pekare där den ena är en invers av den andra. Figur 3.4 är ett exempel där man använder sig av hi operationen. Ur figuren framgår att MDS 2 är ett inverterat segment och problemet är att pekare 2 har inverterad polaritet. Genom att göra ett så kallat hårnål sätts de båda pekarna i samma polaritet, därefter utförs homologisk rekombination på MDS 1 och MDS 2 och de fusioneras [3].

Figur 3.3. Hårnålrekombination.

3.4 Rekombination av dubbla loopar

Dlad operationen utförs på DNA-molekyler där det existerar två par pekare. I figur 3.4 finns ett exempel där dlad operationen behövs. Figuren visar att det finns två par pekare P5 och P6 som åtskiljs med ett IES segment. För att avskilja IES segmentet bildar DNA- molekylen två loopar så att pekarna P5 ligger sida vid sida och att pekarna P6 ligger sida vid sida. Efter det sker två rekombinationer, MDS 4 och MDS 5 fusioneras samt MDS 5 och MDS 6 fusioneras [3].

Ld, hi och dlad operationerna kan utföras i många olika kombinationer under genfusion och många av dessa operationer utförs simultant. Vid genfusion används dessa regler för att skapa en ny makronukleus från en mikronukleus. Operationerna gör det möjligt att avlägsna IES segmenten samt att sätta MDS segmenten i rätt ordning [3].

Figur 3.4. Dubbel-looprekombination.

4 MDS arrangemang, MDS deskriptorer och strängar

4.1 MDS-arrangemang och MDS deskriptorer

DNA-molekyler kan representeras av sekvenser av baser där det finns fyra olika bas- typer A, C, G och T, men denna representation är för detaljerad i många fall.

Informationen i en mikronukleus kan istället representeras med MDS arrangemang.

Genen actin I i S.nova, figur 2.5 representerar MDS/IES strukturen, den kan också representeras i formen M ₃ I₁ M ₄ I₂ M ₆ I₃ M ₅ I₄ M ₇ I₅ M ₉ I₆ M ₂ I₇ M ₁ I₈ M ₈ där alla MDS segment har IES segmentmellan sig. Vid genfusion klipps IES segmenten (Ii) bort och MDS segmenten sätts i rätt ordning.Denna struktur är klumpig om man vill studera genfusion i ciliater. Det skulle vara lättare att arbeta med strängar. Vi tänker oss att alla MDS element betecknas M i och alla inversa element M i,om flera MDS element är sammansatta representeras de av M i j. Actin I i S.nova i figur 2.5 skulle representeras av strängen M 3 M 4 M 6 M 5 M 7 M 9 M 2 M 1 M 8 och denna strängrepresentation kallas MDS arrangemang [9].

MDS elementen har pekare som berättar om hur elementen skall ordnas för att få dem i rätt ordning under transformationen från mikronukleus till makronukleus. Alla MDS element i en gen har en ingående pekare i och en utgående pekar i+1 och vi kan använda oss av denna struktur för att representera genen. MDS deskriptorer består av par av pekare och vissa par består av startmärke b (eng. beginning) och slutmärke e (eng.

ending) och dessa märken berättar var genen börjar och slutar. I MDS deskriptorer används inte numret 1 utan det är ersatt av startmärket b. MDS deskriptorer byggs upp av par av pekare enligt Mi = (i, i+1), M₁ = (b,2) och Mk = (k, e). MDS deskriptor för genen actin I S.nova i figur 2.5 är ( 3, 4 )( 4, 5 )( 6, 7 )( 5, 6 )( 7, 8 )( 9, e )( 3 , 2 )( b, 2 )( 8, 9 ) [3].

Exempel:

M3 = ACTGTTTAAA...TATAATCGTA M4 = CGTATAATA...AATCTAGAGG

M3 =(3, 4), där 3 står för ACTG och 4 står för CGTA.

M4 = (4, 5), där 4 står för CGTA och 5 står för CTAGAGG.

[2]

4.2 Strängar

MDS deskriptorer är uppbyggda av par av pekare men vi kan gå till en högre abstraktionsnivå och använda oss av sekvenser av pekare. MDS deskriptorn ( 3, 4 )( 4, 5 )( 6, 7 )( 5, 6 )( 7, 8 )( 9, e )( 3 , 2 )( b, 2 )( 8, 9 ) representeras av den lagliga strängen 3 4 4 5 6 7 5 6 7 8 9 3 2 2 8 9 [3]. Lagliga strängar är strängar där varje symbol förekommer exakt två gånger [10]. Exempel på en laglig sträng är v = 3 4 3 4 här förekommer 3 och 4 exakt två gånger, strängen v = 3 4 3 4 5 är inte en laglig sträng för 5 förekommer endast en gång. Lagliga strängar är en högre abstraktionsnivå än vad MDS deskriptorer är pga. att olika MDS deskriptorer kan ge samma lagliga sträng [3].

5 Överlappningsgrafer

5.1 Från strängar till grafer

I förra avsnittet redogjordes vad MDS arrangemang, MDS deskriptor och lagliga strängar är. Nu kommer jag istället att använda mig av grafer för att representera MDS strukturen hos gener. En signerad graf består av noder som är signerade med + (positiva) och –

(negativa). Förutom noder, består grafen av bågar och varje båge är par av olika noder {x, y}. Signerade grafer representerar strukturen av överlappspekare i en laglig sträng.

Överlappsgrafen för strängen v = 3 4 5 2 3 2 4 5 representeras av figur 5.1 och pekarna 2, 3 och 5 är positiva medan pekare 4 är negativ. Grafen i figur 5.1 fås från den lagliga strängen v = 3 4 5 2 3 2 4 5 genom att se på pekarnas överlappningar. Pekarnas överlappningar är v2 = 2 3 2 (2 överlappar med 3), v3 = 3 4 5 2 3 (3 överlappar med 4, 5 och 2), v4 = 4 5 2 3 2 4 (4 överlappar med 5 och 3) och v5 = 5 2 3 2 4 5 (överlappar med 3 och 4) och dessa ger Ov (2) = {2, 3}, Ov (3) = {2, 3, 4, 5} och Ov (4) = {3, 4, 5} = Ov (5) där Ov(x) står för alla noder som överlappar nod x [11].

Figur 5.1. Signerad överlappningsgraf [12].

När man översätter från MDS/IES strukturen till MDS arrangemang förlorar man lite information för man inte kan översätta från MDS arrangemang tillbaka till MDS/IES strukturen. Informationen som förloras är den om IES segmenten och genom att översätta till MDS arrangemang övergår man till en högre abstraktionsnivå. När MDS arrangemang översätts till MDS deskriptorer förlorar vi ingen information för att MDS deskriptorer kan översättas tillbaka till MDS arrangemang. Man kan säga att MDS arrangemang och MDS deskriptorer är på samma abstraktionsnivå. Igen när MDS deskriptorer översätts till lagliga strängar förlorar vi lite information. Lagliga strängen 2 3 4 5 5 4 3 2 fås från MDS deskriptorn ( b , 2 )( 3 , 4 )( 5 , e )( 5 , 4 )( 3 , 2 ) men strängen kan också fås från MDS deskriptorn ( 2, 3 )( 4, 5 )( e , 5 )( 4 , 3 )( 2 , b ).

Genom att översätta från MDS deskriptorer till lagliga strängar går vi över till en högre abstraktionsnivå. Det samma händer när man översätter från lagliga strängar till grafer, man övergår till en högre abstraktionsnivå. Alla de lagliga strängarna 6 5 7 4 4 6 5 2 3 3 2 7, 7 5 6 7 5 7 4 3 3 4 2 2, 6 5 7 4 4 6 5 2 3 3 2 7 och många andra blir grafen i figur 5.2. [3].

Figur 5.2. Signerad överlappningsgraf [12].

5.2 Grafreduceringsregler

Jag kommer nu att använda mig av signerade grafer för att formalisera genfusion.

Molekylära operationerna ld, hi och dlad modelleras på signerade grafer som gnr, gpr och gdr [12].

Negativa grafregeln gnr (eng. negative graph rule) utförs på noder i en signerad graf som är negativa och isolerade, det betyder att de saknar bågar till andra noder. Exempel på hur en gnr operationen utförs på en signerad graf demonstreras av exemplet i figur 5.3. [12].

Figur 5.3. a Exempel på en signerad graf före operationen gnr2 är utförd. b Resultatet efter att operationen gnr2 är utförd.

Positiva grafregeln gpr (positive graph rule) utförs på noder som är positiva i en signerad graf. När en gpr operation utförs tas nod p bort ur grafen G och alla grannar till den kompletteras (byter tecken, ”-” blir ”+” och ”+” blir ”-”). Om grannen q till p är positiv så blir q negativ och om q är negativ så blir q positiv. Om noderna q och r är grannar till noden p och de har en båge mellan sig så tas den bort och om det inte finns en båge mellan q och r så uppstår en ny båge mellan q och r. Exempel på hur en gpr operationen utförs på en signerad graf demonstreras av exemplet i figur 5.4. [12].

(a) (b)

Figur 5.4. a Exempel på en signerad graf före operationen gpr2 är utförd. b Resultatet efter att operationen gpr2 är utförd.

Dubbelgrafregeln dlad (eng. graph double rule) utförs på två olika noder p och q som tillhör grafen G endast om noderna p och q är negativa och det existerar en båge mellan p och q. Mellan alla grannar ri till nod p vilka inte är grannar till nod q och för alla grannar si till nod q vilka inte är grannar till nod p bildas det bågar till, ifalldet inte redan finns en båge mellan dem. Finns det en båge mellan ri och si tas den bort. Mellan alla noder ti som både är grannar till p och q och alla grannar för nod p och q bildas det bågar om det inte redan existerar och om det existerar bågar tas de bort. Exempel på hur en gdr operationen utförs på en signerad graf demonstreras av exemplet i figur 5.5. [12].

(a) (b)

Figur 5.5. a Exempel på en signerad graf före operationen gdr2,3 är utförd. b Resultatet efter att operationen gdr2,3 är utförd.

Genom att utföra operationerna gdr2, 3 →gdr5, 10 →gdr7, 8 →gpr9 →gpr4 → gpr6 på grafen i figur 5.5. a kommer grafen att reduceras till en tom graf. Alla signerade grafer kan reduceras till tomma grafer genom att använda operationerna gnr, gpr och gdr.

Bevisningen för att alla signerade grafer kan reduceras till tomma grafer genom att använda gnr, gpr och gdr operationerna går att läsa om i boken Computation in Living Cells. Det är också möjligt att reducera grafen i figur 5.5 på flera olika sätt, grafen kan också t.ex. reduceras av operationerna gdr5, 10 →gdr7, 8 →gpr9 3 →gdr2, 6 →gpr4 →gpr3.

På vilket sätt man väljer att reducera grafen är intressant när man studerar komplexiteten hos en graf [12].

Genom att studera hur komplex genfusionen hos ciliater är kan man få ett sätt att mäta komplexiteten. De grafer som endast kräver gnr operationer är de minst komplexa och relativt lätta att reducera medan de grafer som kräver många gdr operationer är de mest invecklade. För att mäta komplexiteten för grafen i figur 5.5. a kan vi använda oss av formeln 3 * Cgdr+ 3 * Cgpr där variabeln C berättar hur komplexa operationerna är.

Ett annat sätt att mäta komplexiteten hos en graf är att mäta hur många operationer det krävs för få den tomma grafen. Komplexiteten för grafen i figur 5.5. a skulle då bli 6 för både första och andra reduceringssättet som används för att reducera grafen. Ett problem är att gpr och gdr operationer kan vara olika komplexa beroende på hur många grannar noderna har. Gnr operationen är alltid enkel medan gpr och gdr operationerna är enkla att

utföra om de saknar grannar. Ciliater verkar endast använda sig av enkla operationer vid genfusion och det har bekräftats av flera experiment [13].

5.3 Parallellreducering av grafer

Parallellism är ett vanligt fenomen inom biomolekylära processer. I kapitel 5.2 reducerades grafen i figur 5.5. a genom en sekvens av molekylära operationer. Nu kommer vi att titta närmare på hur grafreduceringsreglerna kan utföras parallellt. När en mikronukleär gen transformeras till en makronukleär gen i en ciliat kan man anta att alla MDS segment sätts på rätt plats samt borttagningen av IES segmenten sker parallellt. Det är därför denna process sker väldigt snabbt inom en ciliat. Ett antal operationer kan utföras parallellt på en gen om operationerna inte påverkar varandra. Med andra ord operationerna måste vara möjliga att utföra i vilken ordning som helst. En annan sak som parallellism vid genfusion inför är ett nytt sätt att mäta komplexiteten. För att mäta komplexiteten kan man använda sig av hur många parallellsteg en graf kräver för att reduceras. Minsta antalet parallellsteg som en graf kräver för att reduceras till en tom graf är 1 [12].

För grafen i figur 5.6 kan operationerna gnr4, gpr2 och gdr5,6 utföras parallellt, resultatet efter dessa operationer ges i figur 5.7. Man kan inte utföra operationerna gpr2 och gpr3

parallellt trots att det är möjligt att utföra en gpr operation på dem båda. Orsaken är att en gpr operation på nod 2 skull påverka nod 3 så att den blir negativ och det samma sker om en gpr operation utförs på nod 3. Det är inte heller möjligt att utföra operationerna gdr5, 6

och gdr6, 7 parallellt för ifall operationen gdr5, 6 utförs kommer varken bågen mellan nod 6 och 7 eller nod 6 att existera längre i grafen. Efter parallellsteg 1 existerar bara noderna 3 och 7 samt de är negativa utan båge mellan sig. Nu kan man utföra operationerna gnr2

och gnr7 parallellt utan att de påverkar varandra och man får en tom graf. Grafen krävde två parallellsteg för att få en tom graf och man kan säga att komplexiteten för grafen är 2.

En annan möjlighet för att reducera grafen skulle vara att utföra operationerna gnr4, gpr3

och gdr6, 7 i parallellsteg 1 och i parallellsteg 2 utföra operationerna gnr2 och gnr5 och få en tom graf [12].

Figur 5.6. Överlappningsgraf [12].

Figur 5.7. Överlappningsgrafen efter operationerna gnr4, gpr2 och gdr5,6 utförts på grafen i figur 5.6.

För grafen i figur 5.8. finns det sex maximala parallellstrategier som reducerar grafen, {gpr2, gnr4, gdr5,6, gdr8,9}{gnr7, gpr3}, {gpr2, gnr4, gdr6,7, gdr8,9}{gnr5, gpr3}, {gpr2, gnr4, gdr5,7, gdr8,9}{gnr6, gpr3}, {gpr2, gpr3, gnr4, gdr5,6}{gnr7, gpr8, gpr9}, {gpr2, gpr3, gnr4, gdr5,7}{gnr6, gpr8, gpr9},{gpr2, gpr3, gnr4, gdr6,7}{gnr5, gpr8, gpr9}. Totala antalet lösningar för att reducera grafen är 3060 [12].

Figur 5.8. Överlappningsgraf för actin I i S.nova [12].

6 Genfusionssimulator

6.1 Allmänt

Jag har utvecklat en genfusionssimulator i syfte att göra det enklare att testa och bevisa olika teorier om överlappningsgrafer. Genfusionssimulatorn gör det möjligt att smidigt och enkelt rita upp överlappningsgrafer samt man kan lätt kan ta reda på den maximala parallellreduceringsstrategin för grafen. En annan funktion som byggts in för forsknings- och undervisningssyfte är en sökfunktion. Den fungerar så att den genererar överlappningsgrafer automatiskt enligt dina specifikationer och den försöker lösa dem på ett x antal parallellsteg som du kan specificera. Om sökfunktionen inte hittar en lösning för en graf på x parallellsteg så avbryts sökningen och grafen visas. I den tekniska rapporten ”Parallelism in Gene Assembly” 611, TUCS, 2004 skriven av Tero Harju, Chang Li, Ion Petre, hade de två hypoteser som har mot bevistats med simulatorns hjälp.

En av deras hypoteser var att alla överlappningsgrafer med endast negativa noder är att det alltid finns en lösning för dem som maximalt kräver två parallellsteg men simulatorn lyckades finna överlappningsgrafer med endast negativa noder vilka det inte är möjligt att lösa på två parallellsteg. Andra hypotesen i deras tekniska rapport var att alla överlappningsgrafer som består både av positiva och negativa noder alltid kan reduceras till den tomma grafen på fyra parallellsteg. Men simulatorn lyckades också till denna hypotes hitta grafer som det inte var möjligt att lösa i fyra parallellsteg. Frågan är ännu öppen idag för hur många parallellsteg som krävs för att reducera en överlappningsgraf.

Utan simulatorns hjälp skulle det vara nästan omöjligt att försöka motbevisa en hypotes eller att stärka en hypotes. En graf behöver inte bestå av många noder förrän det finns tusentals sekvensreduceringsstrategier för den, t.ex. överlappningsgrafen i figur 5.7. har 3060 sekvensreduceringsstrategier. Simulatorns största fördel är att det är möjligt att gå igenom ett stort antal grafer på en kort tid.

Figur 6.1. Genfusionssimulator [15].

6.2 Parallellreduceringsalgoritmer

I genfusionssimulatorn finns två olika algoritmer att välja på när man vill finna den optimala parallellreduceringsstrategin för en graf. Den ena algoritmen är girig och snabb och den andra är långsam men går istället igenom alla möjliga parallellreduceringsstrategier för grafen, den garanterar att man har hittat den bästa strategin. Den giriga algoritmen fungerar så att den utför så många operationer som möjligt på en graf i varje parallellsteg. Denna strategi fungerar för det mesta men det finns grafer där den inte finner den optimala parallellreduceringsstrategin. Exempel på en på en graf som den giriga algoritmen inte finner den optimala parallellreduceringsstrategin figureras i figur 6.2. Med den giriga algoritmen finner man att den optimala parallellreduceringsstrategin är 5 parallellsteg men om man använder algoritmen som går igenom precis alla strategier så ger den oss svaret 4 parallellsteg.

Figur 6.2. Överlappningsgraf.

6.3 Problem

Problemet idag med simulatorn är att tiden det tar för att hitta den optimala parallellreduceringsstrategin för en graf är lång. En orsak är att Java inte är det optimalaste språket för att få snabbhet, en annan orsak är hur sökfunktionerna är implementerade. Sökfunktionerna kan optimeras en hel del och många optimeringar håller redan på att implementeras. Flera radikala förbättringar har redan gjorts, t.ex. för överlappningsgrafen i figur 6.3 tog det ungefär tre timmar att hitta den optimala parallellreduceringsstrategin på en dator med en Pentium 4 processor på 2,6 Ghz med 512 Mb i minne. Efter en optimeringen av koden tog det ett par sekunder med samma maskin att hitta den optimala parallellreduceringsstrategin. De förändringar som gjordes var att onödiga permutationstester slopades. Största problemet är nog att beräkningarna som simulatorn måste utföra ökar exponentiellt för varje nod. Redan när en graf är över 20 noder med många bågar tar länge att hitta den optimala grafreduceringsstrategin och på det här problemet finns det ingen enkel lösning.

Figur 6.3. Överlappningsgraf bestående av endast positiva noder.

7 Avslutning

De senaste åren har molekylärbiologin och informationsteknologin utvecklats mycket.

Bioteknologins utveckling har gjort att det produceras mera biologisk data nu än det någonsin har gjorts. Det behövs olika IT-verktyg för att kunna bearbeta denna mängd data och många andra problem kräver IT-relaterat tillvägagångssätt för att lösas. Det är inte bara molekylärbiologin som drar nytta av datavetenskapen utan också datavetenskapen ser stora potentiella möjligheter att använda sig av biologiska system för att spara information, göra snabba beräkningar, mönsterigenkänning, parallellism och energisnåla datorer. Detta är ett område som både biokemister och informationsbehandlare kompletterar varandra i [2].

Genom att använda biologisk hårdvara och verktyg är det möjligt att göra otroligt snabba och effektiva beräkningar pga. att man kan använda sig av den parallellism som sker i naturen. Andra fördelar är att energiförbrukningen är mycket låg samt otroliga mängder data kan sparas på ett litet utrymme [2]. T.ex. på ett gram DNA ryms det all den information som skapats av människan idag eller motsvarande en triljon cd-skivor [14].

Fördelen med att använda biologisk hårdvara och verktyg är mycket lockande men ännu idag finns det många problem som måste lösas före det är möjligt att få datorer med alla dessa nya önskvärda egenskaper [2].

Orsaken till att beräkningar i naturen går väldigt fort är att dessa beräkningar utförs parallellt och det finns mycket ännu att forska inom detta område. Jag hoppas att den genfusionssimulator jag har utvecklat kan användas för att ge svar på en liten del av frågorna om parallellism som ställs vid genfusion.

Litteraturförteckning

Böcker

[3] Andrzej Ehrenfeucht, Tero Harju, Ion Petre, David Prescott, Grzegorz Rozenberg, Computing in living cells, utgiven December 2004.

Rapporter

[5] Harju, Tero 2004. A Combinatorial View on Gene Assembly. TUCS tekniskrapport nr.588. Turku: Turku Center for Computer Science.

Hämtat 10.11.2005

[6] Harju, Tero, Petre, Ion, Rozenberg, Grzegorz 2003. Gene Assembly in Ciliates:

Molecular operations. TUCS tekniskrapport nr.557. Turku: Turku Center for Computer Science.

Hämtat 10.11.2005

[7] Harju, Tero and Petre, Ion and Rozenberg, Grzegorz 2004. Two Models for Gene Assembly in Ciliates. TUCS tekniskrapport nr.604. Turku: Turku Center for Computer Science.

Hämtat 10.11.2005

[8] Harju, Tero, Petre, Ion, Rozenberg, Grzegorz 2005. Modeling Simple Operations for Gene Assembly. TUCS tekniskrapport nr.697. Turku: Turku Center for Computer Science.

Hämtat 10.11.2005

[9] Harju, Tero, Petre, Ion, Rozenberg, Grzegorz 2003. Gene Assembly in Ciliates:

Formal frameworks. TUCS tekniskrapport nr.558. Turku: Turku Center for Computer Science.

Hämtat 10.11.2005

[10] Harju, Tero, Rozenberg, Grzegor. Computational Processes in Living Cells:

Gene Assembly in Ciliates.

Hämtat 10.11.2005

[11] Harju, Tero, Petre, Ion, Rozenberg, Grzegorz 2003. Formal Properties of Gene Assembly : Equivalence Problem for Overlap Graphs. TUCS tekniskrapport nr.548. Turku: Turku Center for Computer Science.

Hämtat 10.11.2005

[12] Harju, Tero, Li, Chang, Petre, Ion 2004. Parallelism in Gene Assembly.

TUCS tekniskrapport nr.611. Turku: Turku Center for Computer Science.

Hämtat 10.11.2005

Föreläsningsmaterial

[2] Petre, Ion 2005. Föreläsningsmaterial för kursen Computational processes in living cells, våren 2005.

http://www.abo.fi/~ipetre/compproc/

Hämtat 10.11.2005

[13] Petre, Ion 2005. Föreläsningsmaterial för kursen Computational processes in living cells, lecture10.pdf våren 2005.

http://www.abo.fi/~ipetre/compproc/lecture10.pdf Hämtat 10.11.2005

Internet källor

[1] BBC News, Processing power of single cells 2001.

http://news.bbc.co.uk/1/hi/sci/tech/1535945.stm Hämtat 10.11.2005

[4] Wikipedia 2005. Ciliate.

http://en.wikipedia.org/wiki/Ciliate Hämtat 10.11.2005

[14] Artikel av Heidi Backas i Meddelanden från Åbo Akademi Nr. 13 31.10.2003.

Stora problem, trevliga tillämpningar.

http://www.abo.fi/meddelanden/forskning/2003_13_petre.sht Hämtat 10.11.2005.

[15] Genfusionssimulator.

http://combio.abo.fi Hämtat 19.01.2006