3 STATE MODELLER
Tanken med att kombinera förutsägelserna till en komplett genstruktur är att de ”grammatiska” begränsningarna kan utesluta vissa felaktiga sammansättningar av exoner. Problemets grammatiska struktur har betonats av David Searls (Searls, 1992; Dong och Searls, 1994), som också föreslog att man skulle använda sig av metoder för formella grammatiker från datavetenskap och lingvistik. Den dynamiska programmeringen kan ofta beskrivas på ett smidigt sätt med någon form av finita automater (Searls och Murphy, 1995; Durbin et al., 1998). En modell kan ha ett tillstånd för översättningsstart (S), ett för donatorplatser (D), ett för acceptatorplatser (A) och ett för översättningsavslut (T). Varje gång en övergång görs från ett tillstånd till ett annat läggs en poäng (eller ett straff) till. Vid övergången från givartillståndet till acceptortillståndet läggs intronpoängen till den totala poängen, och så vidare. I figur 11.2 visas tillståndsdiagrammet för den enkla dynamiska programmeringsalgoritmen ovan. För varje variabel i algoritmen finns det ett motsvarande tillstånd med samma namn, och det behövs också ett start- och sluttillstånd.
Figur 11.2. En automat med ändliga tillstånd som motsvarar den enkla DP-algoritmen.
Fördelen med en sådan formulering är att den dynamiska programmeringen för att hitta den maximala poängen (eller det minsta straffet) är av en mer allmän typ, och därför är det lätt att lägga till nya tillstånd eller nya övergångar. Att till exempel rita tillståndsdiagrammet för en mer allmän dynamisk programmeringsalgoritm som tillåter valfritt antal gener och även partiella gener är okomplicerat (figur 11.3), medan det är komplicerat att skriva ner. På samma sätt visas tillståndsdiagrammet för den rammedvetna algoritm som skisserats ovan i figur 11.4.
Figur 11.3. Modellen i figur 11.2 med tillägg av övergångar som gör det möjligt att förutsäga ett valfritt antal gener och delgener där sekvensen börjar eller slutar mitt i ett exon eller intron.
Figur 11.4. En modell som säkerställer att ramarna är konsekventa i hela genen. Liksom i de två föregående figurerna motsvarar streckade linjer intergeniska regioner, streckade introner och hela linjer kodande regioner (exoner).
Om de poäng som används är log sannolikheter eller log odds är en automat med ändliga tillstånd i huvudsak en dold Markov-modell (HMM), och dessa har nyligen införts i genfyndighet av flera grupper. Den enda grundläggande skillnaden från de dynamiska programmeringsscheman som diskuterats ovan är att dessa modeller är helt probabilistiska, vilket har vissa fördelar. En av fördelarna är att viktningsproblemet är lättare.
VEIL (Henderson et al., 1997) är en tillämpning av en HMM på problemet med att hitta gener. I denna modell är alla sensorer HMM:er. Exonmodulen är i huvudsak en inhomogen Markovkedja av första ordningen, som beskrivs ovan. Detta är den naturliga ordningen för genomförande i en HMM, eftersom var och en av de betingade sannolikheterna i den inhomogena Markov-kedjan då motsvarar sannolikheten för en övergång från ett tillstånd till nästa i HMM. Det är inte möjligt att undvika stoppkodoner i läsramen när man använder en modell av första ordningen, men i VEIL läggs ytterligare några tillstånd till på ett smart sätt, vilket gör att sannolikheten för en stoppkodon blir noll. Sensorer för skarvplatser görs på ett liknande sätt. De enskilda modulerna kombineras sedan i huvudsak som i figur 11.2 (dvs. ramkonsistens upprätthålls inte). Den kombinerade modellen är en enda stor HMM, och alla övergångar har tillhörande sannolikheter. Dessa sannolikheter kan uppskattas från en uppsättning träningsdata med hjälp av en maximum likelihood-metod. För att kombinera modellerna handlar det i huvudsak om att räkna förekomsten av de olika typerna av övergångar i datasetet. Därför är den implicita viktningen av de enskilda sensorerna egentligen inte ett problem.
Och även om det sätt på vilket den optimala genstrukturen hittas liknar andan i den dynamiska programmeringen ovan, ser det helt annorlunda ut i praktiken. Detta beror på att den dynamiska programmeringen görs på nivån för de enskilda tillstånden i alla delmodeller; det finns mer än 200 sådana tillstånd i VEIL. Eftersom modellen är helt probabilistisk kan man beräkna sannolikheten för varje sekvens av tillstånd för en given DNA-sekvens. Denna tillståndssekvens (kallad path) bestämmer tilldelningen av exoner och introner. Om banan går genom exonmodellen märks den delen av sekvensen som exon, om den går genom intronmodellen märks den som intron och så vidare. Den dynamiska programmeringsalgoritmen, som kallas Viterbi-algoritmen, hittar den mest sannolika vägen genom modellen för en given sekvens, och från denna härleds den förutsagda genstrukturen (se Rabiner (1989) för en allmän introduktion till HMM:er).
Denna probabilistiska modell har den fördelen att den löser problemet med att vikta de enskilda sensorerna. Maximal sannolikhetsuppskattningen av parametrarna kan visas vara optimal om det finns tillräckligt med träningsdata och om genernas statistiska natur kan beskrivas med en sådan modell. En svag del av VEIL är exonmodellen av första ordningen, som förmodligen inte kan fånga statistiken i kodande regioner, och de flesta andra metoder använder modeller av fjärde eller femte ordningen.
En HMM-baserad genuppsökare kallad HMMgene håller för närvarande på att utvecklas. Den grundläggande metoden är densamma som VEIL, men den innehåller flera utvidgningar av standard HMM-metodiken, vilka beskrivs av Krogh (1997). En av de viktigaste är att kodningsregioner modelleras av en inhomogen Markov-kedja av fjärde ordningen i stället för en kedja av första ordningen. Detta görs genom en nästan trivial utvidgning av standard HMM-formalismen, som tillåter en Markovkedja av valfri ordning i ett tillstånd i modellen, medan standard HMM har en enkel ovillkorlig sannolikhetsfördelning över de fyra baserna (motsvarande 0:e ordningen). Modellen är rammedveten och kan förutsäga ett valfritt antal gener och delgener, så modellens övergripande struktur är som i figur 11.4 med övergångar som lagts till för att möjliggöra början och slut i introner, som i figur 11.3.
Som redan nämnts fungerar metoden för maximal sannolikhetsuppskattning bra om modellens struktur kan beskriva den sanna statistiken för generna. Detta är ett mycket idealiserat antagande, och därför använder HMMgene en annan metod för att skatta parametrarna som kallas villkorlig maximal sannolikhet (Juang och Rabiner, 1991; Krogh, 1994). Grovt uttryckt maximerar maximal sannolikhet sannolikheten för DNA-sekvenserna i träningsuppsättningen, medan villkorlig maximal sannolikhet maximerar sannolikheten för genstrukturerna för dessa sekvenser, vilket trots allt är vad vi är intresserade av. Denna typ av optimering liknar begreppsmässigt den som används i GeneParser, där prediktionsnoggrannheten också optimeras. HMMgene använder också en algoritm för dynamisk programmering som skiljer sig från Viterbi-algoritmen för förutsägelse av genstrukturen. Alla dessa metoder har bidragit till en hög prestanda hos HMMgene.
Genie är ett annat exempel på en probabilistisk tillståndsmodell som kallas en generaliserad HMM (Kulp et al., 1996; Reese et al., 1997). Figur 11.4 är i själva verket Genies tillståndsstruktur, och både denna figur och figur 11.2 är i huvudsak kopierade från Kulp et al. (1996). I Genie är signalsensorerna (skarvplatser) och innehållssensorerna (kodningspotential) neurala nätverk, och resultatet av dessa nätverk tolkas som sannolikheter. Denna tolkning kräver uppskattning av ytterligare sannolikhetsparametrar som fungerar som vikter för sensorerna. Även om den är formulerad som en probabilistisk modell, är viktningsproblemet fortfarande förklätt. Algoritmen för förutsägelse är nästan identisk med algoritmen för dynamisk programmering i förra avsnittet. En version av Genie inkluderar även databaslikheter som en del av exonsensorn (Kulp et al., 1997).
Det finns två huvudfördelar med generaliserade HMM:er jämfört med standard HMM:er. För det första kan de enskilda sensorerna vara av vilken typ som helst, t.ex. neurala nätverk, medan de i en standard-HMM är begränsade av HMM-ramen. För det andra kan längdfördelningen (av t.ex. kodningsregioner) beaktas explicit, medan den naturliga längdfördelningen för en HMM är en geometrisk fördelning, som avtar exponentiellt med längden. Det är dock möjligt att ha en ganska avancerad längdmodellering i en HMM om flera tillstånd används (Durbin et al., 1998). Fördelen med ett system som HMMgene är å andra sidan att det är en integrerad modell som kan optimeras på en gång för maximal prediktionsnoggrannhet.
En annan genupptäckare som bygger på en generaliserad HMM är GENSCAN (Burge och Karlin, 1997). De viktigaste skillnaderna mellan GENSCANs tillståndsstruktur och Genie eller HMMgene är att GENSCAN modellerar sekvensen i båda riktningarna samtidigt. I många genfinnare, t.ex. de som beskrivs ovan, förutsägs gener först på den ena strängen och sedan på den andra. Modellering av båda strängarna samtidigt gjordes mycket framgångsrikt i GeneMark, och en liknande metod har implementerats i GENSCAN. En fördel (och kanske den viktigaste) är att denna konstruktion undviker förutsägelser av överlappande gener på de två strängarna, som förmodligen är mycket sällsynta i det mänskliga genomet. GENSCAN modellerar ett obegränsat antal gener och delgener på samma sätt som HMMgene. Sensorerna i GENSCAN liknar dem som används i HMMgene. Kodningssensorn är till exempel en inhomogen Markov-kedja av femte ordningen. Signalsensorerna är i huvudsak positionsberoende viktmatriser, och liknar därmed också i hög grad dem i HMMgene, men det finns mer avancerade funktioner i skarvplatsmodellerna. GENSCAN modellerar även promotorer och 5′ och 3′ UTRs.