확률론적 문맥 자유 문법

기호열을 모델링하는 문법 이론은 자연 ^[1][2][3]언어의 구조를 이해하는 것을 목적으로 하는 컴퓨터 언어학 연구로부터 유래했습니다.확률론적 문맥 자유 문법(PCFG)은 RNA 구조가 컴퓨터 ^{[4][5][6][7][8]}언어학에서 도입된 지 거의 40년 후에 확률론적 모델링에 적용되었다.

PCFG는 숨겨진 마르코프 모델이 정규 문법을 확장하는 방법과 유사하게 문맥이 없는 문법을 확장합니다.각 생산에는 확률이 할당됩니다.파생상품(파스)의 확률은 그 파생상품에 사용된 생산물의 확률의 곱이다.이러한 확률은 모델의 매개변수로 볼 수 있으며, 큰 문제의 경우 기계 학습을 통해 이러한 매개변수를 학습하는 것이 편리합니다.확률론적 문법의 유효성은 훈련 데이터 집합의 맥락에 의해 제한된다.

PCFG는 RNA 분자의 구조와 프로그래밍 언어 설계를 연구하기 위해 자연 언어 처리와 같은 다양한 분야에 응용하고 있습니다.효율적인 PCFG를 설계하려면 확장성과 범용성을 고려해야 합니다.문법의 모호성 등의 문제는 반드시 해결되어야 한다.문법 디자인은 결과 정확도에 영향을 미칩니다.문법 해석 알고리즘에는 다양한 시간과 메모리 요건이 있습니다.

정의들

파생:문법에서 문자열을 재귀적으로 생성하는 프로세스입니다.

해석:오토마톤을 사용한 유효한 파생 검색.

해석 트리:문법과 시퀀스의 정렬입니다.

PCFG 문법 파서의 예로는 푸시다운 자동화가 있습니다.이 알고리즘은 왼쪽에서 오른쪽으로 스택과 같은 방식으로 문법의 비종단을 해석합니다.이 무차별적인 접근법은 그다지 효율적이지 않다.RNA에서 Coke의 2차 구조 예측 변종 -Young-Kasami(CYK) 알고리즘은 푸시다운 ^[9]오토마타보다 문법 해석에 더 효율적인 대안을 제공합니다.PCFG 파서의 또 다른 예로는 Treebank를 ^[10]사용하여 훈련한Stanford Statistical 파서는 Stanford Statistical 파서입니다.

형식적 정의

CFG와 마찬가지로 확률론적 문맥 자유 문법 G는 5배수로 정의할 수 있다.

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

어디에

• M은 비단말기 기호 세트입니다.
• T는 단자 기호 집합입니다.
• R은 생산 규칙 집합입니다.
• S는 시작 기호입니다.
• P는 생산 규칙에 대한 확률 집합입니다.

숨겨진 마르코프 모델과의 관계

PCFG 모델은 숨겨진 마르코프 모델이 정규 문법을 확장하는 것과 동일한 방식으로 문맥 자유 문법을 확장합니다.

Inside-Outside 알고리즘은 Forward-Backward 알고리즘의 아날로그입니다.일부 PCFG를 기반으로 특정 시퀀스와 일치하는 모든 파생 프로그램의 총 확률을 계산합니다.이는 PCFG가 시퀀스를 생성할 확률과 동등하며 시퀀스가 주어진 문법과 얼마나 일치하는지 직관적으로 알 수 있습니다.Inside-Outside(내부-외부) 알고리즘은 RNA의 경우 교육 시퀀스에서 관찰된 이전 주파수를 추정하기 위해 모델 매개변수화에 사용됩니다.

CYK 알고리즘의 동적 프로그래밍 변형은 PCFG 모델에 대한 RNA 시퀀스의 Viterbi 해석을 찾습니다.이 해석은 특정 PCFG에 의해 시퀀스가 파생될 가능성이 가장 높습니다.

문법 구성

