Entropia Shannona

9.1 wprowadzenie

Chomsky początkowo sformalizował gramatyki bez kontekstu (CFG) jako próbę modelowania języków. Od tego czasu są one szeroko stosowane w różnych zastosowaniach informatycznych. Cfg mają charakter rekurencyjny i składają się z zestawów reguł, które mogą napędzać ciągi alfabetów, określane również jako słowa. Zbiór słów generowanych przez gramatykę jest określany jako język tej gramatyki. O gramatyce mówi się, że jest jednoznaczna, jeśli istnieje korespondencja jeden do jednego między słowami a ich opisowymi pochodnymi. Stochastyczne CFGs (SCFGs) przypisują prawdopodobieństwa do każdej reguły, która z kolei przypisuje wartość prawdopodobieństwa każdemu słowu przez pomnożenie prawdopodobieństwa reguł używanych do wyprowadzenia tego słowa . Grenander, Kuich, Hutchins, Soule i inni badali ważne właściwości CFG i Scfg, takie jak zbieżność średniej długości derywacji, pojemność lub Entropia Shannona (Entropia Shannona) zdefiniowana w , przy użyciu technik generowania funkcji. Schemat struktury wtórnej RNA ma również charakter wolny od kontekstu, co pozwala na opisanie go za pomocą takich gramatyk. Struktura wtórna RNA została po raz pierwszy formalnie opisana przez Smitha i Watermana . Kombinatoryczne cechy drugorzędowych struktur RNA zostały następnie zbadane przez Steina i Watermana, a następnie zbadane przez Viennot i Vauchaussade de Chaumont, Hofacker i in. , Nebel, Liao i Wang, Doslic et al. i inne wykorzystujące funkcje generujące i funkcje generujące prawdopodobieństwo.

SCFGs miały duży wpływ na badania struktury wtórnej RNA . Modelowanie struktury wtórnej RNA pomaga nam przewidywać strukturę RNA i jej późniejszą funkcję biologiczną, ponieważ funkcje wielu RNA, takich jak różne klasy kodujących RNA (ncRNA), są związane z ich strukturami. Typowo, przewidywanie drugorzędowej struktury RNA odbywa się poprzez minimalizację energii fałdowania sekwencji w oparciu o termodynamiczny model fałdowania, taki jak zespół Boltzmanna . SCFGs, z drugiej strony, są modelami kowariancji, które mogą imitować fałdowanie RNA z większą elastycznością. W przypadku modelu fałdowania opartego na SCFG, wartości prawdopodobieństwa są przypisywane do wszystkich możliwych scenariuszy fałdowania sekwencji RNA. Następnie, struktura o maksymalnej wartości prawdopodobieństwa (ML) jest przewidywana jako struktura drugorzędowa sekwencji RNA. PRZEWIDYWANIE ML modeli opartych na SCFG może być wykonane przez algorytm COCKE-Younger-Kasami (CYK). Podobnie jak minimalizacja energii, algorytm CYK jest realizowany poprzez programowanie dynamiczne. Celem projektowania modelu jest uzyskanie estymacji ML, które są jak najbardziej podobne do znanych struktur drugorzędowych RNA, co sprawia, że przypisywanie prawdopodobieństw do reguł jest zadaniem Krytycznym i trudnym. Rivas oferuje bardziej dogłębny wgląd w różne aspekty modelowania struktury wtórnej RNA.

metody treningowe modelu em (Current expectation maximization) składają się na ogół z następujących dwóch kroków: po pierwsze, algorytm CYK służy do przewidywania struktury każdej sekwencji RNA zestawu treningowego (etap maksymalizacji). Po drugie, prawdopodobieństwa reguły SCFG są ponownie szacowane na podstawie liczby lub częstotliwości ich wystąpień w prognozach (etap szacowania). Szacunki te można obliczyć za pomocą wcześniejszego podejścia Laplace ’ a wyjaśnionego w Durbin et al. lub wdrażanie podobnych podejść opartych na częstotliwości. Iteracyjna procedura EM może być kontynuowana do momentu uzyskania przez wynikającego z niej prawdopodobieństwa reguły pożądanej dokładności. Techniki szkolenia modelowego mogą się różnić, zarówno w definicji kryterium ML (wspólne vs warunkowe) lub w technikach estymacji reguły prawdopodobieństwa . Model składania RNA oparty na SCFG może składać się z lekkiego SCFG z tylko kilkoma regułami gramatycznymi lub może to być ciężka gramatyka składająca się z wielu reguł, takich jak super-gramatyki opisane w Rivas et al. .

w tej pracy Entropia Shannona SCFG, oznaczona tutaj jako Entropia przestrzeni gramatycznej (GS), jest analitycznie obliczana i wprowadzana jako cecha gramatyki krytycznej w modelowaniu struktury wtórnej RNA. Przedstawione preparaty są zgodne z ogólną formą entropii gramatyki znanej jako Entropia pochodna i można je znaleźć w Grenander i Soule . W Sekcji 9.2, przedstawiono formułę do obliczania entropii Shannona nieskończenie dużej przestrzeni probabilistycznej strukturalnie jednoznacznych gramatyk modelujących RNA1, która jest zgodna z derywacyjnymi formułami entropii przedstawionymi w Grenanderze . Wartości entropii GS kilku ugruntowanych modeli fałdowania RNA są następnie obliczane na podstawie różnych zestawów parametrów w sekcji 9.3. W sekcji 9.4 zaproponowano kryterium szkolenia modelu wtórnej struktury RNA opartego na SCFG w oparciu o entropię GS. Na koniec sekcja 9.5 składa się z dyskusji i wniosków.