Pravděpodobnostní bezkontextová gramatika - Probabilistic context-free grammar

Gramatická teorie k modelování řetězců symbolů pochází z práce ve výpočetní lingvistice, jejímž cílem je porozumět struktuře přirozených jazyků . Pravděpodobnostní kontextové gramatiky ( PCFGs ) byly použity pravděpodobnostní modelování z RNA struktur téměř 40 let poté, co byly zavedeny v počítačové lingvistice .

PCFG rozšiřují bezkontextové gramatiky podobně jako skryté Markovovy modely rozšiřují běžné gramatiky . Každé produkci je přiřazena pravděpodobnost. Pravděpodobnost derivace (analýza) je součinem pravděpodobností produkcí použitých při této derivaci. Tyto pravděpodobnosti lze zobrazit jako parametry modelu a pro velké problémy je vhodné se tyto parametry naučit pomocí strojového učení . Platnost pravděpodobnostní gramatiky je omezena kontextem její tréninkové datové sady.

PCFG mají uplatnění v tak rozmanitých oblastech, jako je zpracování přirozeného jazyka, ke studiu struktury molekul RNA a designu programovacích jazyků . Navrhování efektivních PCFG musí vážit faktory škálovatelnosti a obecnosti. Je třeba vyřešit problémy, jako je nejednoznačnost gramatiky. Gramatický design ovlivňuje přesnost výsledků. Algoritmy analýzy gramatiky mají různé časové a paměťové požadavky.

Definice

Odvození: Proces rekurzivního generování řetězců z gramatiky.

Analýza : Nalezení platné derivace pomocí automatu.

Analyzovat strom: Zarovnání gramatiky na sekvenci.

Příkladem analyzátoru pro PCFG gramatiky je pushdown automat . Algoritmus analyzuje gramatické neterminály zleva doprava způsobem podobným hromadě . Tento přístup hrubou silou není příliš účinný. V RNA predikci sekundární struktury varianty Cocke – Younger – Kasami (CYK) algoritmu poskytují efektivnější alternativy k gramatické analýze než pushdown automaty. Dalším příkladem analyzátoru PCFG je Stanford Statistical Parser, který byl vyškolen pomocí Treebank .

Formální definice

Podobně jako u CFG lze pravděpodobnostní bezkontextovou gramatiku $G$ definovat pětinásobkem:

{\ Displaystyle G = (M, T, R, S, P)}

kde

$M$ je sada neterminálních symbolů
$T$ je sada symbolů terminálu
$R$ je sada pravidel produkce
$S$ je počáteční symbol
$P$ je množina pravděpodobností výrobních pravidel

Vztah se skrytými Markovovými modely

Modely PCFG rozšiřují bezkontextové gramatiky stejným způsobem jako skryté Markovovy modely rozšiřují běžné gramatiky .

Algoritmus inside-outside je analog vpřed nebo vzad algoritmu . Vypočítává celkovou pravděpodobnost všech derivací, které jsou v souladu s danou sekvencí, na základě nějakého PCFG. To je ekvivalentní pravděpodobnosti, že PCFG generuje sekvenci, a je intuitivně měřítkem toho, jak je sekvence v souladu s danou gramatikou. Algoritmus Inside-Outside se používá v parametrizaci modelu k odhadu předchozích frekvencí pozorovaných z tréninkových sekvencí v případě RNA.

Varianty dynamického programování algoritmu CYK nacházejí Viterbiho analýzu sekvence RNA pro model PCFG. Tato analýza je nejpravděpodobnějším odvozením sekvence daným PCFG.

Konstrukce gramatiky

Gramatiky bez kontextu jsou reprezentovány jako soubor pravidel inspirovaných pokusy modelovat přirozené jazyky. Pravidla jsou absolutní a mají typickou reprezentaci syntaxe známou jako forma Backus – Naur . Produkční pravidla se skládají z koncových a neterminálních symbolů $S$ a jako koncový bod lze také použít mezeru. V produkčních pravidlech CFG a PCFG má levá strana pouze jeden neterminál, zatímco na pravé straně může být libovolný řetězec terminálu nebo neterminálů. V PCFG jsou nuly vyloučeny. Příklad gramatiky: ${\ displaystyle \ left \ {a, b \ right \}}$ ${\ Displaystyle \ epsilon}$