문맥이 없는 문법은 자연 ^[3]언어를 모델링하려는 시도에서 영감을 얻은 규칙 집합으로 표현됩니다.규칙은 절대적이며 Backus-Naur 형식으로 알려진 일반적인 구문 표현을 가지고 있습니다.제조규칙은 단말기${\displaystyle }${${\displaystyle a,}$ $}({$right$$$\})$와 비단말기S 기호로 구성되며 $공백$의$$\$displaystyle \epsilon$을 엔드$$ 포인트로 사용할 수도 있습니다.CFG 및 PCFG의 생산 규칙에서는 왼쪽에는 비터미널이1개만 있고 오른쪽에는 터미널 또는 비터미널 문자열이 있습니다.PCFG의 null은 ^[9]제외됩니다.문법의 예:

$(\displaystyle S\to aS,S\to bS,S\to \epsilon })$

이 문법은 ''또는'' 문자를 사용하여 다음과 같이 단축할 수 있습니다.

${\displaystyle S\to aS bS \epsilon}$

문법의 단자는 단어이며, 문법의 규칙을 통해 비단말기호는 단자 및/또는 비단말의 문자열로 변환된다.위의 문법은 "비단말기 S에서 시작하여 방출은 a $또는{\displaystyle }$ b 또는$$"\$displaystyle \epsilon"$ 중 하나를 생성할 수 있다"로 읽힌다.그 유래는 다음과 같습니다.

$(\displaystyle S\right 화살표 aS\right 화살표 abs\right 화살표 abs\right 화살표 abb)$

문법이 모호한 경우 동일한 단어 시퀀스에 여러 해석이 있을 수 있기 때문에 동형문자에 적용할 경우 파싱이 모호한 결과를 초래할 수 있습니다.신문 헤드라인 '이라크 머리, 무기를 찾다'와 같은 말장난 문장은 모호한 패러디의 한 예이다.

모호한 파스를 다루는 한 가지 전략은 더 많은 규칙을 추가하거나, 한 규칙이 다른 규칙보다 우선하도록 그것들을 우선시하는 것이다.그러나 이것은 종종 관리하기 어려울 정도로 규칙을 확산시키는 단점이 있다.또 다른 어려움은 무면허 구조물도 발생하는 과잉 발전이다.

확률론적 문법은 주파수 가중치에 대한 다양한 생산의 순위를 매겨 이러한 문제를 회피하고 "가장 가능성이 높은" 해석(승자독식)을 도출한다.사용 패턴이 시간적 이동에서 변경됨에 따라, 이러한 확률론적 규칙을 다시 학습할 수 있으며, 따라서 문법을 갱신할 수 있다.

프로덕션 규칙에 확률을 할당하면 PCFG가 됩니다.이러한 확률은 모델링할 언어와 유사한 구성의 훈련 세트에 대한 분포를 관찰함으로써 알 수 있다.대부분의 광범위한 언어 표본에서 데이터로부터 확률을 추정하는 확률론적 문법은 일반적으로 수작업 문법을 능가한다.PCFG와 대조되는 CFG는 시퀀스-구조 관계를 통합하지만 시퀀스 구조적 잠재력을 드러내는 점수 지표가 부족하기 때문에 RNA 구조 예측에 적용할 수 없다.

가중 문맥 자유 문법

Weighted Context-Free Grammar(WCFG; 가중치 문맥 자유 문법)는 문맥 자유 문법의 보다 일반적인 범주이며, 각 문법에 관련된 숫자 가중치가 있습니다.WCFG에서 특정 해석 트리의 무게는 트리 내의 모든 규칙 가중치의 곱^[12](또는^[13] 합계)입니다.각 규칙 가중치는 규칙이 트리에 사용되는 횟수만큼 포함됩니다.WCFG의 특수한 경우는 PCFG입니다.여기서 가중치는 (의 로그) 확률입니다.

확장 버전의 CYK 알고리즘을 사용하여 일부 WCFG에서 문자열의 "가장 가벼운" 파생(최소 무게)을 찾을 수 있습니다.

트리 가중치가 규칙 가중치의 곱인 경우 WCFG와 PCFG는 동일한 확률 ^[12]분포 집합을 나타낼 수 있습니다.

적용들

RNA구조예측

