Alai

3 MODELE DE STAT

Figura 11.2. Un automat cu stări finite corespunzător algoritmului DP simplu.

Figura 11.3. Diagrama de stări pentru algoritmul de cunoaștere a cadrelor schițat mai sus. Modelul din figura 11.2 cu tranziții adăugate care permit predicția oricărui număr de gene și a genelor parțiale în care secvența începe sau se termină în mijlocul unui exon sau intron.

Figura 11.4. Un model care asigură consecvența cadrului pe parcursul unei gene. Ca și în cele două figuri anterioare, liniile punctate corespund regiunilor intergenice, cele punctate intronilor și cele întregi regiunilor codificatoare (exoni).

Dacă scorurile utilizate sunt probabilități logaritmice sau cote logaritmice, atunci un automat cu stări finite este, în esență, un model Markov ascuns (HMM), iar acestea au fost introduse recent în găsirea genelor de mai multe grupuri. Singura diferență fundamentală față de schemele de programare dinamică discutate mai sus este că aceste modele sunt complet probabilistice, ceea ce are anumite avantaje. Unul dintre avantaje este că problema ponderării este mai ușoară.

VEIL (Henderson et al., 1997) este o aplicație a unui HMM la problema găsirii de gene. În acest model, toți senzorii sunt HMM-uri. Modulul exonului este, în esență, un lanț Markov neomogen de ordinul întâi, care este descris mai sus. Aceasta este ordinea naturală pentru implementarea într-un HMM, deoarece atunci fiecare dintre probabilitățile condiționate ale lanțului Markov neomogen corespunde probabilității unei tranziții de la o stare la alta în HMM. Nu este posibil să se evite codonii de oprire în cadrul de citire atunci când se utilizează un model de ordinul întâi, dar în VEIL se adaugă câteva stări în plus într-un mod inteligent, ceea ce face ca probabilitatea unui codon de oprire să fie zero. Senzorii pentru situsurile de îmbinare sunt realizați într-un mod similar. Modulele individuale sunt apoi combinate în esență ca în figura 11.2 (adică nu este impusă coerența cadrului). Modelul combinat este un mare HMM, iar toate tranzițiile au probabilități asociate. Aceste probabilități pot fi estimate dintr-un set de date de antrenament printr-o metodă de maximă verosimilitate. Pentru combinarea modelelor, acest lucru se rezumă, în esență, la numărarea aparițiilor diferitelor tipuri de tranziții în setul de date. Prin urmare, ponderarea implicită a senzorilor individuali nu este cu adevărat o problemă.

Deși modul în care se găsește structura optimă a genei este similar în spirit cu programarea dinamică de mai sus, în practică arată destul de diferit. Acest lucru se datorează faptului că programarea dinamică se face la nivelul stărilor individuale din toate submodelele; există mai mult de 200 de astfel de stări în VEIL. Deoarece modelul este complet probabilistic, se poate calcula probabilitatea oricărei secvențe de stări pentru o anumită secvență de ADN. Această secvență de stări (numită cale) determină atribuirea de exoni și introni. Dacă traiectoria trece prin modelul exonului, acea parte a secvenței este etichetată ca exon; dacă trece prin modelul intronului, este etichetată ca intron, și așa mai departe. Algoritmul de programare dinamică, care se numește algoritmul Viterbi, găsește calea cea mai probabilă prin model pentru o secvență dată, iar din aceasta se derivă structura genei prezise (a se vedea Rabiner (1989) pentru o introducere generală în HMM-uri).

Acest model probabilistic are avantajul de a rezolva problema ponderării senzorilor individuali. Se poate demonstra că estimarea de maximă verosimilitate a parametrilor este optimă dacă există suficiente date de antrenament și dacă natura statistică a genelor poate fi descrisă de un astfel de model. O parte slabă a VEIL este modelul exonului de ordinul întâi, care probabil nu este capabil să capteze statisticile regiunilor de codificare, iar majoritatea celorlalte metode folosesc modele de ordinul patru sau cinci.

În prezent se dezvoltă un detector de gene bazat pe HMM numit HMMgene. Metoda de bază este aceeași cu VEIL, dar include mai multe extensii la metodologia HMM standard, care sunt descrise de Krogh (1997). Una dintre cele mai importante constă în faptul că regiunile de codificare sunt modelate printr-un lanț Markov neomogen de ordinul patru, în loc de un lanț de ordinul unu. Acest lucru este realizat printr-o extensie aproape trivială a formalismului HMM standard, care permite un lanț Markov de orice ordin într-o stare a modelului, în timp ce HMM standard are o simplă distribuție de probabilitate necondiționată pe cele patru baze (corespunzătoare ordinului 0). Modelul este sensibil la cadre și poate prezice orice număr de gene și gene parțiale, astfel încât structura generală a modelului este cea din figura 11.4, cu tranziții adăugate pentru a permite începutul și sfârșitul în introni, ca în figura 11.3.

