3 ÁLLAPOTI MODELLEK
A predikciók teljes génszerkezetté történő kombinálásának lényege, hogy a “grammatikai” megkötések kizárhatnak néhány téves exon-összeállítást. A probléma nyelvtani szerkezetét David Searls hangsúlyozta (Searls, 1992; Dong és Searls, 1994), aki a formális nyelvtanok informatikai és nyelvészeti módszereinek alkalmazását is javasolta. A dinamikus programozás gyakran kényelmesen leírható valamilyen véges automatával (Searls és Murphy, 1995; Durbin et al., 1998). Egy modellnek lehet egy állapota a fordítás kezdetére (S), egy a donorhelyekre (D), egy az akceptorhelyekre (A) és egy a fordítás befejezésére (T). Minden egyes alkalommal, amikor az egyik állapotból egy másikba történő átmenet történik, egy pontszámot (vagy büntetést) adunk hozzá. A donor állapotból az akceptor állapotba való átmenet esetén az intron pontszámot hozzáadjuk az összpontszámhoz, és így tovább. A 11.2. ábrán a fenti egyszerű dinamikus programozási algoritmus állapotdiagramja látható. Az algoritmusban minden változóhoz tartozik egy azonos nevű állapot, és szükség van egy kezdő és egy végállapotra is.
11.2. ábra. Az egyszerű DP-algoritmusnak megfelelő véges állapotú automata.
Egy ilyen megfogalmazás előnye, hogy a maximális pontszám (vagy minimális büntetés) megtalálására szolgáló dinamikus programozás általánosabb típusú, ezért új állapotok vagy új átmenetek hozzáadása egyszerű. Például egy általánosabb dinamikus programozási algoritmus állapotdiagramjának megrajzolása, amely tetszőleges számú gént és részleges számú részleges gént is megenged, egyszerű (11.3. ábra), míg a leírása bonyolult. Hasonlóképpen a fentebb felvázolt, kerettudatos algoritmus állapotdiagramja a 11.4. ábrán látható.
11.3. ábra. A 11.2. ábra modellje átmenetekkel kiegészítve, amelyek lehetővé teszik tetszőleges számú gén és olyan részleges gének előrejelzését, ahol a szekvencia egy exon vagy intron közepén kezdődik vagy végződik.
A 11.4. ábra. Egy modell, amely biztosítja a keret konzisztenciáját az egész génben. Az előző két ábrához hasonlóan a szaggatott vonalak az intergenikus régióknak, a szaggatott az intronoknak, a teljes vonalak pedig a kódoló régióknak (exonoknak) felelnek meg.
Ha a használt pontszámok log valószínűségek vagy log esélyek, akkor egy véges állapotú automata lényegében egy rejtett Markov-modell (HMM), és ezeket az utóbbi időben több csoport is bevezette a génkeresésbe. Az egyetlen alapvető különbség a fent tárgyalt dinamikus programozási sémáktól az, hogy ezek a modellek teljesen valószínűségi alapúak, aminek bizonyos előnyei vannak. Az egyik előny az, hogy a súlyozási probléma könnyebbé válik.
A VEIL (Henderson et al., 1997) egy HMM alkalmazása a génkeresési problémára. Ebben a modellben minden szenzor HMM. Az exonmodul lényegében egy elsőrendű inhomogén Markov-lánc, amelyet fentebb ismertettünk. Ez a természetes sorrend a HMM-ben való megvalósításhoz, mert ekkor az inhomogén Markov-lánc minden egyes feltételes valószínűsége megfelel a HMM egyik állapotból a másikba való átmenet valószínűségének. Egy elsőrendű modell alkalmazásakor nem lehet elkerülni a stopkódonokat az olvasókeretben, de a VEIL-ben ügyes módon néhány további állapotot adunk hozzá, ami a stopkódonok valószínűségét nullává teszi. A splice-helyek érzékelése hasonló módon történik. Az egyes modulokat ezután lényegében a 11.2. ábrán látható módon kombináljuk (azaz a keretkonzisztencia nem érvényesül). A kombinált modell egy nagy HMM, és minden átmenethez valószínűség tartozik. Ezek a valószínűségek maximális valószínűségű módszerrel becsülhetők egy gyakorló adathalmazból. A modellek kombinálásához ez lényegében a különböző típusú átmenetek előfordulásának megszámlálását jelenti az adathalmazban. Ezért az egyes szenzorok implicit súlyozása nem igazán jelent problémát.
Noha az optimális génszerkezet megtalálásának módja szellemében hasonló a fenti dinamikus programozáshoz, a gyakorlatban egészen másképp néz ki. Ennek oka, hogy a dinamikus programozás az összes részmodellben az egyes állapotok szintjén történik; a VEIL-ben több mint 200 ilyen állapot van. Mivel a modell teljesen valószínűségi alapú, egy adott DNS-szekvencia esetén kiszámítható az állapotok bármelyik szekvenciájának valószínűsége. Ez az állapotsorozat (az úgynevezett útvonal) határozza meg az exonok és intronok hozzárendelését. Ha az útvonal áthalad az exon-modellen, akkor a szekvencia adott része exonként van jelölve; ha áthalad az intron-modellen, akkor intronként van jelölve, és így tovább. A dinamikus programozási algoritmus, amelyet Viterbi algoritmusnak nevezünk, egy adott szekvenciához megtalálja a modellen keresztül vezető legvalószínűbb utat, és ebből vezetjük le a megjósolt génszerkezetet (a HMM-ek általános bevezetését lásd Rabiner (1989)).
Ez a valószínűségi modell előnye, hogy megoldja az egyes szenzorok súlyozásának problémáját. A paraméterek maximális valószínűségű becslése optimálisnak bizonyulhat, ha elegendő gyakorló adat áll rendelkezésre, és ha a gének statisztikai jellege leírható egy ilyen modellel. A VEIL gyenge pontja az elsőrendű exonmodell, amely valószínűleg nem képes megragadni a kódoló régiók statisztikáját, és a legtöbb más módszer negyed- vagy ötödrendű modelleket használ.
A HMM-alapú génkereső HMMgene néven jelenleg fejlesztés alatt áll. Az alapmódszer ugyanaz, mint a VEIL, de a standard HMM-módszertanhoz képest számos bővítést tartalmaz, amelyeket Krogh (1997) ismertet. Az egyik legfontosabb az, hogy a kódoló régiókat egy negyedrendű inhomogén Markov-lánccal modellezik az elsőrendű lánc helyett. Ez a standard HMM formalizmus szinte triviális kiterjesztésével történik, amely lehetővé teszi, hogy a modell egy állapotában bármilyen rendű Markov-lánc szerepeljen, míg a standard HMM egyszerű, feltétel nélküli valószínűségeloszlással rendelkezik a négy bázis felett (ami a 0. rendnek felel meg). A modell keret-érzékeny, és tetszőleges számú gént és részleges számú gént képes megjósolni, így a modell általános szerkezete a 11.4. ábrán látható, azzal, hogy a 11.3. ábrának megfelelően átmeneteket adunk hozzá az intronokban való kezdet és vég figyelembevételére.
Amint már említettük, a maximum likelihood becslési módszer jól működik, ha a modellszerkezet képes leírni a gének valódi statisztikáját. Ez egy nagyon idealizált feltételezés, ezért a HMMgene egy másik módszert használ a paraméterek becslésére, amelyet feltételes maximális valószínűségnek nevezünk (Juang és Rabiner, 1991; Krogh, 1994). Lazán fogalmazva, a maximális valószínűség maximalizálja a tréningkészletben lévő DNS-szekvenciák valószínűségét, míg a feltételes maximális valószínűség maximalizálja e szekvenciák génszerkezetének valószínűségét, ami végül is minket érdekel. Ez a fajta optimalizálás koncepcionálisan hasonló a GeneParserben használt optimalizáláshoz, ahol szintén a predikció pontosságát optimalizálják. A HMMgene a Viterbi algoritmustól eltérő dinamikus programozási algoritmust is használ a génszerkezet előrejelzésére. Mindezek a módszerek hozzájárultak a HMMgene nagy teljesítményéhez.
A Genie egy másik példa a valószínűségi állapotmodellre, amelyet általánosított HMM-nek neveznek (Kulp et al., 1996; Reese et al., 1997). A 11.4. ábra tulajdonképpen a Genie állapotszerkezete, és mind ez az ábra, mind a 11.2. ábra lényegében Kulp et al. (1996) ábrájáról van átvéve. A Genie-ben a jelérzékelők (illesztési helyek) és a tartalomérzékelők (kódolási potenciál) neurális hálózatok, és e hálózatok kimenetét valószínűségként értelmezzük. Ez az értelmezés további valószínűségi paraméterek becslését igényli, amelyek úgy működnek, mint a szenzorok súlyai. Így, bár valószínűségi modellként van megfogalmazva, a súlyozási probléma mégis álruhában jelenik meg. Az előrejelzés algoritmusa szinte teljesen megegyezik az előző szakasz dinamikus programozási algoritmusával. A Genie egyik változata az exonszenzorok részeként adatbázis-hasonlóságokat is tartalmaz (Kulp et al., 1997).
Az általánosított HMM-eknek két fő előnye van a standard HMM-ekkel szemben. Először is, az egyes szenzorok bármilyen típusúak lehetnek, például neurális hálózatok, míg a standard HMM-ben a HMM keretrendszer korlátozza őket. Másodszor, a hosszeloszlást (például a kódoló régiók esetében) explicit módon figyelembe lehet venni, míg egy HMM esetében a természetes hosszeloszlás egy geometriai eloszlás, amely exponenciálisan csökken a hosszal. Ugyanakkor egy HMM-ben meglehetősen fejlett hosszmodellezésre van lehetőség, ha több állapotot használunk (Durbin et al., 1998). Ezzel szemben egy olyan rendszer, mint a HMMgene előnye, hogy egyetlen integrált modellről van szó, amelyet egyszerre lehet optimalizálni a maximális előrejelzési pontosság érdekében.
Egy másik általánosított HMM-en alapuló génkereső a GENSCAN (Burge és Karlin, 1997). A fő különbség a GENSCAN állapotszerkezete és a Genie vagy a HMMgene között az, hogy a GENSCAN egyszerre modellezi a szekvenciát mindkét irányban. Sok génkeresőben, mint például a fent leírtak, a géneket először az egyik szálon, majd a másik szálon jósolják meg. A két szál egyidejű modellezése a GeneMarkban nagyon sikeresen megvalósult, és a GENSCAN-ban is hasonló módszer van implementálva. Az egyik előny (és talán a legfontosabb) az, hogy ezzel a konstrukcióval elkerülhetők a két szálon átfedő gének előrejelzései, amelyek feltehetően nagyon ritkák az emberi genomban. A GENSCAN a HMMgene-hez hasonlóan tetszőleges számú gént és parciális gént modellez. A GENSCAN szenzorai hasonlóak a HMMgene-ben használtakhoz. Például a kódoló szenzor egy ötödrendű inhomogén Markov-lánc. A jelszenzorok lényegében pozíciófüggő súlymátrixok, és így szintén nagyon hasonlítanak a HMMgene szenzoraihoz, de a splice site modellekben fejlettebb jellemzők vannak. A GENSCAN modellezi a promótereket és az 5′ és 3′ UTR-t is.