{\ Displaystyle S \ to aS, S \ to bS, S \ to \ epsilon}

Tuto gramatiku lze zkrátit pomocí '|' ('nebo') znak do:

{\ Displaystyle S \ to aS | bS | \ epsilon}

Terminály v gramatice jsou slova a prostřednictvím gramatických pravidel je neterminální symbol transformován do řetězce buď terminálů, nebo neterminálů. Výše uvedená gramatika se čte jako „počínaje neterminálním $S,$ emise může generovat buď $a$ nebo $b$ nebo “. Jeho odvození je: ${\ Displaystyle \ epsilon}$

{\ Displaystyle S \ Rightarrow aS \ Rightarrow abS \ Rightarrow abbS \ Rightarrow abb}

Nejednoznačná gramatika může mít za následek nejednoznačnou analýzu, pokud je použita na homografech, protože stejná sekvence slov může mít více než jednu interpretaci. Trestní věty jako novinový titulek „Irácká hlava hledá zbraně“ jsou příkladem nejednoznačných analýz.

Jednou ze strategií řešení nejednoznačných analýz (pocházejících z gramatiků již od Pāṇiniho ) je přidat ještě další pravidla nebo je upřednostnit tak, aby jedno pravidlo mělo přednost před ostatními. To má však nevýhodu v šíření pravidel, často až do bodu, kdy je obtížné je spravovat. Další obtíž je nadgenerace, kde se generují také nelicencované struktury.

Pravděpodobnostní gramatiky tyto problémy obcházejí zařazením různých produkcí na frekvenční váhy, což má za následek „nejpravděpodobnější“ (vítěz bere vše) interpretaci. Jelikož se vzorce používání mění v diachronních směnách, lze se tato pravděpodobnostní pravidla znovu naučit a aktualizovat tak gramatiku.

Přiřazení pravděpodobnosti produkčním pravidlům vytvoří PCFG. Tyto pravděpodobnosti jsou informovány pozorováním distribucí na tréninkové sadě podobného složení jako jazyk, který má být modelován. Ve většině vzorků širokého jazyka pravděpodobnostní gramatiky, kde jsou pravděpodobnosti odhadovány z dat, obvykle převyšují ručně vytvořené gramatiky. CFG, když jsou v kontrastu s PCFG, nejsou použitelné pro predikci struktury RNA, protože zatímco obsahují vztah mezi sekvencí a strukturou, chybí jim skórovací metriky, které odhalují strukturální potenciál sekvence

Vážená bezkontextová gramatika

Vážený kontext gramatika ( WCFG ) je obecnější kategorie kontextové gramatiky , kde má každá výrobní číselnou váhu s ním spojené. Váha konkrétního stromu analýzy v WCFG je součinem (nebo součtem) všech vah pravidel ve stromu. Každá váha pravidla je zahrnuta tak často, jak je pravidlo ve stromu použito. Zvláštním případem WCFG jsou PCFG, kde váhy jsou ( logaritmy ) pravděpodobností .

Rozšířenou verzi algoritmu CYK lze použít k nalezení „nejlehčí“ (nejmenší) derivace řetězce s určitým WCFG.

Když je hmotnost stromu součinem závaží pravidel, WCFG a PCFG mohou vyjadřovat stejnou sadu rozdělení pravděpodobnosti .

Aplikace

Predikce struktury RNA

Minimalizace energie a PCFG poskytují způsoby predikce sekundární struktury RNA se srovnatelným výkonem. Predikce struktury pomocí PCFG je však hodnocena spíše pravděpodobnostně než pomocí výpočtu minimální volné energie. Parametry modelu PCFG jsou přímo odvozeny z frekvencí různých znaků pozorovaných v databázích struktur RNA, nikoli experimentálním určováním, jako je tomu u metod minimalizace energie.