에너지 최소화^[16][17] 및 PCFG는 유사한 ^[4][5][9]성능으로 RNA 2차 구조를 예측하는 방법을 제공합니다.그러나 PCFG에 의한 구조 예측은 최소 자유 에너지 계산이 아닌 확률적으로 평가된다.PCFG 모델 매개변수는 에너지 최소화 ^[18][19]방법의 경우와 같이 실험적인 결정에 의한 것이 아니라 RNA 구조의 데이터베이스에서 관찰된 다른 특징의 주파수에서 직접 도출된다.

PCFG에서 모델링할 수 있는 다양한 구조의 유형에는 장거리 상호작용, 쌍방향 구조 및 기타 중첩 구조가 포함됩니다.그러나 의사 노트는 모델링할 ^[4][5][9]수 없습니다.PCFG는 각 프로덕션 규칙에 확률을 할당하여 CFG를 확장합니다.문법의 최대 확률 해석 트리는 최대 확률 구조를 의미합니다.RNA는 1차 배열에 걸쳐 구조를 보존하기 때문에 RNA 구조 예측은 비교 배열 분석의 진화 정보와 그러한 확률에 기초한 구조 타당성에 대한 생물물리학적 지식을 결합함으로써 유도될 수 있다.또한 PCFG 규칙을 사용한 구조 호몰로그의 검색 결과는 PCFG 파생 확률에 따라 점수가 매겨집니다.따라서 기본 쌍과 단일 가닥 영역의 동작을 모델링하기 위한 문법을 구축하는 것은 관련된 RNA의 ^[9]구조적 다중 시퀀스 정렬의 특징을 탐구하는 것으로 시작합니다.

$(\displaystyle S\to aSa bSb aa bb)$

위의 문법은 Outside-in 방식으로 문자열을 생성합니다.즉, 단말기의 가장 먼 쪽의 베이스 페어가 최초로 도출됩니다.${\displaystyle \mathrm{따라서}}$ a ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ a ${\displaystyle b}$ ${\displaystyle a}$ a a$$a a \ $displaystyle$ a $baabaaa와$$같은{\displaystyle }$ 문자열은 내부로 이동하기 전에 먼저 양쪽 원위부 a를 생성함으로써 도출됩니다.

$({displaystyle S\right 화살표 aSa\right 화살표 aaaa\right 화살표 aabaaa\right 화살표 aabaaaa})$

PCFG 모델의 확장성은 RNA의 다른 특징에 대한 기대를 포함시킴으로써 구조 예측을 제약할 수 있습니다.예를 들어,^[11] 그러한 기대는 RNA가 특정 구조를 가정하는 경향을 반영할 수 있습니다.그러나 너무 많은 정보를 포함하면 PCFG의 공간과 메모리가 복잡해질 수 있으므로 PCFG 기반 모델은 가능한 ^[11][20]한 단순하게 하는 것이 좋습니다.

문법이 생성하는 모든 문자열 x에는 PCFG 모델 $"\displaystyle \theta$$}"\displaystyle$ $(x \theta$)가$$ 지정됩니다.따라서 가능한 모든 문법 생성에 대한 모든 확률의 합계는 ${\displaystyle \underset{}{}}$ P${\displaystyle (x}$ )${\displaystyle =}$ ${\displaystyle 1}$ $\displaystyle$ \$sum _{$ta } \$text}$입니다.쌍체 및 비쌍체 잔기에 대한 점수는 2차 구조 형성에 대한 가능성을 설명한다.생산규칙은 베이스쌍 스태킹 순서뿐만 아니라 스코어링 루프 길이도 허용하기 때문에 문법에서 차선의 구조를 포함한 가능한 모든 세대의 범위를 탐색하고 점수 ^[9][11]임계값을 기반으로 구조를 받아들이거나 거부할 수 있습니다.

실장

PCFG 접근법에 기초한 RNA 2차 구조 구현은 에서 사용할 수 있습니다.

• MSA에 ^[20][21]대한 구조 접합 확률을 최적화하여 합의 구조를 찾는다.
• 데이터베이스 ^[4]검색에서 호몰로지 검출을 위한 베이스 페어 공바리에이션을 모델링합니다.
• 쌍으로 동시에 접고 정렬할 ^[22][23]수 있습니다.

