3 STAATSMODELLEN
Het idee om de voorspellingen te combineren tot een volledige genstructuur is dat de ‘grammaticale’ constraints enkele verkeerde exon-assemblages kunnen uitsluiten. De grammaticale structuur van het probleem is benadrukt door David Searls (Searls, 1992; Dong en Searls, 1994), die ook voorstelde de methoden van formele grammatica’s uit de informatica en de taalkunde te gebruiken. De dynamische programmering kan vaak handig worden beschreven door een soort eindige toestandsautomaat (Searls en Murphy, 1995; Durbin et al., 1998). Een model kan een toestand hebben voor translatiebegin (S), een voor donorsites (D), een voor acceptorsites (A) en een voor translatiebeëindiging (T). Elke keer dat een overgang wordt gemaakt van de ene toestand naar de andere, wordt een score (of een penalty) toegevoegd. Voor de overgang van de donortoestand naar de acceptortoestand wordt de intron-score bij de totale score opgeteld, enzovoort. In figuur 11.2 wordt het toestandsdiagram getoond voor het eenvoudige dynamische programmeeralgoritme hierboven. Voor elke variabele in het algoritme is er een overeenkomstige toestand met dezelfde naam, en ook een begin- en eindtoestand zijn nodig.
Figuur 11.2. Een eindige-toestandsautomaat die overeenkomt met het eenvoudige DP-algoritme.
Het voordeel van een dergelijke formulering is dat de dynamische programmering voor het vinden van de maximale score (of minimale straf) van een algemener type is, en dat het toevoegen van nieuwe toestanden of nieuwe overgangen dus eenvoudig is. Zo is het tekenen van het toestandsdiagram voor een algemener dynamisch programmeringsalgoritme dat een willekeurig aantal genen en ook partiële genen toestaat, eenvoudig (figuur 11.3), terwijl het opschrijven ervan veel voeten in de aarde heeft. Op dezelfde manier is het toestandsdiagram voor het hierboven geschetste frame-aware algoritme weergegeven in figuur 11.4.
Figuur 11.3. Het model van figuur 11.2 met toegevoegde overgangen die het mogelijk maken een willekeurig aantal genen en partiële genen te voorspellen waarbij de sequentie begint of eindigt in het midden van een exon of intron.
Figuur 11.4. Een model dat zorgt voor frame consistentie in een gen. Net als in de twee vorige figuren komen stippellijnen overeen met intergene regio’s, stippellijnen met introns en volle lijnen met coderende regio’s (exonen).
Als de gebruikte scores log waarschijnlijkheden of log kansen zijn, dan is een eindige-toestand automaat in wezen een verborgen Markov model (HMM), en deze zijn onlangs door verschillende groepen geïntroduceerd in gen-vinding. Het enige fundamentele verschil met de hierboven besproken dynamische programmeringsschema’s is dat deze modellen volledig probabilistisch zijn, hetgeen bepaalde voordelen heeft. Een van de voordelen is dat het wegingsprobleem eenvoudiger is.
VEIL (Henderson et al., 1997) is een toepassing van een HMM op het gen-vindprobleem. In dit model zijn alle sensoren HMM’s. De exon-module is in wezen een eerste-orde inhomogene Markov-keten, die hierboven is beschreven. Dit is de natuurlijke volgorde voor implementatie in een HMM, omdat dan elk van de voorwaardelijke waarschijnlijkheden van de inhomogene Markov-keten overeenkomt met de waarschijnlijkheid van een overgang van de ene toestand naar de volgende in de HMM. Het is niet mogelijk om stopcodons in het leesraam te vermijden bij gebruik van een eerste-orde model, maar in VEIL worden op een slimme manier een paar extra toestanden toegevoegd, waardoor de waarschijnlijkheid van een stopcodon nul wordt. Sensoren voor splitsingsplaatsen worden op een soortgelijke manier gemaakt. De afzonderlijke modules worden vervolgens gecombineerd zoals in figuur 11.2 (d.w.z. frame-consistentie wordt niet afgedwongen). Het gecombineerde model is één grote HMM, en alle overgangen hebben bijbehorende waarschijnlijkheden. Deze waarschijnlijkheden kunnen worden geschat uit een reeks trainingsgegevens door middel van een maximum likelihood methode. Voor het combineren van de modellen komt dit in wezen neer op het tellen van het voorkomen van de verschillende soorten overgangen in de dataset. Daarom is de impliciete weging van de afzonderlijke sensoren niet echt een probleem.
Hoewel de manier waarop de optimale genstructuur wordt gevonden in de geest vergelijkbaar is met de dynamische programmering hierboven, ziet het er in de praktijk heel anders uit. Dit komt doordat de dynamische programmering wordt uitgevoerd op het niveau van de afzonderlijke toestanden in alle submodellen; er zijn meer dan 200 van dergelijke toestanden in VEIL. Omdat het model volledig probabilistisch is, kan men voor een gegeven DNA-sequentie de waarschijnlijkheid van elke toestandssequentie berekenen. Deze toestandssequentie (een pad genoemd) bepaalt de toewijzing van exonen en intronen. Als het pad door het exon-model gaat, wordt dat deel van de sequentie als exon gelabeld; als het door het intron-model gaat, wordt het als intron gelabeld, enzovoort. Het dynamische programmeringsalgoritme, dat het Viterbi algoritme wordt genoemd, vindt het meest waarschijnlijke pad door het model voor een gegeven sequentie, en daaruit wordt de voorspelde genstructuur afgeleid (zie Rabiner (1989) voor een algemene inleiding tot HMM’s).
Dit probabilistische model heeft het voordeel dat het probleem van het wegen van de afzonderlijke sensoren wordt opgelost. Er kan worden aangetoond dat de maximale waarschijnlijkheidsschatting van de parameters optimaal is indien er voldoende trainingsgegevens zijn, en indien de statistische aard van de genen door een dergelijk model kan worden beschreven. Een zwak onderdeel van VEIL is het eerste-orde exon-model, dat waarschijnlijk niet in staat is de statistiek van coderende regio’s weer te geven, en de meeste andere methoden gebruiken vierde- of vijfde-orde modellen.
Een op HMM gebaseerde gen-finder, HMMgene genaamd, wordt momenteel ontwikkeld. De basismethode is dezelfde als VEIL, maar het bevat verschillende uitbreidingen op de standaard HMM-methodologie, die worden beschreven door Krogh (1997). Een van de belangrijkste is dat coderende regio’s worden gemodelleerd door een inhomogene Markov-keten van de vierde orde in plaats van een eerste-orde-keten. Dit wordt gedaan door een bijna triviale uitbreiding van het standaard HMM-formalisme, dat een Markov-keten van elke orde in een toestand van het model toestaat, terwijl de standaard HMM een eenvoudige onvoorwaardelijke kansverdeling over de vier bases heeft (overeenkomend met 0e orde). Het model is frame-bewust en kan een willekeurig aantal genen en partiële genen voorspellen, zodat de algemene structuur van het model is als in figuur 11.4 met toegevoegde overgangen om begin en einde in introns mogelijk te maken, zoals in figuur 11.3.
Zoals reeds vermeld, werkt de maximum likelihood schattingsmethode goed als de modelstructuur de ware statistiek van genen kan beschrijven. Dit is een zeer geïdealiseerde aanname, en daarom gebruikt HMMgene een andere methode voor het schatten van de parameters, genaamd conditionele maximale waarschijnlijkheid (Juang en Rabiner, 1991; Krogh, 1994). Grofweg maximaliseert de maximale waarschijnlijkheid de waarschijnlijkheid van de DNA-sequenties in de trainingsverzameling, terwijl de conditionele maximale waarschijnlijkheid de waarschijnlijkheid van de genstructuren van deze sequenties maximaliseert, hetgeen tenslotte is waarin wij geïnteresseerd zijn. Dit soort optimalisatie is conceptueel gelijk aan die welke wordt gebruikt in GeneParser, waar de nauwkeurigheid van de voorspelling ook wordt geoptimaliseerd. HMMgene gebruikt ook een dynamisch programmeringsalgoritme dat verschilt van het Viterbi algoritme voor de voorspelling van de genstructuur. Al deze methoden hebben bijgedragen tot een hoge prestatie van HMMgene.
Genie is een ander voorbeeld van een probabilistisch toestandsmodel dat een gegeneraliseerde HMM wordt genoemd (Kulp et al., 1996; Reese et al., 1997). Figuur 11.4 is in feite de toestandsstructuur van Genie, en zowel deze figuur als figuur 11.2 zijn in essentie overgenomen van Kulp et al. (1996). In Genie zijn de signaalsensoren (splice sites) en inhoudsensoren (coding potential) neurale netwerken, en de output van deze netwerken wordt geïnterpreteerd als waarschijnlijkheden. Deze interpretatie vereist een schatting van bijkomende waarschijnlijkheidsparameters die als gewichten op de sensoren werken. Hoewel het model dus is geformuleerd als een probabilistisch model, doet het probleem van de weging zich nog steeds vermomd voor. Het algoritme voor de voorspelling is vrijwel identiek aan het dynamisch programmeringsalgoritme van het laatste hoofdstuk. Een versie van Genie bevat ook database-overeenkomsten als onderdeel van de exon-sensor (Kulp et al., 1997).
Er zijn twee belangrijke voordelen van gegeneraliseerde HMM’s vergeleken met standaard HMM’s. Ten eerste kunnen de individuele sensoren van elk type zijn, zoals neurale netwerken, terwijl zij in een standaard HMM beperkt worden door het HMM raamwerk. Ten tweede kan expliciet rekening worden gehouden met de lengteverdeling (van bijvoorbeeld coderingsgebieden), terwijl de natuurlijke lengteverdeling voor een HMM een geometrische verdeling is, die exponentieel met de lengte afneemt. Het is echter mogelijk een vrij geavanceerde lengtemodellering in een HMM te hebben als verschillende toestanden worden gebruikt (Durbin et al., 1998). Het voordeel van een systeem als HMMgene daarentegen is dat het één geïntegreerd model is, dat in één keer kan worden geoptimaliseerd voor maximale nauwkeurigheid van de voorspelling.
Een andere gen-vinder gebaseerd op een gegeneraliseerde HMM is GENSCAN (Burge en Karlin, 1997). Het belangrijkste verschil tussen de GENSCAN-statusstructuur en die van Genie of HMMgene is dat GENSCAN de sequentie in beide richtingen tegelijk modelleert. In veel genenzoekers, zoals die welke hierboven zijn beschreven, worden genen eerst op één streng voorspeld, en daarna op de andere. Het gelijktijdig modelleren van beide strengen werd zeer succesvol gedaan in GeneMark, en een gelijkaardige methode is geïmplementeerd in GENSCAN. Een voordeel (en misschien wel het belangrijkste voordeel) is dat deze constructie voorkomt dat op de twee strengen overlappende genen worden voorspeld, wat in het menselijk genoom vermoedelijk zeer zeldzaam is. GENSCAN modelleert een willekeurig aantal genen en partiële genen zoals HMMgene. De sensoren in GENSCAN zijn vergelijkbaar met die welke in HMMgene worden gebruikt. De coderingssensor is bijvoorbeeld een inhomogene Markov-keten van de vijfde orde. De signaalsensoren zijn in wezen positie-afhankelijke gewichtsmatrices, en lijken dus ook sterk op die van HMMgene, maar er zijn meer geavanceerde functies in de splitsingsplaatsmodellen. GENSCAN modelleert ook promotors en de 5′ en 3′ UTRs.