Alai

3 STAVOVÉ MODELY

Použije-li se skóre logaritmických pravděpodobností nebo logaritmických šancí, pak je konečný stavový automat v podstatě skrytým Markovovým modelem (HMM) a ty byly nedávno několika skupinami zavedeny do vyhledávání genů. Jediný zásadní rozdíl oproti výše uvedeným schématům dynamického programování spočívá v tom, že tyto modely jsou plně pravděpodobnostní, což má určité výhody. Jednou z výhod je, že problém vážení je jednodušší.

VEIL (Henderson a kol., 1997) je aplikací HMM na problém hledání genů. V tomto modelu jsou všechny senzory HMM. Exonový modul je v podstatě nehomogenní Markovův řetězec prvního řádu, který je popsán výše. To je přirozený řád pro implementaci v HMM, protože pak každá z podmíněných pravděpodobností nehomogenního Markovova řetězce odpovídá pravděpodobnosti přechodu z jednoho stavu do druhého v HMM. Při použití modelu prvního řádu se nelze vyhnout stop kodonům ve čtecím rámci, ale ve VEIL je chytrým způsobem přidáno několik dalších stavů, díky čemuž je pravděpodobnost stop kodonu nulová. Podobným způsobem jsou vytvořeny senzory pro místa sestřihu. Jednotlivé moduly se pak kombinují v podstatě jako na obrázku 11.2 (tj. konzistence rámce není vynucena). Kombinovaný model je jeden velký HMM a všechny přechody mají přiřazené pravděpodobnosti. Tyto pravděpodobnosti lze odhadnout ze souboru trénovacích dat metodou maximální věrohodnosti. Pro kombinování modelů se to v podstatě omezuje na počítání výskytů různých typů přechodů v souboru dat. Proto implicitní vážení jednotlivých snímačů není ve skutečnosti problémem.

Ačkoli způsob nalezení optimální genové struktury je v duchu podobný výše uvedenému dynamickému programování, v praxi vypadá zcela jinak. Je to proto, že dynamické programování se provádí na úrovni jednotlivých stavů ve všech dílčích modelech; takových stavů je ve VEILu více než dvě stě. Protože je model plně pravděpodobnostní, lze pro danou sekvenci DNA vypočítat pravděpodobnost libovolné posloupnosti stavů. Tato posloupnost stavů (nazývaná cesta) určuje přiřazení exonů a intronů. Pokud cesta prochází modelem exonu, je tato část sekvence označena jako exon; pokud prochází modelem intronu, je označena jako intron atd. Algoritmus dynamického programování, který se nazývá Viterbiho algoritmus, najde pro danou sekvenci nejpravděpodobnější cestu modelem a z ní se odvodí předpovězená struktura genu (obecný úvod do HMM viz Rabiner (1989)).

Tento pravděpodobnostní model má tu výhodu, že řeší problém vážení jednotlivých senzorů. Odhad parametrů metodou maximální věrohodnosti se může ukázat jako optimální, pokud existuje dostatek trénovacích dat a pokud lze statistickou povahu genů popsat takovým modelem. Slabou součástí VEIL je model exonů prvního řádu, který pravděpodobně není schopen zachytit statistiku kódujících oblastí, a většina ostatních metod používá modely čtvrtého nebo pátého řádu.

V současné době se vyvíjí vyhledávač genů založený na HMM s názvem HMMgene. Základní metoda je stejná jako VEIL, ale obsahuje několik rozšíření standardní metodiky HMM, které popisuje Krogh (1997). Jedním z nejdůležitějších je, že kódující oblasti jsou modelovány nehomogenním Markovovým řetězcem čtvrtého řádu namísto řetězce prvního řádu. To se provádí téměř triviálním rozšířením standardního formalismu HMM, které umožňuje ve stavu modelu Markovův řetězec libovolného řádu, zatímco standardní HMM má jednoduché nepodmíněné rozdělení pravděpodobnosti nad čtyřmi bázemi (odpovídající 0. řádu). Model si uvědomuje rámec a může předpovídat libovolný počet genů a částečných genů, takže celková struktura modelu je jako na obrázku 11.4 s přidanými přechody umožňujícími začátek a konec v intronech, jako na obrázku 11.3.