Typy různých struktur, které lze modelovat pomocí PCFG, zahrnují interakce s dlouhým dosahem, párovou strukturu a další vnořené struktury. Pseudoknoty však nelze modelovat. PCFG rozšiřují CFG přiřazováním pravděpodobností každému produkčnímu pravidlu. Strom analýzy maximální pravděpodobnosti z gramatiky implikuje strukturu maximální pravděpodobnosti. Protože RNA zachovávají své struktury přes svou primární sekvenci; Predikci struktury RNA lze řídit kombinací evolučních informací ze srovnávací sekvenční analýzy s biofyzikálními znalostmi o věrohodnosti struktury na základě těchto pravděpodobností. Výsledky vyhledávání strukturálních homologů pomocí pravidel PCFG jsou také hodnoceny podle pravděpodobností derivací PCFG. Budování gramatiky pro modelování chování párů bází a jednovláknových oblastí tedy začíná zkoumáním rysů strukturálního uspořádání více sekvencí souvisejících RNA.

{\ Displaystyle S \ to aSa | bSb | aa | bb}

Výše uvedená gramatika generuje řetězec způsobem zvenčí, to znamená, že se nejprve odvodí základní pár na nejvzdálenějších extrémech terminálu. Takže řetězec, který je odvozen nejprve generováním distálních $a$ na obou stranách, než se pohne dovnitř: ${\ Displaystyle aabaabaa}$

{\ Displaystyle S \ Rightarrow aSa \ Rightarrow aaSaa \ Rightarrow aabSbaa \ Rightarrow aabaabaa}

Rozšiřitelnost modelu PCFG umožňuje omezení predikce struktury začleněním očekávání ohledně různých vlastností RNA. Takové očekávání může odrážet například sklon k převzetí určité struktury RNA. Začlenění příliš velkého množství informací však může zvýšit složitost PCFG prostoru a paměti a je žádoucí, aby model na bázi PCFG byl co nejjednodušší.

Každému možnému řetězci $x,$ který gramatika generuje, je přiřazena pravděpodobnostní váha daná modelem PCFG . Z toho vyplývá, že součet všech pravděpodobností všech možných gramatických produkcí je . Skóre pro každý spárovaný a nepárový zbytek vysvětluje pravděpodobnost vzniku sekundárních struktur. Produkční pravidla také umožňují skórovat délky smyček a také pořadí skládání párů bází, takže je možné prozkoumat rozsah všech možných generací včetně suboptimálních struktur z gramatiky a přijmout nebo odmítnout struktury na základě prahových hodnot skóre. ${\ displaystyle P (x | \ theta)}$ ${\ displaystyle \ theta}$ ${\ displaystyle \ sum _ {\ text {x}} P (x | \ theta) = 1}$

Implementace

Implementace sekundární struktury RNA založené na přístupech PCFG lze využít v:

Hledání konsensuální struktury optimalizací společných strukturálních pravděpodobností oproti MSA.
Modelování kovariace párů bází k detekci homologie při vyhledávání v databázi.
párové současné skládání a zarovnání.

Existují různé implementace těchto přístupů. Například Pfold se používá v predikci sekundární struktury ze skupiny příbuzných sekvencí RNA, kovarianční modely se používají při vyhledávání databází pro homologní sekvence a anotaci a klasifikaci RNA, RNApromo, CMFinder a TEISER se používají při hledání stabilních strukturních motivů v RNA.

Aspekty návrhu

Návrh PCFG ovlivňuje přesnost predikce sekundární struktury. Jakýkoli užitečný pravděpodobnostní model predikce struktury založený na PCFG musí udržovat jednoduchost bez velkého kompromisu v přesnosti predikce. Příliš složitý model vynikajícího výkonu v jedné sekvenci se nemusí škálovat. Gramatický model by měl být schopen:

Najděte optimální zarovnání mezi sekvencí a PCFG.
Vyhodnoťte pravděpodobnost struktur pro posloupnost a podsekvence.
Parametrizujte model školením o sekvencích/strukturách.
Najděte optimální strom analýzy gramatiky (algoritmus CYK).
Zkontrolujte nejasnou gramatiku (algoritmus podmíněného vnitřku).

Výsledek několika stromů analýzy na gramatiku označuje nejednoznačnost gramatiky. To může být užitečné při odhalování všech možných struktur párů bází pro gramatiku. Optimální struktura je však ta, kde existuje pouze jedna korespondence mezi stromem analýzy a sekundární strukturou.

