3 STATUSMODELLER
Tanken med at kombinere forudsigelserne til en komplet genstruktur er, at de “grammatiske” begrænsninger kan udelukke nogle forkerte exon-sammensætninger. Problemets grammatiske struktur er blevet fremhævet af David Searls (Searls, 1992; Dong og Searls, 1994), som også foreslog at anvende metoderne for formelle grammatikker fra datalogi og lingvistik. Den dynamiske programmering kan ofte beskrives på en praktisk måde ved hjælp af en slags finite state automaton (Searls og Murphy, 1995; Durbin et al., 1998). En model kan have en tilstand for oversættelsesstart (S), en for donorsteder (D), en for acceptorsteder (A) og en for oversættelsesafslutning (T). Hver gang der foretages en overgang fra en tilstand til en anden, tilføjes der en score (eller en straf). Ved overgangen fra donortilstanden til accepttilstanden lægges intron-scoren til den samlede score osv. I figur 11.2 er tilstandsdiagrammet vist for den enkle dynamiske programmeringsalgoritme ovenfor. For hver variabel i algoritmen er der en tilsvarende tilstand med samme navn, og der er også brug for en begyndelses- og sluttilstand.
Figur 11.2. En finite state automaton svarende til den simple DP-algoritme.
Førdelen ved en sådan formulering er, at den dynamiske programmering til at finde den maksimale score (eller den mindste straf) er af en mere generel type, og det er derfor let at tilføje nye tilstande eller nye overgange. F.eks. er det ligetil at tegne tilstandsdiagrammet for en mere generel dynamisk programmeringsalgoritme, der tillader et vilkårligt antal gener og også partielle gener (figur 11.3), mens det er kompliceret at skrive det ned. På samme måde er tilstandsdiagrammet for den ovenfor skitserede frame-aware algoritme vist i figur 11.4.
Figur 11.3. Modellen i figur 11.2 med tilføjede overgange, der giver mulighed for forudsigelse af et vilkårligt antal gener og delgener, hvor sekvensen starter eller slutter midt i et exon eller intron.
Figur 11.4. En model, der sikrer rammekonsistens i hele et gen. Som i de to foregående figurer svarer stiplede linjer til intergeniske regioner, stiplede til introner og hele linjer til kodningsregioner (exoner).
Hvis de anvendte scoringer er log-sandsynligheder eller log-odds, så er en finite state automaton i det væsentlige en skjult Markov-model (HMM), og disse er for nylig blevet indført i genfindelse af flere grupper. Den eneste grundlæggende forskel fra de dynamiske programmeringsordninger, der er drøftet ovenfor, er, at disse modeller er fuldt probabilistiske, hvilket har visse fordele. En af fordelene er, at vægtningsproblemet er lettere.
VEIL (Henderson et al., 1997) er en anvendelse af en HMM på genfindingsproblemet. I denne model er alle sensorer HMM’er. Exonmodulet er i det væsentlige en inhomogen Markov-kæde af første orden, som er beskrevet ovenfor. Dette er den naturlige rækkefølge for implementering i en HMM, fordi hver af de betingede sandsynligheder i den inhomogene Markov-kæde svarer til sandsynligheden for en overgang fra én tilstand til den næste i HMM’en. Det er ikke muligt at undgå stopkodoner i læserammen, når man anvender en model af første orden, men i VEIL tilføjes der på en smart måde et par tilstande mere, hvilket gør sandsynligheden for en stopkodon lig nul. Sensorer for splejsesteder laves på en lignende måde. De enkelte moduler kombineres derefter i det væsentlige som i figur 11.2 (dvs. rammekonsistens er ikke håndhævet). Den kombinerede model er én stor HMM, og alle overgange har tilknyttede sandsynligheder. Disse sandsynligheder kan estimeres ud fra et sæt træningsdata ved hjælp af en maximum likelihood-metode. For at kombinere modellerne kan dette i det væsentlige koges ned til at tælle forekomsten af de forskellige typer af overgange i datasættet. Derfor er den implicitte vægtning af de enkelte sensorer ikke rigtig et problem.
Og selv om den måde, hvorpå den optimale genstruktur findes, i ånden ligner den dynamiske programmering ovenfor, ser det i praksis helt anderledes ud. Det skyldes, at den dynamiske programmering foretages på niveauet for de enkelte tilstande i alle delmodellerne; der er mere end 200 sådanne tilstande i VEIL. Da modellen er fuldt probabilistisk, kan man beregne sandsynligheden for enhver sekvens af tilstande for en given DNA-sekvens. Denne tilstandssekvens (kaldet en sti) bestemmer tildelingen af exoner og introner. Hvis stien går gennem exonmodellen, betegnes den pågældende del af sekvensen som exon; hvis den går gennem intronmodellen, betegnes den som intron, osv. Den dynamiske programmeringsalgoritme, som kaldes Viterbi-algoritmen, finder den mest sandsynlige vej gennem modellen for en given sekvens, og heraf udledes den forudsagte genstruktur (se Rabiner (1989) for en generel introduktion til HMM’er).
Denne probabilistiske model har den fordel, at den løser problemet med vægtning af de enkelte sensorer. Det kan påvises, at maximum likelihood-estimationen af parametrene er optimal, hvis der er tilstrækkelige træningsdata, og hvis genernes statistiske karakter kan beskrives af en sådan model. En svag del af VEIL er exonmodellen af første orden, som sandsynligvis ikke er i stand til at indfange statistikken i kodningsregioner, og de fleste andre metoder anvender modeller af fjerde eller femte orden.
En HMM-baseret genfinder kaldet HMMgene er under udvikling i øjeblikket. Den grundlæggende metode er den samme som VEIL, men den omfatter flere udvidelser af standard HMM-metoden, som er beskrevet af Krogh (1997). En af de vigtigste er, at kodningsregioner modelleres ved hjælp af en inhomogen Markov-kæde af fjerde orden i stedet for en kæde af første orden. Dette sker ved en næsten triviel udvidelse af standard-HMM-formalismen, som tillader en Markov-kæde af en hvilken som helst orden i en tilstand i modellen, hvorimod standard-HMM’en har en simpel ubetinget sandsynlighedsfordeling over de fire baser (svarende til 0. orden). Modellen er frame-aware og kan forudsige et vilkårligt antal gener og delgener, så modellens overordnede struktur er som i figur 11.4 med overgange tilføjet for at tillade begyndelse og afslutning i introner, som i figur 11.3.
Som allerede nævnt fungerer maximum likelihood estimationsmetoden godt, hvis modellens struktur kan beskrive den sande statistik for generne. Dette er en meget idealiseret antagelse, og derfor anvender HMMgene en anden metode til estimering af parametrene kaldet betinget maksimal sandsynlighed (Juang og Rabiner, 1991; Krogh, 1994). Groft sagt maksimerer maximum likelihood sandsynligheden for DNA-sekvenserne i træningssættet, mens conditional maximum likelihood maksimerer sandsynligheden for genstrukturerne af disse sekvenser, som trods alt er det, vi er interesseret i. Denne form for optimering svarer konceptuelt set til den, der anvendes i GeneParser, hvor forudsigelsesnøjagtigheden også optimeres. HMMgene anvender også en dynamisk programmeringsalgoritme, der er forskellig fra Viterbi-algoritmen, til forudsigelse af genstrukturen. Alle disse metoder har bidraget til en høj ydeevne for HMMgene.
Genie er et andet eksempel på en probabilistisk tilstandsmodel, som kaldes en generaliseret HMM (Kulp et al., 1996; Reese et al., 1997). Figur 11.4 er i virkeligheden Genies tilstandsstruktur, og både denne figur og figur 11.2 er i det væsentlige kopieret fra Kulp et al. (1996). I Genie er signalsensorerne (splejsesteder) og indholdssensorerne (kodningspotentiale) neurale netværk, og output fra disse netværk fortolkes som sandsynligheder. Denne fortolkning kræver estimering af yderligere sandsynlighedsparametre, der fungerer som vægte på sensorerne. Så selv om den er formuleret som en probabilistisk model, er vægtningsproblemet stadig skjult. Algoritmen til forudsigelse er næsten identisk med algoritmen for dynamisk programmering fra sidste afsnit. En version af Genie omfatter også databaseligheder som en del af exon-sensoren (Kulp et al., 1997).
Der er to hovedfordele ved generaliserede HMM’er sammenlignet med standard-HMM’er. For det første kan de enkelte sensorer være af en hvilken som helst type, f.eks. neurale netværk, hvorimod de i en standard-HMM er begrænset af HMM-rammen. For det andet kan der eksplicit tages hensyn til længdefordelingen (af f.eks. kodningsområder), hvorimod den naturlige længdefordeling for en HMM er en geometrisk fordeling, som falder eksponentielt med længden. Det er dog muligt at have en ret avanceret længdemodellering i en HMM, hvis der anvendes flere tilstande (Durbin et al., 1998). Fordelen ved et system som HMMgene er derimod, at det er én integreret model, som kan optimeres på én gang for at opnå maksimal forudsigelsesnøjagtighed.
En anden genfinder, der er baseret på en generaliseret HMM, er GENSCAN (Burge og Karlin, 1997). De væsentligste forskelle mellem GENSCAN’s tilstandsstruktur og Genie eller HMMgene er, at GENSCAN modellerer sekvensen i begge retninger samtidig. I mange genfindere, som f.eks. de ovenfor beskrevne, forudsiges generne først på den ene streng og derefter på den anden. Modellering af begge strenge samtidig blev udført med stor succes i GeneMark, og en lignende metode er implementeret i GENSCAN. En fordel (og måske den vigtigste) er, at man ved denne konstruktion undgår forudsigelser af overlappende gener på de to strenge, hvilket formodentlig er meget sjældent i det menneskelige genom. GENSCAN modellerer et vilkårligt antal gener og delgener ligesom HMMgene. Sensorerne i GENSCAN svarer til dem, der anvendes i HMMgene. F.eks. er kodningssensoren en inhomogen Markov-kæde af femte orden. Signalsensorerne er i det væsentlige positionsafhængige vægtmatricer og ligner således også i høj grad dem i HMMgene, men der er mere avancerede funktioner i splejsningsstedsmodellerne. GENSCAN modellerer også promotorer og 5′ og 3′ UTR’erne.