Jak již bylo zmíněno, metoda odhadu maximální věrohodnosti funguje dobře, pokud struktura modelu může popisovat skutečnou statistiku genů. To je velmi idealizovaný předpoklad, a proto HMMgene používá jinou metodu odhadu parametrů zvanou podmíněná maximální věrohodnost (Juang a Rabiner, 1991; Krogh, 1994). Volně řečeno, maximální věrohodnost maximalizuje pravděpodobnost sekvencí DNA v trénovací množině, zatímco podmíněná maximální věrohodnost maximalizuje pravděpodobnost genových struktur těchto sekvencí, což je koneckonců to, co nás zajímá. Tento druh optimalizace je koncepčně podobný optimalizaci používané v programu GeneParser, kde se rovněž optimalizuje přesnost predikce. HMMgene používá pro predikci struktury genu také algoritmus dynamického programování, který se liší od Viterbiho algoritmu. Všechny tyto metody přispěly k vysoké výkonnosti HMMgene.

Genie je dalším příkladem pravděpodobnostního stavového modelu, který se nazývá zobecněný HMM (Kulp a kol., 1996; Reese a kol., 1997). Obrázek 11.4 je ve skutečnosti stavová struktura Genie a jak tento obrázek, tak obrázek 11.2 jsou v podstatě okopírovány z Kulp et al. (1996). V Genie jsou senzory signálu (místa spoje) a senzory obsahu (kódovací potenciál) neuronové sítě a výstup těchto sítí je interpretován jako pravděpodobnosti. Tato interpretace vyžaduje odhad dalších pravděpodobnostních parametrů, které fungují jako váhy senzorů. Ačkoli je tedy model formulován jako pravděpodobnostní, problém vážení se stále objevuje v převleku. Algoritmus pro predikci je téměř totožný s algoritmem dynamického programování z minulého oddílu. Verze Genie zahrnuje také databázové podobnosti jako součást exonového senzoru (Kulp a kol., 1997).

Ve srovnání se standardními HMM existují dvě hlavní výhody zobecněných HMM. Za prvé, jednotlivé senzory mohou být libovolného typu, například neuronové sítě, zatímco ve standardním HMM jsou omezeny rámcem HMM. Za druhé lze explicitně zohlednit rozdělení délek (například kódovacích oblastí), zatímco přirozené rozdělení délek pro HMM je geometrické rozdělení, které s délkou exponenciálně klesá. V HMM je však možné mít poměrně pokročilé modelování délky, pokud se použije několik stavů (Durbin et al., 1998). Výhodou systému, jako je HMMgene, je naopak to, že se jedná o jeden integrovaný model, který lze optimalizovat celý najednou pro maximální přesnost předpovědi.

Dalším vyhledávačem genů založeným na zobecněném HMM je GENSCAN (Burge a Karlin, 1997). Hlavní rozdíly mezi stavovou strukturou GENSCAN a Genie nebo HMMgene spočívají v tom, že GENSCAN modeluje sekvenci v obou směrech současně. V mnoha vyhledávačích genů, jako jsou ty popsané výše, jsou geny nejprve předpovídány v jednom směru a poté v druhém. Modelování obou vláken současně bylo velmi úspěšně provedeno v programu GeneMark a podobná metoda je implementována v programu GENSCAN. Jednou z výhod (a možná tou hlavní) je, že tato konstrukce zabraňuje predikcím překrývajících se genů na obou vláknech, které jsou pravděpodobně v lidském genomu velmi vzácné. GENSCAN modeluje libovolný počet genů a částečných genů podobně jako HMMgene. Senzory v GENSCAN jsou podobné těm, které se používají v HMMgene. Například senzorem kódování je nehomogenní Markovův řetězec pátého řádu. Signální senzory jsou v podstatě váhové matice závislé na poloze, a jsou tedy také velmi podobné těm v HMMgene, ale v modelech míst sestřihu jsou pokročilejší funkce. GENSCAN také modeluje promotory a 5′ a 3′ UTR

.