Lze rozlišit dva typy nejasností. Analyzujte nejednoznačnost stromu a strukturální nejednoznačnost. Strukturální nejednoznačnost neovlivňuje termodynamické přístupy, protože výběr optimální struktury je vždy na základě nejnižších skóre volné energie. Nejasnost analýzy stromu se týká existence více analyzovaných stromů na sekvenci. Taková nejednoznačnost může odhalit všechny možné báze spárované struktury pro sekvenci vygenerováním všech možných stromů analýzy a poté nalezením optimálního. V případě strukturální nejednoznačnosti popisuje několik stromů analýzy stejnou sekundární strukturu. To zakrývá rozhodnutí algoritmu CYK o nalezení optimální struktury, protože korespondence mezi stromem analýzy a strukturou není jedinečná. Nejistotu gramatiky lze zkontrolovat pomocí algoritmu podmíněného vnitřku.

Sestavení modelu PCFG

Pravděpodobnostní bezkontextová gramatika se skládá z terminálních a neterminálních proměnných. Každý prvek, který má být modelován, má produkční pravidlo, kterému je přiřazena pravděpodobnost odhadovaná z tréninkové sady struktur RNA. Produkční pravidla se používají rekurzivně, dokud nezůstanou pouze koncové zbytky.

Počáteční neterminální vytváří smyčky. Zbytek gramatiky pokračuje s parametrem, který rozhoduje, zda je smyčka začátkem kmene nebo oblasti $s$ jedním vláknem $s$ a parametrem, který vytváří spárované báze. ${\ displaystyle \ mathbf {\ mathit {S}}}$ ${\ displaystyle \ mathbf {\ mathit {L}}}$ ${\ displaystyle \ mathbf {\ mathit {F}}}$

Formalismus tohoto jednoduchého PCFG vypadá takto:

{\ displaystyle {\ mathit {S \ to LS | L}}}

{\ displaystyle {\ mathit {L \ to s | dFd}}}

{\ displaystyle {\ mathit {F \ to dFd | LS}}}

Aplikace PCFG v predikčních strukturách je vícestupňový proces. Kromě toho může být samotný PCFG začleněn do pravděpodobnostních modelů, které berou v úvahu evoluční historii RNA nebo vyhledávají homologní sekvence v databázích. V kontextu evoluční historie zahrnutí předchozích distribucí struktur RNA se strukturálním zarovnáním do produkčních pravidel PCFG usnadňuje dobrou přesnost predikce.

Souhrn obecných kroků pro využití PCFG v různých scénářích:

Vygenerujte pravidla produkce pro sekvence.
Zkontrolujte nejednoznačnost.
Rekurzivně generujte analyzované stromy možných struktur pomocí gramatiky.
Nejspolehlivější sekvenci hodnotíte a analyzujete stromy analýzy.

Algoritmy

Existuje několik algoritmů zabývajících se aspekty pravděpodobnostních modelů založených na PCFG v predikci struktury RNA. Například algoritmus inside-outside a algoritmus CYK. Algoritmus uvnitř-vně je rekurzivní algoritmus bodování dynamického programování, který může následovat paradigmata maximalizace očekávání . Vypočítává celkovou pravděpodobnost všech derivací, které jsou v souladu s danou sekvencí, na základě nějakého PCFG. Vnitřní část vyhodnocuje podstromy z analyzovaného stromu, a proto pravděpodobnosti subsekvencí dané PCFG. Vnější část vyhodnocuje pravděpodobnost úplného stromu analýzy pro celou sekvenci. CYK upravuje bodování uvnitř-venku. Všimněte si, že termín 'CYK algoritmus' popisuje variantu CYK vnitřního algoritmu, který najde optimální strom analýzy pro sekvenci pomocí PCFG. Rozšiřuje skutečný algoritmus CYK používaný v nepravděpodobných CFG.

