본문 바로가기

Library

B-트리 용어의 유래 .... 기초적인 B-트리(tree) 알고리즘의 변형과 성능을 논하기 이전에, B-트리 용어를 좀 더 형식적으로 기술하는 것이 필요하다. 차수(order)나 리프(leaf) 등과 같은 용어의 철저한 정의를 제공하는 것은 B-트리로 구분되기 위해 자료구조가 지녀야만 하는 성질을 설명할 수 있도록 한다. 다시 말해, B-트리의 성질에 대한 이러한 정의는 B-트리로부터 키를 삭제하는 절차와 같은 문제에 대한 논의를 할 수 있도록 한다. 불행하게도, B-트리에 관한 문헌은 B-트리와 관련된 용어를 이용하는데 있어 동일하지 않다. 그러므로 문헌을 읽고 새로운 개발을 하는 것은 약간의 융통성과 예비 지식을 필요로 한다. 독자는 기본적인 용어의 다른 사용에 대해서도 알 필요가 있다. 예를 들어, Bayer와 McCr.. 더보기
Gibbs Sampling 모티프(Motif)란 DNA, RNA, Protein 어떤 것의 조각이든, 비교적 반복적으로 나타나는 아주 짧은 서열 조각을 말한다. Regulatory Motif의 특징으로, 작고(tiny), 변화가 심하며(highly variable), 서로 거의 비슷한 크기에(constant size) 아주 빈번하게 나타난다. 이 작은 서열 조각은, 다중 서열 정렬을 하는데 아주 중요한 역할을 한다. 일반적으로, 다중 서열 정렬에 관한 문제는 다이나믹 프로그래밍(Dynamic Programming)을 적용하더라도 매우 어려운 문제로 알려져 있다. 어느 정도의 시간이 필요한지, 이것을 효과적으로 계산할 수 있는 다항시간 내의 알고리즘이 존재하는지 여부조차 알 수 없는, NP 문제에 속한다. 그런데, 모티프를 이용하면.. 더보기
CpG Island 일반적으로 각각의 뉴클리오타이드(nucleotide)가 나타날 확률은 이론상으로 1 / 4이다. 만약, 2개씩의 뉴클리오타이드가 짝 지어 존재해야 한다면 그 경우의 수는 4^2 = 16이며, 3개씩 뉴클리오타이드가 짝 지어져서 존재해야 한다면 4^3 = 64이다. 그렇지만, 실제로 각각의 뉴클리오타이드들이 나타날 확률은 동일하지 않다. 즉, 실제로 CG 서열은 상당히 낮은 빈도로 출현하는데, 진핵 생물체에서 CG 서열은 TG 서열로 변경되는 경우가 있기 때문이다. 특히, C-G 쌍으로 이루어진 뉴클리오타이드 짝이 아니라 그냥 인접해있는 경우를 관찰할 수 있는데, 이 CG 서열은 서로 연관된 두 가닥의 DNA 서열의 상보적인 짝이 아니다. 이들은 특히 프로모터(promotor) 주변에 많이 존재하며, 이것.. 더보기
Gene Finding과 HMM Advantage and Disadvantage Hidden Markov Model(HMM)를 응용하면 유전자의 서열을 정렬하는 문제에도 적용할 수 있다. 서열을 정렬하는 문제에 HMM을 적용하기 위해서는 여기에 맞는 모델(Model)을 정의해야 하는데, 모델을 정의하기 위해서는 특정 상태에서 심벌(symbol)을 방출할 확률, 상태 사이의 변환 확률을 알고 있어야 한다. 그리고, 여기서도 기존의 서열 정렬에 사용되었던 다이나믹 프로그래밍(Dynamic Programming)이 적용될 수 있다. 즉, 2개의 서열을 정렬한다면, 가장 가능성이 높은 정렬 상태를 찾아야 하며, 이것은 HMM 문제로 변환할 수 있다. 예를 들어 어떤 유전자 서열 _ATTGTA_GC라는 것과 TAATGTAACC가 주어졌다고 했을 때, 이것을 어떻게 표현할 수 있을까? 간단하게.. 더보기
Hidden Markov Model 2 Hidden Markov Model(HMM)에는 중요한 세 가지 문제가 있는데, Evaluation Problem, Decoding Problem, Learning Problem이 그것이다. 각각의 문제에서는 주어지는 것과 찾아야 하는 것은 다음과 같다. 여기서 HMM m이란 것은, HMM을 구성하는 각 인자들이 주어졌다는 뜻이다. 1. Evaluation Problem GIVEN : HMM m, sequence x FIND : Prob[x | m] 2. Decoding Problem GIVEN : HMM m, sequence x FIND : sequence π of states that max Prob[x, π | m] 3. Learning Problem GIVEN : HMM m, unspecified.. 더보기
Integral and Simpson's Rule 어떤 함수가 주어졌고, 이 함수의 특정 구간에서의 정적분 값을 알고 싶다고 하자. 만약 함수의 방정식을 알고 있다면 함수의 적분 근사식을 얻어내어 그것을 계산하면 되지만, 여기서 적분을 구하고자 할 때 주어진 것은 이산적인 함수값 뿐이다. 따라서, 함수값을 가지고 이 넓이를 계산한다는 것은, 결국 이 함수값을 지나는 적절한 곡선의 방정식을 구해서 두 함수값 사이의 넓이를 구하는 것이라 할 수 있다. 이 넓이의 정확성은, 주어진 함수값을 지나는 선이 실제 함수와 얼마나 적절한지 여부에 달려 있다. 가장 단순하게, 이 넓이를 이루는 도형이 매우 작은 직사각형이라 가정할 수 있다. 그리고, 넓이는 증분 h와 함수값 f를 곱하고, 이들을 더해서 구할 수 있다. 이 방법을 가장 단순한, 1차 근사식이라 한다. 이.. 더보기
Hidden Markov Model 1 HMM(Hidden Markov Model)은 강력한 통계학적 분석 방법이다. HMM으로 해결할 수 있는 유형의 문제는 Evaluation Problem, Decoding Problem, Learning Problem 세가지이다. Hidden이라는 이름이 붙은 이유는, 관찰자는 오로지 특정 상태에서 방출되는 기호들을 관찰할 수 있을 뿐이며, 기호가 어떤 상태에서 방출된 것인지 알 수 없기 때문이다. (즉, HMM이 현재 어떤 상태인지 알 방법이 없다) 예를 들어, 카지노(Casino)에서 주사위 던지기 게임을 한다고 했을 때, 이 카지노의 딜러(Dealer)는 언제나 공정한 주사위를 사용하지 않는다고 하자. 딜러는 가중치가 적용된 주사위와 공정한 주사위를 번갈아가며 사용한다. 여기서 결과로 얻어진 시퀀스.. 더보기
Introduction to B-Tree 3 B-트리는 삽입과 삭제의 선형 비용 문제를 해결하는 다단계 인덱스이다. 이것이 B-트리가 좋은 이유이고, 인덱스를 표현하는 표준 방법이 된 이유이다. 해결 방법은 두 부분으로 나뉜다. 첫 번째는 가득 차게 될 인덱스 레코드를 요구하지 않는다. 두 번째는 다음 레코드로 오버플로우(overflow) 키를 넘기지 않는다. 대신 초과되는 레코드를 두개의 인덱스 레코드로 각각 반씩 나눈다. 삭제는 필요할 때 인덱스를 하나의 레코드로 합치는 전략을 취한다. B-트리의 각각의 노드는 인덱스 레코드이다. 이 레코드의 각각은 B-트리의 차수(order)라고 불리는 키-참조 쌍의 최대수를 가질 수 있다. 또한 보통 차수의 반인 최소소의 키-참조 쌍을 가질 수 있다. 차수가 100인 B-트리는 레코드 당 최소 50개의 키와.. 더보기
Introduction to B-Tree 2 효율적인 트리(tree) 구조를 유지하는데 가장 큰 문제는, 최적의 트리 탐색 성능을 제공하기 위해서 트리는 정렬된 상태로, 균형 트리를 이루어야 한다는 것이다. 그러나 트리의 균형을 잡는 연산은 매우 비싸다. 이진 트리가 이상적인 상태를 유지한다고 하더라도, 이진 탐색은 디스크 상주 인덱싱에 비해서 그다지 빠르지 않다. 트리가 최적의 탐색 성능을 제공하기 위해서는, 트리는 균형을 이루어야 하는데, 이것은 가능한 한 루트에서 가장 끝에 위치한 각각의 노드까지 경로가 최대한 비슷해야 한다는 것을 의미한다. 즉, 트리가 최악의 성능을 보이는 경우는 일렬로 노드가 연속되어 붙어 있을 때이며, 이 경우 사실 트리라기보다는 리스트에 더 가깝다. 역사적으로 트리를 균형 상태로 유지하기 위해 AVL 트리나, 페이지화.. 더보기
Introduction to B-Tree 1 가변 길이 레코드 집합을 탐색하기 위해 인덱스(index)를 사용하는 것은 효과적인 기법이다. 그러나, 문제는 인덱스 전체를 메모리에 올릴 수 없는 경우이다. 이 문제를 해결하기 위해, 1972년 Bayer와 McCreight가 발표한 논문의 처음 몇 단락을 보기로 하자. 여기에서는 그들이 B-트리(B-Tree)로서 해결하고자 했던 문제, 즉 메모리로 적재하기에는 너무 큰 인덱스의 접근과 유지에 관한 방법에 대해 간결하게 설명하고 있다. .... 이 논문에서는 동적으로 변화하는 임의 접근 파일(random access file)을 위해서 인덱스를 구성하고 유지하는 문제에 관해 고찰한다. 여기서 인덱스라 함은 물리적으로 인접한 고정된 크기의 두 데이터 항목, 즉 키(key) x와 관련 정보 a가 갈협하여 .. 더보기

티스토리툴바