이러한 접근방식은 다양한 구현이 존재합니다.예를 들어 Pfold는 관련된 RNA ^[20]배열 그룹으로부터의 2차 구조 예측에 사용되며, 공분산 모델은 상동 배열의 데이터베이스 탐색에 사용되며, RNA 주석 및 분류,^[4][24] RNA 프로모, CMFinder 및 TEISER는 RNA의 ^[25][26][27]안정적인 구조 모티브를 찾는 데 사용된다.

설계에 관한 고려 사항

PCFG 설계는 2차 구조 예측 정확도에 영향을 미칩니다.PCFG에 기반한 유용한 구조 예측 확률론적 모델은 예측 정확도에 큰 영향을 주지 않고 단순성을 유지해야 합니다.너무 복잡하면 단일 시퀀스에서 뛰어난 성능의 모델이 ^[9]확장되지 않을 수 있습니다.문법 기반 모델은 다음을 수행할 수 있어야 합니다.

• 시퀀스와 PCFG 사이의 최적의 얼라인먼트를 찾습니다.
• 순서와 후속에 대한 구조의 확률을 채점합니다.
• 시퀀스/구조에 대한 교육을 통해 모델을 매개 변수화합니다.
• 최적의 문법 해석 트리(CYK 알고리즘)를 찾습니다.
• 문법이 모호한지 확인합니다(Conditional Inside 알고리즘).

문법당 여러 해석 트리의 결과는 문법의 모호성을 나타냅니다.이것은 문법에 대해 가능한 모든 베이스 페어 구조를 밝히는 데 도움이 될 수 있습니다.그러나 최적의 구조는 해석 트리와 보조 구조 사이에 하나뿐인 대응이 있는 구조입니다.

두 가지 유형의 모호성을 구별할 수 있습니다.트리 모호성과 구조적 모호성을 해석합니다.최적의 구조 선택은 항상 최저 자유 에너지 ^[11]점수에 기초하기 때문에 구조적 모호성은 열역학적 접근법에 영향을 미치지 않는다.해석 트리의 모호성은 시퀀스당 여러 해석 트리의 존재에 관한 것입니다.이러한 모호성은 가능한 모든 해석 트리를 생성한 후 최적의 ^[28][29][30]해석 트리를 찾아 시퀀스에 대해 가능한 모든 염기쌍 구조를 나타낼 수 있습니다.구조가 애매한 경우, 복수의 해석 트리는 같은 2차 구조를 기술한다.이는 해석 트리와 구조 간의 대응관계가 ^[31]고유하지 않기 때문에 최적의 구조를 찾는 CYK 알고리즘 결정을 모호하게 합니다.문법의 모호성은 조건부 내부 ^[9][11]알고리즘으로 확인할 수 있습니다.

PCFG 모델 구축

확률론적 문맥 자유 문법은 말단 변수와 비말단 변수로 구성됩니다.모델링되는 각 피쳐에는 RNA 구조의 훈련 세트로부터 추정된 확률이 할당되는 생산 규칙이 있습니다.생산 규칙은 단말 잔여물만 남을 때까지 재귀적으로 적용됩니다.