Vnitřní algoritmus vypočítává pravděpodobnosti pro všechny podstromy analýzy rozdělené na pro podsekvenci . Vnější algoritmus vypočítává pravděpodobnosti úplného stromu analýzy pro sekvenci $x$ z kořene bez výpočtu . Proměnné $α$ a $β$ upřesňují odhad pravděpodobnostních parametrů PCFG. Algoritmus PCFG je možné přehodnotit tak, že zjistíme očekávaný počet použití stavu při derivaci součtem všech produktů $α$ a $β$ děleno pravděpodobností pro sekvenci $x$ danou modelem . Je také možné zjistit očekávaný počet použití produkčního pravidla pomocí maximalizace očekávání, která využívá hodnoty $α$ a $β$ . Algoritmus CYK vypočítá, aby našel nejpravděpodobnější strom analýzy a výnosy . ${\ Displaystyle \ alpha (i, j, v)}$ ${\ Displaystyle i, j, v}$ ${\ displaystyle W_ {v}}$ ${\ displaystyle x_ {i}, ..., x_ {j}}$ ${\ displaystyle \ beta (i, j, v)}$ ${\ displaystyle x_ {i}, ..., x_ {j}}$ ${\ displaystyle P (x | \ theta)}$ ${\ Displaystyle \ gamma (i, j, v)}$ ${\ displaystyle {\ hat {\ pi}}}$ ${\ Displaystyle \ log P (x, {\ hat {\ pi}} | \ theta)}$

Složitost paměti a času pro obecné algoritmy PCFG v předpovědích struktury RNA jsou a . Omezením PCFG lze tento požadavek změnit, jako je tomu u metod vyhledávání v databázi. ${\ displaystyle O (L^{2} M)}$ ${\ displaystyle O (L^{3} M^{3})}$

PCFG při hledání homologie

Covariance modely (CM) jsou speciální typ PCFG s aplikacemi v databázových vyhledáváních homologů, anotací a klasifikace RNA. Prostřednictvím CM je možné vybudovat profily RNA založené na PCFG, kde mohou být související RNA reprezentovány konsensuální sekundární strukturou. Balíček pro analýzu RNA Infernal používá takové profily pro odvození zarovnání RNA. Databáze Rfam také používá CM při klasifikaci RNA do rodin na základě jejich struktury a informací o sekvenci.

CM jsou navrženy z konsensuální struktury RNA. CM umožňuje v zarovnání indely neomezené délky. Terminály tvoří stavy v CM a pravděpodobnost přechodu mezi stavy je 1, pokud nejsou uvažovány žádné indely. Gramatiky v CM jsou následující:

${\ displaystyle P \ to aWb}$: pravděpodobnosti párových interakcí mezi 16 možnými páry
${\ displaystyle L \ to aW}$: pravděpodobnosti generování 4 možných jednotlivých základen vlevo
${\ displaystyle R \ to Wa}$: pravděpodobnosti generování 4 možných jednotlivých základen vpravo
${\ displaystyle B \ to SS}$: rozdvojení s pravděpodobností 1
${\ Displaystyle S \ až W}$: začít s pravděpodobností 1
${\ Displaystyle E \ to \ epsilon}$: končí s pravděpodobností 1

Model má 6 možných stavů a každá státní gramatika obsahuje různé typy pravděpodobností sekundární struktury neterminálů. Stavy jsou spojeny přechody. V ideálním případě se aktuální stavy uzlů připojují ke všem stavům vložení a následné stavy uzlů se připojují ke stavům bez vložení. Aby bylo možné vkládat více než jeden základní stav vložení, připojte se k sobě.

K bodování modelu CM se používají algoritmy inside-outside. CM používají trochu jinou implementaci CYK. Skóre emise log -odds pro optimální strom analýzy - - se vypočítávají ze stavů vyzařování . Vzhledem k tomu, že tato skóre jsou funkcí délky sekvence, je dosaženo více diskriminačního opatření k obnovení optimálního skóre pravděpodobnosti stromu analýzy-- omezením maximální délky sekvence, která má být zarovnána, a výpočtem log-odds relativně k nule. Čas výpočtu tohoto kroku je lineární vzhledem k velikosti databáze a algoritmus má složitost paměti . ${\ displaystyle \ log {\ hat {e}}}$ ${\ displaystyle P, ~ L, ~ R}$ ${\ displaystyle \ log {\ text {P}} (x, {\ hat {\ pi}} | \ theta)}$ ${\ displaystyle O (M_ {a} D+M_ {b} D^{2})}$

