NoamChomsky의 언어학이론, 변형문법.

ChomskyHierarchy로 언어문법을 계층화. 생물정보학문제에서는 ContextFreeGrammar가 RnaSecondaryStructurePrediction에 활용된다.

이제까지 biological sequence를 1차원의 independent 하고 uncorrelated symbol 로 다루었으나 이 가정은 컴퓨터로 계산하기에는 간편하지만 구조적으로 realistic 하지 않다.

Introduction

The three-dimensional folding of [Proteins] and NucleicAcid involves extensively physical interactions between residues that are not adjacent in primary sequence. 이러한 [Protein] 과 NucleicAcid 의 longer range interactions을 허용하는 확률적인 model을 만들 수 있겠는가? 우리가 이러한 model을 효과적으로 compute 할 수 있는가?

NoamChomsky는 어떻게 뇌나 컴퓨터 프로그램이 문장을 grammatical 한지 아닌지를 결정할수 있는지 관심을 가졌다. 그는 'grammar' 라고 불리는 finite formal machines를 구축하였다. 이것은 언어에 속한 무한한 수의 문장을 회귀적으로 ([Recursion]) 계산한다. 'does the language contain this sentence?' 라는 질문을 grammar theory 는 'can the grammar generate this sentence?' 라는 질문으로 대치하였다.

첫 번째 질문은 intractable 한 반면 두 번째 질문은 실제적으로 답변되어질 수 있다. 이 일이 얼마나 잘 되는가는 얼마나 grammar 가 그 language 의 constrain를 model 하는가에 의존된다.

Definition of a transformational grammar

TransformationalGrammar 는 몇개의 symbols 과 rewriting rule α→β(production 으로도 불리운다.) 로 구성된다. α와 β는 둘다 symbol 의 string 이다. 두가지 종류의 symbol 이 있다.

1. abstract nonterminal symbols
2. terminal symbols : 실제로 observed string에서 나타난다.

Special start nonterminal : S

이 process에서 기인된 string 의 연속은 derivation 이라 불리운다. 이러한 간단한 예제 grammar 의 derivation 은 다음과 같다.

하나의 주어진 sequence 에 대한 valid derivation을 찾는 것은 [Parsing] 이라 불리워진다. 그리고 이러한 관점에서, derivation 은 sequence 의 parse 라 불리워진다. 우리는 parse를 grammar 와 sequence 의 alignment 로 생각할 수 있다. [HMM]에 대한 sequence 의 Viterbi alignment 가 sequence position 의 HMM states 에 대한 assignment 인 것과 같이, grammar를 가지고 sequence 를 parse 하는 것은 본질적으로 sequence position 의 grammar nonterminal 에 대한 assignment 이다.

ChomskyHierarchy and Automata

Stochastic Grammar

어떤 diverse 한 ProteinFamily에서 discriminative [PROSITE] pattern을 만드는 것이 불가능함이 증명되었다. 논리적인 해결책은 예외를 인정하는 것이다. 그러나 모든 가능성을 동등하게 하는 대신에, consensus 에 대한 strong match 보다 예외에 낮은 score를 준다.

이 idea 는 sequence [Profile]과 [HMM]과 같은 stochastic (probabilistic) Regular Grammar로 이르게 한다.

• StochasticRegularGrammar

• StochasticContextFreeGrammar

SeeAlso TransformationalGrammar