시동 $S$(\displaystyle $\mathbf {S})는$루프를 생성합니다$$.나머지 문법은 루프가 스템의 시작인지 단일 고립 영역의 시작인지를 결정하는 $파라미터{\displaystyle \mathit{}}$ L$(\$과 쌍을 이루는 베이스를 생성하는 $파라미터{\displaystyle \mathit{}}$ F$(\$로 진행됩니다.

이 단순한 PCFG의 형식은 다음과 같습니다.

${\displaystyle {S\to LS L}}$

${\displaystyle {L\to s dFd}}$

${\displaystyle {F\to dFd LS}}$

PCFG를 구조 예측에 적용하는 것은 다단계 프로세스입니다.또한 PCFG 자체는 RNA 진화 이력을 고려하거나 데이터베이스의 상동성 시퀀스를 검색하는 확률론적 모델에 통합될 수 있다.진화이력에서 PCFG의 생산규칙에 구조배열의 RNA구조의 사전분포를 포함하면 예측정확도가 ^[21]향상된다.

다양한 시나리오에서 PCFG를 사용하기 위한 일반적인 순서의 개요:

• 시퀀스에 대한 생산 규칙을 생성합니다.
• 애매함을 체크합니다.
• 문법을 사용하여 가능한 구조의 구문 분석 트리를 반복적으로 생성합니다.
• 가장 그럴듯한 ^[9]시퀀스에 대해 구문 분석 트리의 순위를 매기고 점수를 매깁니다.

알고리즘

RNA 구조 예측에서 PCFG 기반 확률론적 모델의 측면을 다루는 몇 가지 알고리즘이 존재한다.예를 들어 내부 외부 알고리즘과 CYK 알고리즘입니다.Inside-Outside 알고리즘은 기대 최대화 패러다임을 따를 수 있는 재귀 동적 프로그래밍 스코어링 알고리즘입니다.일부 PCFG를 기반으로 특정 시퀀스와 일치하는 모든 파생 프로그램의 총 확률을 계산합니다.내부 부품은 해석 트리에서 하위 트리를 채점하기 때문에 PCFG에 주어진 후속 확률입니다.외부 부품은 전체 ^[32][33]시퀀스에 대한 완전한 해석 트리의 확률을 채점합니다.CYK는 Inside Outside 스코어링을 변경합니다.'CYK 알고리즘'이라는 용어는 PCFG를 사용하여 시퀀스의 최적의 해석 트리를 찾는 내부 알고리즘의 CYK 변형을 나타냅니다.비확률론적 CFG에서 ^[9]사용되는 실제 CYK 알고리즘을 확장한다.

Inside 알고리즘은$$ $v$에 루트된 해석 서브트리의${\displaystyle }모든{\displaystyle }$ ${\displaystyle i,}$$$$,$ ${\displaystyle v}$(\$displaystyle$$i,$ j$, v$)에 대해${\displaystyle \alpha }$$i, j, v$$)$ $확률$을 계산합니다.이후 ${\displaystyle x_{},}$ ${\displaystyle .,}$ x$$(\$displaystyle x_i, x_{j$}, x_j$$$\},$ β $알고리즘$의 외부에서는${\displaystyle }$β, i${\displaystyle \}}$의 ${\displaystyle \mathrm{확률}}$을 계산합니다.$루트로$부터의 시퀀스x$$의 $완전$한 해석 트리의 확률$$$($${\displaystyle {xi}_{}{}_{}}$.${\displaystyle }$, ${\displaystyle x_{}}$j {$i}$ , ...$x_{j$ 의 $계산$을 제외).변수 α와 β는 PCFG의 확률 매개변수의 추정을 세분화합니다.모델${\displaystyle }P{\displaystyle }$ ( ${\displaystyle x}$ ${\displaystyle )}$)\${\displaystyle style}$ P(x \$theta$ )\$style$ P$(x$\theta$)\}$에서 α와 β의 모든 곱을 시퀀스 x의 확률로 나눈 값을 구함으로써 PCFG 알고리즘을 재추정할 수 있으며, 예상 생성 횟수 규칙도 구할 수 있다.e는 α와 ^[32][33]β의 값을 이용한 기대치화에서 사용된다.$CYK{\displaystyle }$ 알고리즘은 $^\$style$\gamma($$i,j,v$를 ${\displaystyle \mathrm{계산}}$하여$가장$ 가능성이 높은 해석 트리 ${\displaystyle \stackrel{}{^\backslash }}$display\$gamma{\displaystyle \stackrel{}{}}$($i$${\displaystyle ,}$j,$v)$를 찾아 로그$,$ ${\displaystyle \stackrel{}{^}}$）\$display\log P(x,{\hat$^[9]를 ${\displaystyle \mathrm{생성}}$합니다$.$

RNA 구조 예측에서 일반 PCFG 알고리즘의 메모리 및 시간 복잡도는 각각 O${\displaystyle ({L\mathrm{}}^{}}$ $)$ {{$displaystyle$ O$(L^{2}M)},$ $O$(L ${\displaystyle {3M3\mathrm{}}^{}}${$displaystyle$ O$(L^{3}M^{3}})$이다.PCFG를 제한하면 데이터베이스 검색 방법과 마찬가지로 이 요건이 변경될 수 있습니다.

호몰로지 검색의 PCFG

공분산 모델(CM)은 호몰로그, 주석 및 RNA 분류에 대한 데이터베이스 검색에서 애플리케이션을 사용하는 특수한 유형의 PCFG입니다.CM을 통해 관련 RNA가 합의된 2차 ^[4][5]구조로 표현될 수 있는 PCFG 기반 RNA 프로파일을 구축할 수 있습니다.RNA 분석 패키지 Infernal은 이러한 프로파일을 사용하여 RNA ^[34]정렬을 추론합니다.또한 Rfam 데이터베이스는 구조 및 시퀀스 ^[24]정보를 기반으로 RNA를 패밀리로 분류하는 데 CM을 사용합니다.

CM은 컨센서스 RNA 구조에서 설계됩니다.CM을 사용하면 얼라인먼트에서 길이가 무제한인 인델을 사용할 수 있습니다.단말기는 CM 내의 상태를 구성하며, Indel이 ^[9]고려되지 않은 경우 상태 간의 전이 확률은 1입니다.CM의 문법은 다음과 같습니다.

${\displaystyle P\to aWb}$

가능한 16개 쌍 사이의 쌍별 교호작용 확률

$(\displaystyle L\to aW)$

왼쪽에서 가능한 4개의 단일 베이스를 생성할 확률

${\displaystyle R\to Wa}$

우측에 4개의 가능한 단일 베이스가 생성될 확률

${\displaystyle B\to SS}$

확률 1의 분기

${\displaystyle S\to W}$

1의 확률로 시작하다

$(\displaystyle E\to\epsilon)$

1의 확률로 끝나다

이 모델에는 6개의 가능한 상태가 있으며, 각 상태 문법은 비말단 2차 구조 확률의 다른 유형을 포함합니다.상태는 전환에 의해 연결됩니다.현재 노드 상태는 모든 삽입 상태에 연결되고 후속 노드 상태는 비삽입 상태에 연결됩니다.둘 이상의 베이스 삽입 상태를 삽입할 수 있도록 ^[9]서로 연결합니다.

CM 모델에 점수를 매기기 위해 내부 외부 알고리즘을 사용합니다.CM에서는 CYK의 실장이 약간 다릅니다.최적 해석 트리 - 로그${\displaystyle ds\stackrel{}{}}$ e$^$ {\$displaystyle$\log {$e}}$의 로그 ods 배출 $점수$는 $출력$ 상태 $P$$,$ L, R {\displaystyle P$,~L,~R$ ${\displaystyle \text{중}}$에서 산출되며, 이러한 점수는 최적의 해석 확률 ${\displaystyle 점수-로그}$ an P를 회복하기 위한 시퀀스 길이의 함수이므로 보다 차별적인 척도가 된다${\displaystyle .}$${\displaystyle (x}$ , "${\displaystyle \stackrel{}{}^}$ " )$${$style \log$ { P$}$（$$x , { \ hat { $pi }}$ \$theta }$ }$$ - 정렬되는 시퀀스의 최대 길이를 제한하고 null을 기준으로 로그오드를 계산함으로써 도달합니다.이 순서의 계산 시간은 데이터베이스 크기에 선형이며 알고리즘의 메모리 $복잡도$는${\displaystyle }$O(${\displaystyle {}_{}}$a ${\displaystyle {}_{}}$ + ${\displaystyle {}_{}{}^{}}$ ${\displaystyle {b\mathrm{}}^{}}$ D${\displaystyle {}^{}}$2$)(\displaystyle$O($M_{a}D$+M_${b}D^{2$^[9]입니다.

예:진화적 정보를 사용하여 구조 예측 안내

Knudsen과 Hein의 KH-99 알고리즘은 RNA 2차 ^[20]구조를 예측하는 Pfold 접근법의 기초를 마련한다.이 접근법에서 매개변수화에는 열과 돌연변이의 확률과 더불어 정렬 트리에서 파생된 진화 이력 정보가 필요하다.문법 확률은 교육 데이터 집합에서 관찰됩니다.

쌍체 및 비쌍체 염기에 대한 열 확률 추정

구조 선형에서 쌍체화되지 않은 기준 열과 쌍체화 기준 열의 확률은 다른 열과 독립적입니다.단일 베이스 위치 및 쌍으로 구성된 위치의 염기를 계수함으로써 루프 및 스템의 베이스 주파수를 구한다.베이스 페어 X 및 Y의 경우 $({displaystyle$XY})의 발생은 ${\displaystyle Y}$X({$displaystyle YX$의 발생으로도 카운트됩니다.${\displaystyle X}$ X$({displaystyle$XX})와 같은 베이스 페어가 2회 카운트됩니다.

쌍체 염기 및 비쌍체 염기에 대한 돌연변이율 계산

가능한 모든 방법으로 시퀀스를 조합함으로써 전체 돌연변이율을 추정한다.신뢰성 있는 돌연변이를 회복하기 위해서는 유사한 시퀀스 간에 비교가 이루어지도록 시퀀스 식별 임계값을 사용해야 한다.이 방법에서는 쌍으로 구성된 시퀀스 간에 85%의 ID 임계값을 사용합니다.시퀀스 쌍 간의 첫 번째 단일 베이스 위치 차이는 (갭된 컬럼을 제외하고) 두 시퀀스 내의 동일한 위치가 서로 다른 베이스 X, Y를 가지면 그 차이의 카운트가 각 시퀀스에 대해 증가하도록 계수된다.

$반면{\displaystyle }$ X -$$Y \$displaystyle$ X$\neq$Y                $displaystyle C_{\text{X$$$$Y}}+1$}$$첫 번째 시퀀스 쌍                $style$$YX}}+1$}$$두 번째 시퀀스 쌍 

돌연변이율을 계산합니다.                ${\displaystyle {\text{let}}_{}}$ r XY$$ {\$displaystyle r_{\text${X}$Y}}=}$ 베이스$$ X에서 베이스 Y로의 변환 $={\displaystyle }$ ${\displaystyle \frac{\text{K}{}_{}}{}}$ ${\displaystyle \frac{{\text{C}}_{}}{}}$ ${\displaystyle \frac{{}_{}}{{}_{}}}$ ${\displaystyle \frac{P_{}}{}}$ ${\displaystyle \frac{{}_{}{}_{}}{}}$ ${\displaystyle \frac{P_{}}{}}$s {\$displaystyle$=$by$ frac ${K~C_{\text{X$}$Y}}{P_{x}P_{s}}}}$                ${\displaystyle {\text{r}}_{}}$ XX $=$ {\$displaystyle r_{\text{X$}}=} 다른$$ 베이스에 대한 X 변이율의 음수 $=$ -${\displaystyle {}_{}}$ ${\displaystyle {\text{r}}_{}}$ XY$${ - \$sum$r _ { \ text { $X$ }로 합니다.$Y}}}$                ${\displaystyle P_{}}$ s $=$ (\$displaystyle P_{s$}=) 베이스가$$ 쌍을 이루지 않을 확률. 

비쌍성 염기의 경우 X에서 Y로의 돌연변이 흐름이 ^[35]가역적이라는 것을 만족시키는 4X4 돌연변이율 매트릭스가 사용된다.

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

베이스 페어의 경우 마찬가지로 16 X 16 레이트 분포 매트릭스가 생성됩니다.^[36][37]PCFG는 구조의 사전 확률 분포를 예측하는 데 사용되는 반면 사후 확률은 내부 외부 알고리즘에 의해 추정되며 가장 가능성이 높은 구조는 CYK ^[20]알고리즘에 의해 발견됩니다.

정렬 확률 추정

열 사전 확률을 계산한 후 가능한 모든 2차 구조를 합산하여 정렬 확률을 추정합니다.D ${\displaystyle =}$ ( ${\displaystyle {C\mathrm{}}_{}\text{1}{}_{}}$ ,${\displaystyle {}_{}{C\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ,${\displaystyle }$.$$C${\displaystyle {}_{}{l}_{}}$ ) \ $displaystyle$ D $=$ ( $C$_ {$1$ ) ~ C _ { $2$}$$$l$ l l l l l D = ( C _ { 1 ) （ C _ { 2 ） 。$C_{l}}$는 얼라인먼트 트리 T 및 변이 모델 M에 대해 점수를 매길 수 있다.PCFG에 의해 제공되는 이전 배포는 $P{\displaystyle (}$ 「${\displaystyle M}$」 ){ $displaystyle$ P$(\sigma$ M$)$입니다.계통수 T는 최대우도 추정을 통해 모형에서 계산할 수 있습니다.갭은 미지의 베이스로 취급되며, 합계는 동적 프로그래밍을 ^[38]통해 이루어질 수 있습니다.

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

${\displaystyle =\sum P(D,\sigma T,M)}$

${\displaystyle =\sum P(D \sum,T,M)P(\sigma T,M)}$

$\displaystyle =\sum P(D \sum, T, M)P(\sigma M)}$

문법의 각 규칙에 생산 확률 할당

문법의 각 구조에는 훈련 데이터 세트의 구조에서 설계된 생산 확률이 할당됩니다.이러한 이전 확률은 예측 ^[21][32][33]정확도에 가중치를 부여합니다.각 규칙이 사용되는 횟수는 해당 특정 문법 기능에 대한 교육 데이터 집합의 관찰 결과에 따라 달라집니다.이러한 확률은 문법 형식주의에서 괄호 안에 쓰여지고 각 규칙은 총 100%^[20]가 됩니다.예:

${\displaystyle S에서 LS(80\)} L(20\%)}$

$\displaystyle L\to s(70\) dFd(30\%)}$

$\displaystyle F\to dFd(60.4\) LS(39.6\%)}$

구조 우도 예측

데이터의 사전 정렬 빈도를 고려할 때 문법에 의해 예측되는 앙상블에서 가장 가능성이 높은 구조는 CYK 알고리즘을 통해 P${\displaystyle (}$ ${\displaystyle d}$ D${\displaystyle ,}$ $)\style$ P$(\sigma$ D,$T, M)$를 $최대화$하여 계산할 수 있습니다.정확한 예측 수가 가장 많은 구조를 합의구조로 ^[20]보고한다.

$({displaystyle_{MAP}=\arg{underset}{\max}}P(D\displaystyle,T^{M}L,M)P(\sigma M)})$

KH-99 알고리즘의 Pfold 개선

PCFG 기반의 접근법은 충분히 확장 가능하고 일반적인 것이 바람직합니다.정확성을 위해 속도를 희생하는 것은 가능한 한 최소화해야 합니다.Pfold는 확장성, 간격, 속도 및 ^[20]정확성에 관한 KH-99 알고리즘의 한계를 해결합니다.

• Pfold에서 간격은 알 수 없는 것으로 처리된다.이런 의미에서 갭된 기둥의 확률은 갭되지 않은 기둥의 확률과 같습니다.
• Pfold에서는 트리 T는 PCFG 문법에 의한 최대우도가 아닌 네이버 결합에 의한 구조 예측 전에 계산됩니다.분기 길이만 최대우도 추정치로 조정됩니다.
• Pfold의 가정은 모든 시퀀스가 동일한 구조를 가지고 있다는 것이다.배열 동일성 임계값과 뉴클레오티드가 또 다른 뉴클레오티드가 될 1%의 확률을 허용하면 정렬 오류로 인한 성능 저하가 제한된다.

단백질 배열 분석

PCFG는 RNA 2차 구조를 예측하기 위한 강력한 도구를 입증했지만 단백질 배열 분석 분야에서는 사용이 제한적이었다.사실, 아미노산 알파벳의 크기와 단백질에서 볼 수 있는 다양한 상호작용은 문법 추론을 훨씬 ^[39]더 어렵게 만든다.결과적으로, 단백질 분석에 대한 형식 언어 이론의 대부분의 적용은 주로 국소적 ^[40][41]상호작용에 기초한 단순한 기능 패턴을 모델링하기 위해 낮은 표현력의 문법 생산으로 제한되었다.단백질 구조는 일반적으로 중첩 및 교차 관계를 포함한 고차 의존성을 나타내기 때문에 CFG의 ^[39]능력을 확실히 초과합니다.그러나 PCFG의 개발을 통해 이러한 의존성의 일부를 표현하고 광범위한 단백질 패턴을 모델링할 수 있습니다.

「 」를 참조해 주세요.

• 통계 해석
• 확률 문법
• L계

레퍼런스

외부 링크

• Rfam 데이터베이스
• 지옥
• 스탠포드 파서:통계 파서
• pyStatParser