Příklad: Použití evolučních informací k vedení predikce struktury

Algoritmus KH-99 od Knudsena a Heina tvoří základ Pfoldova přístupu k predikci sekundární struktury RNA. V tomto přístupu vyžaduje parametrizace kromě pravděpodobností sloupců a mutací také informace o evoluční historii odvozené ze stromu zarovnání. Pravděpodobnosti gramatiky jsou pozorovány z tréninkové datové sady.

Odhadněte pravděpodobnosti sloupců pro spárované a nepárové základny

Ve strukturálním vyrovnání jsou pravděpodobnosti sloupců nepárových bází a sloupců spárovaných bází nezávislé na ostatních sloupcích. Počítáním základen v polohách jednotlivých základen a spárovaných polohách získáme frekvence základen ve smyčkách a stoncích. Pro párů bází $X$ a $Y$ výskyt je také počítána jako výskytu . Stejné základní páry, jako jsou ty, které se počítají dvakrát. ${\ displaystyle XY}$ ${\ displaystyle YX}$ ${\ Displaystyle XX}$

Vypočítejte míry mutací pro spárované a nepárové báze

Spárováním sekvencí všemi možnými způsoby se odhadují celkové míry mutací. Aby se obnovily věrohodné mutace, měl by být použit práh identity sekvence, aby bylo srovnání mezi podobnými sekvencemi. Tento přístup používá 85% prah identity mezi párovacími sekvencemi. Rozdíly v polohách první jednoduché báze - kromě mezerových sloupců - mezi páry sekvencí se počítají tak, že pokud stejná pozice ve dvou sekvencích měla různé báze $X, Y,$ počet rozdílů se pro každou sekvenci zvyšuje.

while  $X\neq Y$ 
                $C_{\text{XY}}+1$  first sequence  pair
                $C_{\text{YX}}+1$  second sequence pair

Calculate mutation rates.
               Let   $r_{\text{XY}}=$  mutation of base X to base Y  $={\frac {K~C_{\text{XY}}}{P_{x}P_{s}}}$ 
               Let   $r_{\text{XX}}=$  the negative of the rate of X mutation to other bases  $=-\sum r_{\text{XY}}$ 
                $P_{s}=$  the probability that the base is not paired.

Pro nepárové báze se používá matice rychlosti mutace 4 X 4, která splňuje, že tok mutací z X do Y je reverzibilní:

{\ displaystyle PX^{r} XY = PY^{r} YX}

Pro základní páry je podobně generována distribuční matice rychlosti 16 X 16. PCFG se používá k předpovědi předchozího rozdělení pravděpodobnosti struktury, zatímco pozdější pravděpodobnosti jsou odhadovány algoritmem inside-exter a nejpravděpodobnější struktura je nalezena algoritmem CYK.

Odhadněte pravděpodobnosti zarovnání

Po výpočtu předchozích pravděpodobností sloupce se pravděpodobnost zarovnání odhadne součtem všech možných sekundárních struktur. Každý sloupec $C$ v sekundární struktury pro sekvence $D$ délky $l$ tak, že mohou být jehož vzhledem k vyrovnání stromu $T$ a mutační modelu $M$ . Předchozí distribuce daná PCFG je . Fylogenetický strom, $T$ lze vypočítat z modelu odhadem maximální pravděpodobnosti. Mezery jsou považovány za neznámé báze a sčítání lze provést pomocí dynamického programování . ${\ Displaystyle \ sigma}$ ${\ displaystyle D = (C_ {1}, ~ C_ {2}, ... C_ {l})}$ ${\ Displaystyle P (\ sigma | M)}$

{\ displaystyle P (D | T, M)}

{\ Displaystyle = \ sum P (D, \ sigma | T, M)}

{\ Displaystyle = \ sum P (D | \ sigma, T, M) P (\ sigma | T, M)}

{\ Displaystyle = \ sum P (D | \ sigma, T, M) P (\ sigma | M)}

