DNA, RNA 또는 단백질 서열에서 발생하는 서열의 재배열 현상과 분자 간 상호결합에 의해 발생하는 서열의 이차구조 결합 현상을 모델링하여 정형 언어 대상의 바이오 연산자(Bio-inspired operation)를 정의한다. 유전 서열에서 발생하는 비정상적인 재배열(Rearrangement)과 이차구조(Secondary Structure)) 접힘 현상은 생물의 세포 생성과 작용에 대한 정보를 지니고, 염색체 돌연변이 예방, 탐지를 위한 중요한 정보로 사용되기때문에 유전 서열을 분석하는 연구는 생물학 분야 뿐만아니라 정형 언어 이론에서도 중요한 연구 중 하나로 분류된다. 우리는 실제 유전 서열에서 발생하는 비정상적인 서열 재배열과, 실험실에서 인위적으로 비정상적인 재배열을 조합하는 방법 중 하나인 중합 효소 연쇄반응(Polymerase Chain Reaction)을 문자열 대상의 바이오 연산자로 정형화하고, 정형 언어적 특성 분석을 수행하였다. 비정상적인 서열 재배열 현상의 정형 언어 이론 기반 모델링과 특성 분석 연구는 해당 현상이 100\% 발생한다는 가정에 기반하여 수행되었다. 하지만, 실제 염기 서열에서는 뉴클리오티드(Nucleotide) 간 결합 오류와 실험 환경에 따라 예상치 못한 오류가 발생하기때문에 효율적인 유전 서열 분석을 위해 오류를 고려한 모델링이 필요하다. 우리는 완전하게 발현하지않은 ...
DNA, RNA 또는 단백질 서열에서 발생하는 서열의 재배열 현상과 분자 간 상호결합에 의해 발생하는 서열의 이차구조 결합 현상을 모델링하여 정형 언어 대상의 바이오 연산자(Bio-inspired operation)를 정의한다. 유전 서열에서 발생하는 비정상적인 재배열(Rearrangement)과 이차구조(Secondary Structure)) 접힘 현상은 생물의 세포 생성과 작용에 대한 정보를 지니고, 염색체 돌연변이 예방, 탐지를 위한 중요한 정보로 사용되기때문에 유전 서열을 분석하는 연구는 생물학 분야 뿐만아니라 정형 언어 이론에서도 중요한 연구 중 하나로 분류된다. 우리는 실제 유전 서열에서 발생하는 비정상적인 서열 재배열과, 실험실에서 인위적으로 비정상적인 재배열을 조합하는 방법 중 하나인 중합 효소 연쇄반응(Polymerase Chain Reaction)을 문자열 대상의 바이오 연산자로 정형화하고, 정형 언어적 특성 분석을 수행하였다. 비정상적인 서열 재배열 현상의 정형 언어 이론 기반 모델링과 특성 분석 연구는 해당 현상이 100\% 발생한다는 가정에 기반하여 수행되었다. 하지만, 실제 염기 서열에서는 뉴클리오티드(Nucleotide) 간 결합 오류와 실험 환경에 따라 예상치 못한 오류가 발생하기때문에 효율적인 유전 서열 분석을 위해 오류를 고려한 모델링이 필요하다. 우리는 완전하게 발현하지않은 역위 현상을 모델링한 유사-역위(Pseudo-Inversion) 연산자와 최대 k개의 오류의 발생을 허용한 유사-복제(Pseudo-Duplication) 연산자를 정의한다. 또한, 단백질 합성을 위한 정보를 지닌 엑손(Exon)서열에서 발생하는 복제 현상을 모델링한 내포복제(Nested Duplication)연산자를 정의한다. 세 연산자는 실제 자연 현상에서 발생 가능한 오류를 고려한 현실적인 모델링으로써 세포 작용 및 새대를 거쳐 발현하는 현상의 시뮬레이션에 적용가능하고, 유전 서열 분석 실험을 위한 효율적인 기법 개발에 용이하다. 우리는 유전 서열을 대상으로 실험실에서 사용되는 중합 효소 연쇄 반응 기반의 위치 지정 돌연변이(Site-Directed Mutagenesis) 생성 기법을 바이오 연산자로 정형화한다. 위치 지정 돌연변이랑 돌연변이의 발생 과정과 원인을 분석하기위해 효소 작용을 이용하여 인위적으로 특정 위치에 돌연변이를 만드는 기법으로, 우리는 유사 매듭 구조(Pseudoknot Structure)와 위치 지정 삽입/삭제(Site-Directed Insertion/Deletion) 현상을 유사 매듭 생성(Pseudoknot-Generating) 연산자와 위치 지정 삽입/삭제 연산자로 정형화한다. 유사 매듭 생성 연산자는 주어진 문자열을 시작으로 발생가능한 모든 유사 매듭 형태의 문자열 집합을 생성한다. 위치 지정 삽입/삭제 연산자는 두 문자열을 대상으로, 해당 문자열의 부분 서열이 표현하는 특정 위치에 부분 문자열을 삽입/삭제한다. 정의한 바이오 연산자를 대상으로 춈스키 계층(Chomsky Hierarchy)에서의 닫힘 특성(Closure Property) 분석을 수행하고, 바이오 연산자를 고려한 결정 문제(Decision Problem)에 대한 효율적인 알고리즘 설계 연구를 수항한다. 닫힘 특성 분석을 통해 바이오 연산자가 적용된 정형 언어의 표현 능력을 파악할 수 있고, 정형 언어 표현 장치를 활용한 효율적인 분석 기법 설계 가능하다. 우리는 정규 언어(Regular Languages)가 유사-역위 연산자와 위치 지정 삽입/삭제 연산자에 닫혀있고, 유사-복제 연산자와 유사 매듭 구조 생성 연산자에 닫혀있지 않음을 보인다. 문맥 자유 언어(Context-Free Languages)는 모든 바이오 연산자에 닫혀있지 않다. 또한, 우리는 주어진 정규 언어와 바이오 연산자가 적용된 정형 언어 간 자유도(Freeness Problem) 문제의 결정가능성을 보이고, 문맥 자유 언어의 경우 결정 불가능 함을 증명한다. 우리는 주어진 문자열이 유사 매듭 구조인지 선형 시간에 판단 가능하고, 주어진 문자열을 대상으로 위치 지정 삽입/삭제의 발생 가능성을 다항 시간에 판단 가능함을 보인다. 마지막으로, 바이오 연산자가 적용된 정형 언어의 상태 복잡도(State Compexity)와 표현력(Capacity)을 계산한다.
DNA, RNA 또는 단백질 서열에서 발생하는 서열의 재배열 현상과 분자 간 상호결합에 의해 발생하는 서열의 이차구조 결합 현상을 모델링하여 정형 언어 대상의 바이오 연산자(Bio-inspired operation)를 정의한다. 유전 서열에서 발생하는 비정상적인 재배열(Rearrangement)과 이차구조(Secondary Structure)) 접힘 현상은 생물의 세포 생성과 작용에 대한 정보를 지니고, 염색체 돌연변이 예방, 탐지를 위한 중요한 정보로 사용되기때문에 유전 서열을 분석하는 연구는 생물학 분야 뿐만아니라 정형 언어 이론에서도 중요한 연구 중 하나로 분류된다. 우리는 실제 유전 서열에서 발생하는 비정상적인 서열 재배열과, 실험실에서 인위적으로 비정상적인 재배열을 조합하는 방법 중 하나인 중합 효소 연쇄반응(Polymerase Chain Reaction)을 문자열 대상의 바이오 연산자로 정형화하고, 정형 언어적 특성 분석을 수행하였다. 비정상적인 서열 재배열 현상의 정형 언어 이론 기반 모델링과 특성 분석 연구는 해당 현상이 100\% 발생한다는 가정에 기반하여 수행되었다. 하지만, 실제 염기 서열에서는 뉴클리오티드(Nucleotide) 간 결합 오류와 실험 환경에 따라 예상치 못한 오류가 발생하기때문에 효율적인 유전 서열 분석을 위해 오류를 고려한 모델링이 필요하다. 우리는 완전하게 발현하지않은 역위 현상을 모델링한 유사-역위(Pseudo-Inversion) 연산자와 최대 k개의 오류의 발생을 허용한 유사-복제(Pseudo-Duplication) 연산자를 정의한다. 또한, 단백질 합성을 위한 정보를 지닌 엑손(Exon)서열에서 발생하는 복제 현상을 모델링한 내포복제(Nested Duplication)연산자를 정의한다. 세 연산자는 실제 자연 현상에서 발생 가능한 오류를 고려한 현실적인 모델링으로써 세포 작용 및 새대를 거쳐 발현하는 현상의 시뮬레이션에 적용가능하고, 유전 서열 분석 실험을 위한 효율적인 기법 개발에 용이하다. 우리는 유전 서열을 대상으로 실험실에서 사용되는 중합 효소 연쇄 반응 기반의 위치 지정 돌연변이(Site-Directed Mutagenesis) 생성 기법을 바이오 연산자로 정형화한다. 위치 지정 돌연변이랑 돌연변이의 발생 과정과 원인을 분석하기위해 효소 작용을 이용하여 인위적으로 특정 위치에 돌연변이를 만드는 기법으로, 우리는 유사 매듭 구조(Pseudoknot Structure)와 위치 지정 삽입/삭제(Site-Directed Insertion/Deletion) 현상을 유사 매듭 생성(Pseudoknot-Generating) 연산자와 위치 지정 삽입/삭제 연산자로 정형화한다. 유사 매듭 생성 연산자는 주어진 문자열을 시작으로 발생가능한 모든 유사 매듭 형태의 문자열 집합을 생성한다. 위치 지정 삽입/삭제 연산자는 두 문자열을 대상으로, 해당 문자열의 부분 서열이 표현하는 특정 위치에 부분 문자열을 삽입/삭제한다. 정의한 바이오 연산자를 대상으로 춈스키 계층(Chomsky Hierarchy)에서의 닫힘 특성(Closure Property) 분석을 수행하고, 바이오 연산자를 고려한 결정 문제(Decision Problem)에 대한 효율적인 알고리즘 설계 연구를 수항한다. 닫힘 특성 분석을 통해 바이오 연산자가 적용된 정형 언어의 표현 능력을 파악할 수 있고, 정형 언어 표현 장치를 활용한 효율적인 분석 기법 설계 가능하다. 우리는 정규 언어(Regular Languages)가 유사-역위 연산자와 위치 지정 삽입/삭제 연산자에 닫혀있고, 유사-복제 연산자와 유사 매듭 구조 생성 연산자에 닫혀있지 않음을 보인다. 문맥 자유 언어(Context-Free Languages)는 모든 바이오 연산자에 닫혀있지 않다. 또한, 우리는 주어진 정규 언어와 바이오 연산자가 적용된 정형 언어 간 자유도(Freeness Problem) 문제의 결정가능성을 보이고, 문맥 자유 언어의 경우 결정 불가능 함을 증명한다. 우리는 주어진 문자열이 유사 매듭 구조인지 선형 시간에 판단 가능하고, 주어진 문자열을 대상으로 위치 지정 삽입/삭제의 발생 가능성을 다항 시간에 판단 가능함을 보인다. 마지막으로, 바이오 연산자가 적용된 정형 언어의 상태 복잡도(State Compexity)와 표현력(Capacity)을 계산한다.
Bio-inspired operation is characterized by biological phenomena on gene sequences such as deoxyribonucleic acid (DNA), ribonucleic acid (RNA) and protein sequence from formal language viewpoint. Gene sequences present the functions of living organism, thus, analyzing gene sequences is one of the imp...
Bio-inspired operation is characterized by biological phenomena on gene sequences such as deoxyribonucleic acid (DNA), ribonucleic acid (RNA) and protein sequence from formal language viewpoint. Gene sequences present the functions of living organism, thus, analyzing gene sequences is one of the important research topics in both molecular biology and formal language theory. We define bio-inspired operations on strings motivated from abnormal gene rearrangements and enzymatic activities and analyze their theoretical properties. The goal of thesis is modeling abnormal biological phenomenon more generally so that the result helps experiment in practice. First, we introduce the pseudo-inversion, pseudo-duplication and nested duplication operations, roughly speaking, the variants of inversion and duplication which are well-known operations in both formal language theory and molecular genetics. The pseudo-inversion operation on a string reverses only the outermost part of the string, meanwhile, the middle part of the string is not reversed, which implies that an ordinary inversion operation occurs with incompletely. The pseudo-duplication operation on a string is a process of copying a substring allowing errors at most k. The nested duplication has restrictions on position and the maximum size of the duplication segment, which is motivated from exon duplication in molecular biology that duplicates a segment within a current exon. Second, we characterize the pseudoknot-generating, site-directed insertion and site-directed deletion operations from a procedure of enzymatic activities called site-directed mutagenesis. The pseudoknot-generating operation generates all possible strings of pseudoknot structure, which is a crucial intra-molecular structure related to hepatitis C virus (HCV), from a given string x. Given two strings x and y, the site-directed insertion operation partially inserts a substring u to x guided by y, and the site-directed deletion operation partially removed a substring u from x guided by y. We mainly study closure property of the families in the Chomsky hierarchy under the bio-inspired operations and \emph{decidability} with respect to the bio-inspired operations. First, we show that regular languages are closed under pseudo-inversion, site-directed insertion and site-directed deletion, whereas it is not closed under pseudo-duplication and pseudoknot-generating. Context-free languages are not closed under all bio-inspired operations. We establish that the iterated pseudo-inversion of context-free language is recognized by a nondeterministic reversal-bounded multicounter machine. Furthermore, regular languages are closed under site-directed insertion and deletion, whereas it is not when L is context-free. Second, we consider freeness problem on formal languages, which implies the question of determining whether or not a language L has no string that exists in both L and L' where L' obtained by the bio-inspired operation. Then, we design polynomial-time algorithms for regular languages and demonstrate undecidability result for context-free languages. Furthermore, we consider several decidability problems over pseudoknot-generating, site-directed insertion and site-directed deletion. We design an linear time algorithm that decides whether or not a given string is a pseudoknot of a regular language L. In addition, for given two string x and y, we design an linear time algorithm that determines whether or not y is an insertion guide of x (respectively, y is a deletion guide of x). We present an linear time algorithm for membership problem with respect to the site-directed deletion operation. Lastly, we compute descriptional complexity of bio-inspired operations that measures the size of a finite automaton. We show that there exists a nondeterministic finite automaton (NFA) recognizing all duplications---duplication, k-pseudo-duplication and reverse-duplication---of a string and present the necessary and sufficient number of states of NFA. We estimate generative power of nested duplication operation that is repeatedly applied to an initial string. We present an NFA construction for nested duplications on a string and compute the generative power using the Perron-Frobenius theory.
Bio-inspired operation is characterized by biological phenomena on gene sequences such as deoxyribonucleic acid (DNA), ribonucleic acid (RNA) and protein sequence from formal language viewpoint. Gene sequences present the functions of living organism, thus, analyzing gene sequences is one of the important research topics in both molecular biology and formal language theory. We define bio-inspired operations on strings motivated from abnormal gene rearrangements and enzymatic activities and analyze their theoretical properties. The goal of thesis is modeling abnormal biological phenomenon more generally so that the result helps experiment in practice. First, we introduce the pseudo-inversion, pseudo-duplication and nested duplication operations, roughly speaking, the variants of inversion and duplication which are well-known operations in both formal language theory and molecular genetics. The pseudo-inversion operation on a string reverses only the outermost part of the string, meanwhile, the middle part of the string is not reversed, which implies that an ordinary inversion operation occurs with incompletely. The pseudo-duplication operation on a string is a process of copying a substring allowing errors at most k. The nested duplication has restrictions on position and the maximum size of the duplication segment, which is motivated from exon duplication in molecular biology that duplicates a segment within a current exon. Second, we characterize the pseudoknot-generating, site-directed insertion and site-directed deletion operations from a procedure of enzymatic activities called site-directed mutagenesis. The pseudoknot-generating operation generates all possible strings of pseudoknot structure, which is a crucial intra-molecular structure related to hepatitis C virus (HCV), from a given string x. Given two strings x and y, the site-directed insertion operation partially inserts a substring u to x guided by y, and the site-directed deletion operation partially removed a substring u from x guided by y. We mainly study closure property of the families in the Chomsky hierarchy under the bio-inspired operations and \emph{decidability} with respect to the bio-inspired operations. First, we show that regular languages are closed under pseudo-inversion, site-directed insertion and site-directed deletion, whereas it is not closed under pseudo-duplication and pseudoknot-generating. Context-free languages are not closed under all bio-inspired operations. We establish that the iterated pseudo-inversion of context-free language is recognized by a nondeterministic reversal-bounded multicounter machine. Furthermore, regular languages are closed under site-directed insertion and deletion, whereas it is not when L is context-free. Second, we consider freeness problem on formal languages, which implies the question of determining whether or not a language L has no string that exists in both L and L' where L' obtained by the bio-inspired operation. Then, we design polynomial-time algorithms for regular languages and demonstrate undecidability result for context-free languages. Furthermore, we consider several decidability problems over pseudoknot-generating, site-directed insertion and site-directed deletion. We design an linear time algorithm that decides whether or not a given string is a pseudoknot of a regular language L. In addition, for given two string x and y, we design an linear time algorithm that determines whether or not y is an insertion guide of x (respectively, y is a deletion guide of x). We present an linear time algorithm for membership problem with respect to the site-directed deletion operation. Lastly, we compute descriptional complexity of bio-inspired operations that measures the size of a finite automaton. We show that there exists a nondeterministic finite automaton (NFA) recognizing all duplications---duplication, k-pseudo-duplication and reverse-duplication---of a string and present the necessary and sufficient number of states of NFA. We estimate generative power of nested duplication operation that is repeatedly applied to an initial string. We present an NFA construction for nested duplications on a string and compute the generative power using the Perron-Frobenius theory.
주제어
#bio-inspired operations formal languages closure property decidability state complexity capacity 바이오 연산자 정형 언어 닫힘 특성 결정가능성 상태 복잡도 표현력
학위논문 정보
저자
조다정
학위수여기관
Graduate School, Yonsei University
학위구분
국내박사
학과
Department of Computer Science
지도교수
Yo-Sub Han
발행연도
2018
총페이지
viii, 161 p.
키워드
bio-inspired operations formal languages closure property decidability state complexity capacity 바이오 연산자 정형 언어 닫힘 특성 결정가능성 상태 복잡도 표현력
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.