3 TILAMALLIT
Ajatuksena ennusteiden yhdistämisessä täydelliseksi geenirakenteeksi on se, että ”kieliopilliset” rajoitteet voivat sulkea pois joitakin vääriä eksonikokoonpanoja. Ongelman kieliopillista rakennetta on korostanut David Searls (Searls, 1992; Dong ja Searls, 1994), joka on myös ehdottanut tietotekniikasta ja kielitieteestä peräisin olevien formaalien kielioppien menetelmien käyttöä. Dynaaminen ohjelmointi voidaan usein kuvata kätevästi jonkinlaisella äärellisen tilan automaatilla (Searls ja Murphy, 1995; Durbin et al., 1998). Mallissa voi olla tila käännöksen alkamiselle (S), tila luovutuspaikoille (D), tila akseptoripaikoille (A) ja tila käännöksen päättymiselle (T). Joka kerta, kun siirrytään tilasta toiseen, lisätään pisteet (tai rangaistus). Siirryttäessä luovuttajatilasta akseptoritilaan kokonaispistemäärään lisätään intronin pistemäärä ja niin edelleen. Kuvassa 11.2 on esitetty edellä esitetyn yksinkertaisen dynaamisen ohjelmointialgoritmin tilakaavio. Algoritmin jokaiselle muuttujalle on vastaava samanniminen tila, ja lisäksi tarvitaan alku- ja lopputila.
Kuvio 11.2. Alkutila. Yksinkertaista DP-algoritmia vastaava äärellinen automaatti.
Tällaisen muotoilun etuna on, että dynaaminen ohjelmointi maksimipistemäärän (tai pienimmän rangaistuksen) löytämiseksi on yleisempää tyyppiä, ja siksi uusien tilojen tai uusien siirtymien lisääminen on helppoa. Esimerkiksi yleisemmän dynaamisen ohjelmoinnin algoritmin, joka sallii minkä tahansa määrän geenejä ja myös osittaisia geenejä, tilakaavion piirtäminen on suoraviivaista (kuva 11.3), kun taas sen kirjoittaminen on hankalaa. Vastaavasti edellä hahmotellun kehykset huomioivan algoritmin tilakaavio on esitetty kuvassa 11.4.
Kuva 11.3. Algoritmin tilakaavio. Kuvan 11.2 malli, johon on lisätty siirtymät, joiden avulla voidaan ennustaa mikä tahansa määrä geenejä ja osittaisia geenejä, joissa sekvenssi alkaa tai päättyy eksonin tai intronin keskelle.
Kuva 11.4. Malli, jolla varmistetaan rungon yhdenmukaisuus koko geenissä. Kuten kahdessa edellisessä kuvassa, katkoviivat vastaavat intergeenisiä alueita, katkoviivat introneja ja kokoviivat koodaavia alueita (eksoneja).
Jos käytetyt pistemäärät ovat log-todennäköisyyksiä tai log-kertoimia, niin äärellinen automaatti on pohjimmiltaan piilevä Markovin malli (HMM, Hidden Markov Model), ja nämä ovat viime aikoina tulleet käyttöön geeninlöytämisessä useiden ryhmien toimesta. Ainoa perustavanlaatuinen ero edellä käsiteltyihin dynaamisiin ohjelmointimalleihin on se, että nämä mallit ovat täysin probabilistisia, millä on tiettyjä etuja. Yksi eduista on, että painotusongelma on helpompi.
VEIL (Henderson et al., 1997) on HMM:n sovellus geeninetsintäongelmaan. Tässä mallissa kaikki anturit ovat HMM:iä. Eksonimoduuli on pohjimmiltaan ensimmäisen kertaluvun inhomogeeninen Markovin ketju, joka on kuvattu edellä. Tämä on luonnollinen järjestys toteutettavaksi HMM:ssä, koska tällöin jokainen inhomogeenisen Markovin ketjun ehdollinen todennäköisyys vastaa todennäköisyyttä, jolla HMM:ssä siirrytään tilasta toiseen. Ensimmäisen järjestyksen mallia käytettäessä ei ole mahdollista välttää stop-kodoneja lukukehyksessä, mutta VEIL:ssä lisätään fiksulla tavalla muutama tila lisää, jolloin stop-kodonin todennäköisyys on nolla. Liitoskohtien tunnistimet tehdään vastaavalla tavalla. Yksittäiset moduulit yhdistetään sitten periaatteessa kuten kuvassa 11.2 (eli kehyksen johdonmukaisuutta ei ole pakotettu). Yhdistetty malli on yksi suuri HMM, ja kaikkiin siirtymiin liittyy todennäköisyyksiä. Nämä todennäköisyydet voidaan arvioida harjoitteluaineistosta maksimaalisen todennäköisyyden menetelmällä. Mallien yhdistämisessä tämä tarkoittaa lähinnä sitä, että lasketaan erityyppisten siirtymien esiintymiset tietokannassa. Siksi yksittäisten antureiden implisiittinen painotus ei oikeastaan ole ongelma.
Vaikka tapa, jolla optimaalinen geenirakenne löydetään, on hengeltään samankaltainen kuin edellä esitetyssä dynaamisessa ohjelmoinnissa, se näyttää käytännössä aivan erilaiselta. Tämä johtuu siitä, että dynaaminen ohjelmointi tehdään kaikkien alamallien yksittäisten tilojen tasolla; VEILissä on yli 200 tällaista tilaa. Koska malli on täysin probabilistinen, voidaan laskea minkä tahansa tilasarjan todennäköisyys tietylle DNA-sekvenssille. Tämä tilasekvenssi (jota kutsutaan poluksi) määrittää eksonien ja intronien sijoittumisen. Jos polku kulkee eksonimallin läpi, kyseinen sekvenssin osa merkitään eksoniksi; jos se kulkee intronimallin läpi, se merkitään introniksi ja niin edelleen. Dynaaminen ohjelmointialgoritmi, jota kutsutaan Viterbi-algoritmiksi, löytää tietylle sekvenssille todennäköisimmän polun mallin läpi, ja siitä johdetaan ennustettu geenirakenne (ks. Rabiner (1989), jossa on yleinen johdatus HMM:iin).
Tämän todennäköisyysmallin etuna on se, että se ratkaisee ongelman yksittäisten anturien painottamisesta. Parametrien suurimman todennäköisyyden estimoinnin voidaan osoittaa olevan optimaalinen, jos harjoitusdataa on riittävästi ja jos geenien tilastollinen luonne voidaan kuvata tällaisella mallilla. VEILin heikko osa on ensimmäisen kertaluvun eksonimalli, joka ei todennäköisesti kykene kuvaamaan koodaavien alueiden tilastoja, ja useimmat muut menetelmät käyttävät neljännen tai viidennen kertaluvun malleja.
HMM-pohjaista geeninetsintäohjelmaa nimeltä HMMgene kehitetään parhaillaan. Perusmenetelmä on sama kuin VEIL, mutta se sisältää useita laajennuksia standardiin HMM-menetelmään, jotka on kuvattu Kroghissa (1997). Yksi tärkeimmistä on se, että koodaavia alueita mallinnetaan neljännen kertaluvun inhomogeenisella Markovin ketjulla ensimmäisen kertaluvun ketjun sijasta. Tämä tehdään lähes triviaalilla laajennuksella tavalliseen HMM-formalismiin, joka sallii minkä tahansa järjestyksen Markov-ketjun mallin tilassa, kun taas tavallisessa HMM:ssä on yksinkertainen ehdoton todennäköisyysjakauma neljälle perustalle (mikä vastaa 0. järjestystä). Malli on kehystietoinen ja voi ennustaa minkä tahansa määrän geenejä ja osittaisia geenejä, joten mallin kokonaisrakenne on kuvan 11.4 mukainen, ja siihen on lisätty siirtymiä intronien alkamisen ja päättymisen sallimiseksi, kuten kuvassa 11.3.
Kuten jo mainittiin, maksimaalisen likelihoodin estimointimenetelmä toimii hyvin, jos mallin rakenne voi kuvata geenien todellisia tilastoja. Tämä on hyvin idealisoitu oletus, ja siksi HMMgene käyttää parametrien estimointiin toista menetelmää, jota kutsutaan nimellä conditional maximum likelihood (Juang ja Rabiner, 1991; Krogh, 1994). Löyhästi sanottuna maksimiluotettavuus maksimoi harjoitusjoukon DNA-sekvenssien todennäköisyyden, kun taas ehdollinen maksimiluotettavuus maksimoi näiden sekvenssien geenirakenteiden todennäköisyyden, joka loppujen lopuksi on se, mistä olemme kiinnostuneita. Tällainen optimointi on käsitteellisesti samanlainen kuin GeneParserissa käytetty optimointi, jossa optimoidaan myös ennustustarkkuutta. HMMgene käyttää myös Viterbi-algoritmista poikkeavaa dynaamisen ohjelmoinnin algoritmia geenirakenteen ennustamiseen. Kaikki nämä menetelmät ovat vaikuttaneet HMMgenen korkeaan suorituskykyyn.
Genie on toinen esimerkki probabilistisesta tilamallista, jota kutsutaan yleistetyksi HMM:ksi (Kulp et al., 1996; Reese et al., 1997). Kuva 11.4 on itse asiassa Genien tilarakenne, ja sekä tämä kuva että kuva 11.2 on pääosin kopioitu Kulp et al. (1996):sta. Geniessä signaalianturit (liitospaikat) ja sisältöanturit (koodauspotentiaali) ovat neuroverkkoja, ja näiden verkkojen tuotos tulkitaan todennäköisyyksinä. Tämä tulkinta edellyttää lisätodennäköisyysparametrien estimointia, jotka toimivat antureiden painojen tavoin. Vaikka malli on siis muotoiltu todennäköisyysmallina, painotusongelma esiintyy silti naamioituneena. Ennustamiseen käytettävä algoritmi on lähes identtinen edellisen jakson dynaamisen ohjelmoinnin algoritmin kanssa. Eräs Genie-versio sisältää myös tietokannan samankaltaisuudet osana eksonianturia (Kulp et al., 1997).
Yleistetyillä HMM-malleilla on kaksi pääetua verrattuna tavallisiin HMM-malleihin. Ensinnäkin yksittäiset anturit voivat olla minkä tahansa tyyppisiä, kuten neuroverkkoja, kun taas tavallisessa HMM:ssä niitä rajoittaa HMM-kehys. Toiseksi pituusjakauma (esimerkiksi koodausalueiden) voidaan ottaa eksplisiittisesti huomioon, kun taas HMM:n luonnollinen pituusjakauma on geometrinen jakauma, joka hajoaa eksponentiaalisesti pituuden myötä. HMM:ssä on kuitenkin mahdollista saada melko pitkälle menevä pituuden mallinnus, jos käytetään useita tiloja (Durbin et al., 1998). HMMgenen kaltaisen järjestelmän etuna on toisaalta se, että se on yksi integroitu malli, joka voidaan optimoida kerralla maksimaalisen ennustustarkkuuden saavuttamiseksi.
Toinen yleistettyyn HMM:ään perustuva geeninetsintäohjelma on GENSCAN (Burge ja Karlin, 1997). Tärkeimmät erot GENSCANin tilarakenteen ja Genien tai HMMgenen välillä ovat siinä, että GENSCAN mallintaa sekvenssiä molempiin suuntiin samanaikaisesti. Monissa geenejä etsivissä ohjelmissa, kuten edellä kuvatuissa, geenit ennustetaan ensin toiselta puolelta ja sitten toiselta puolelta. Molempien säikeiden samanaikainen mallintaminen onnistui hyvin GeneMarkissa, ja samanlainen menetelmä on toteutettu GENSCANissa. Yksi (ja ehkä tärkein) etu on se, että tällä rakenteella vältetään päällekkäisten geenien ennustaminen molemmilla säikeillä, mikä oletettavasti on hyvin harvinaista ihmisen genomissa. GENSCAN mallintaa minkä tahansa määrän geenejä ja osittaisia geenejä kuten HMMgene. GENSCANin anturit ovat samanlaisia kuin HMMgenessä käytetyt. Esimerkiksi koodausanturi on viidennen kertaluvun inhomogeeninen Markovin ketju. Signaalisensorit ovat lähinnä sijainnista riippuvaisia painomatriiseja ja siten myös hyvin samankaltaisia kuin HMMgenessä, mutta liitospaikkamalleissa on kehittyneempiä ominaisuuksia. GENSCAN mallintaa myös promoottoreita sekä 5′ ja 3′ UTR:ää.