Každému pravidlu v gramatice přiřaďte pravděpodobnosti produkce

Každé struktuře v gramatice jsou přiřazeny výrobní pravděpodobnosti vymyšlené ze struktur tréninkové datové sady. Tyto předchozí pravděpodobnosti dávají váhu přesnosti předpovědí. Počet použití každého pravidla závisí na pozorováních z tréninkové datové sady pro tuto konkrétní gramatickou funkci. Tyto pravděpodobnosti jsou zapsány v závorkách v gramatickém formalismu a každé pravidlo bude mít celkem 100%. Například:

{\ Displaystyle S \ až LS (80 \%) | L (20 \%)}

{\ Displaystyle L \ to s (70 \%) | dFd (30 \%)}

{\ Displaystyle F \ až dFd (60,4 \%) | LS (39,6 \%)}

Předpovídejte pravděpodobnost struktury

Vzhledem k předchozím srovnávacím frekvencím dat lze nejpravděpodobnější strukturu ze souboru predikovaného gramatikou vypočítat maximalizací pomocí algoritmu CYK. Struktura s nejvyšším předpokládaným počtem správných předpovědí je uvedena jako konsensuální struktura. ${\ Displaystyle P (\ sigma | D, T, M)}$

{\ Displaystyle \ sigma _ {MAP} = \ arg {\ underset {\ sigma} {\ max}} P (D | \ sigma, T^{M} L, M) P (\ sigma | M)}

Pfold vylepšení algoritmu KH-99

Je žádoucí, aby přístupy založené na PCFG byly dostatečně škálovatelné a obecné. Kompromisní rychlost pro přesnost musí být co nejmenší. Pfold řeší omezení algoritmu KH-99 s ohledem na škálovatelnost, mezery, rychlost a přesnost.

V Pfold jsou mezery považovány za neznámé. V tomto smyslu se pravděpodobnost mezerového sloupce rovná pravděpodobnosti prázdného sloupce.
V Pfold je strom $T$ vypočítán před predikcí struktury spojením sousedů a ne podle maximální pravděpodobnosti pomocí gramatiky PCFG. Pouze délky větví jsou přizpůsobeny odhadům maximální pravděpodobnosti.
Předpokladem Pfold je, že všechny sekvence mají stejnou strukturu. Prah identity sekvence a umožňující 1% pravděpodobnost, že se jakýkoli nukleotid stane dalším limitem zhoršení výkonu v důsledku chyb zarovnání.

Analýza proteinové sekvence

Zatímco PCFG se ukázaly jako účinné nástroje pro předpovídání sekundární struktury RNA, použití v oblasti analýzy sekvencí proteinů bylo omezené. Velikost aminokyselinové abecedy a rozmanitost interakcí pozorovaných v proteinech činí odvozování gramatiky mnohem náročnějším. V důsledku toho byla většina aplikací teorie formálních jazyků na analýzu proteinů omezena hlavně na produkci gramatik s nižší expresivní schopností pro modelování jednoduchých funkčních vzorů založených na lokálních interakcích. Protože proteinové struktury běžně vykazují závislosti vyššího řádu včetně vnořených a křížených vztahů, jasně překračují možnosti jakéhokoli CFG. Přesto vývoj PCFG umožňuje vyjádřit některé z těchto závislostí a poskytnout schopnost modelovat širší škálu proteinových vzorů.

Jednou z hlavních překážek při odvozování proteinové gramatiky je velikost abecedy, která by měla kódovat 20 různých aminokyselin . Bylo navrženo řešit to pomocí fyzikálně-chemických vlastností aminokyselin, aby se výrazně snížil počet možných kombinací symbolů na pravé straně v produkčních pravidlech: místo 20 typů aminokyselin , např. Malých, jsou použity 3 úrovně kvantitativní vlastnosti , střední nebo velký objem van der Waals . Na základě takového schématu byly vytvořeny PCFG pro generování deskriptorů vazebného místa i kontaktního místa šroubovice-šroubovice. Významnou vlastností těchto gramatik je, že analýza jejich pravidel a analyzovaných stromů může poskytnout biologicky smysluplné informace.

Languages

In other projects