După cum s-a menționat deja, metoda de estimare de maximă verosimilitate funcționează bine dacă structura modelului poate descrie adevărata statistică a genelor. Aceasta este o ipoteză foarte idealizată și, prin urmare, HMMgene utilizează o altă metodă de estimare a parametrilor, numită maximum de verosimilitate condiționată (Juang și Rabiner, 1991; Krogh, 1994). În sens larg, probabilitatea maximă maximală maximizează probabilitatea secvențelor de ADN din setul de instruire, în timp ce probabilitatea maximă condiționată maximizează probabilitatea structurilor genetice ale acestor secvențe, care, la urma urmei, este ceea ce ne interesează. Acest tip de optimizare este similar, din punct de vedere conceptual, cu cel utilizat în GeneParser, unde este optimizată și acuratețea predicției. HMMgene utilizează, de asemenea, un algoritm de programare dinamică diferit de algoritmul Viterbi pentru predicția structurii genetice. Toate aceste metode au contribuit la o performanță ridicată a HMMgene.

Genie este un alt exemplu de model probabilistic de stare care se numește HMM generalizat (Kulp et al., 1996; Reese et al., 1997). Figura 11.4 este, de fapt, structura de stare a lui Genie, iar atât această figură, cât și figura 11.2 sunt în esență copiate din Kulp et al. (1996). În Genie, senzorii de semnal (locurile de îmbinare) și senzorii de conținut (potențialul de codificare) sunt rețele neuronale, iar ieșirea acestor rețele este interpretată ca probabilități. Această interpretare necesită estimarea unor parametri de probabilitate suplimentari care funcționează ca niște ponderi pe senzori. Astfel, deși este formulat ca un model probabilistic, problema ponderării apare totuși deghizată. Algoritmul de predicție este aproape identic cu algoritmul de programare dinamică din ultima secțiune. O versiune a Genie include, de asemenea, similitudinile bazei de date ca parte a senzorului de exon (Kulp et al., 1997).

Există două avantaje principale ale HMM-urilor generalizate în comparație cu HMM-urile standard. În primul rând, senzorii individuali pot fi de orice tip, cum ar fi rețelele neuronale, în timp ce într-un HMM standard aceștia sunt restricționați de cadrul HMM. În al doilea rând, distribuția lungimii (de exemplu, a regiunilor de codare) poate fi luată în considerare în mod explicit, în timp ce distribuția naturală a lungimii pentru un HMM este o distribuție geometrică, care scade exponențial odată cu lungimea. Cu toate acestea, este posibilă o modelare destul de avansată a lungimii într-un HMM dacă se utilizează mai multe stări (Durbin et al., 1998). Avantajul unui sistem ca HMMgene, pe de altă parte, este că este un singur model integrat, care poate fi optimizat dintr-o dată pentru o precizie maximă a predicției.

Un alt instrument de găsire a genelor bazat pe un HMM generalizat este GENSCAN (Burge și Karlin, 1997). Principalele diferențe între structura de stare a GENSCAN și cea a Genie sau HMMgene este că GENSCAN modelează secvența în ambele direcții simultan. În multe dispozitive de căutare a genelor, cum ar fi cele descrise mai sus, genele sunt mai întâi prezise pe o filieră și apoi pe cealaltă. Modelarea simultană a ambelor șiruri a fost realizată cu mare succes în GeneMark, iar o metodă similară este implementată în GENSCAN. Un avantaj (și poate cel mai important) este că această construcție evită prezicerile de gene suprapuse pe cele două componente, care se presupune că sunt foarte rare în genomul uman. GENSCAN modelează orice număr de gene și gene parțiale, la fel ca HMMgene. Senzorii din GENSCAN sunt similari cu cei utilizați în HMMgene. De exemplu, senzorul de codificare este un lanț Markov neomogen de ordinul cinci. Senzorii de semnal sunt, în esență, matrici de ponderare dependente de poziție și, prin urmare, sunt, de asemenea, foarte asemănători cu cei din HMMgene, dar există caracteristici mai avansate în modelele situsurilor de îmbinare. GENSCAN modelează, de asemenea, promotori și UTR-urile 5′ și 3′.

.