본 내용은 내 동료 Jorg의 diploma thesis의 내용 중 일부를 번역한 것이다.
그래프 구조
이전에 설명했듯이, 지놈 서열은 블록들에 저장된다. 여러 개의 블록으로 분기해 확장되어나가는 서열들을 검색하기 위해서, 연결되어 있는 블록들에 대한 연결 정보를 가지고 있어야 한다. 이런 목적으로, 각 블록 테이블 요소는 양 인접한 블록들의 블록 수를 저장한다. 그런 까닭에, 이 구조는 그래프로 해석될 수 있다. 각 블록은 정점(vertex)으로, 그리고 그 연결은 에지(edge)로 해석된다. 지놈은 이제 염기 문자열들을 포함하고 있을 뿐 아니라, 서로 연결된 블록의 문자열들을 포함하고 있다(그림 2.3 (A)).
그림 2.3. 블록들을 포함하는 그래프 구조로 각 블록은 최대 256개의 염기를 저장한다. (A) 단일 참조 지놈은 단지 블록들(노드들)이 서로 연결된 순서쌍으로 표현된다. (B) 다른 종류의 계통 서열 정보와 함께, 순차적인 순서는 버려진다. 참조 서열과 계통 서열 사이의 갈라지는 서열을 포함하는 분기(branch)들이 보인다(단일 계통의 수퍼블록의 블록 서열). "계통 연결(strain links)"에 의해 연결된 블록들은 하나 이상의 외향(혹은 내향)의 에지를 가진다.
이 간단한 그래프 구조는 추가적인 계통 지놈과의 통합으로 더 복잡해진다. 계통 서열 중에 참조 서열과 다르게 분기하는 서열을 가질 때마다, 병렬의 블록 문자열들이 시작되어야 한다. 이 블록들의 연결을 "분기(branch)"라고 부르고, 한 분기를 포함하는 모든 블록들의 축적을 "수퍼블록"이라고 부를 것이다. 두 수퍼블록들 사이에 정렬된 블록들을 "보존 블록들"이라고 부르며 모든 계통들 사이에서 참조와 동일한 서열들을 보존하고 있는 블록들을 포함하기 때문이다(그림 2.3 (B)).
그런 까닭에, 추가적인 에지들은 다른 계통 서열들을 서로 연결해가며 생성되어햐 한다. 다른 계통에 인접한 블록들의 블록 숫자를 저장하는 두 개의 정수를 예비해 둠으로써 블록 테이블은 만약 다른 계통에 인접한 블록들이 있을 때 추가적인 에지가 연결되어질 수 있도록 해준다. 오직 맨 처음고 맨 마지막에 있는 분기의 블록이 수퍼 블록에 있는 다른 계통의 맨 처음과 맨 마지막 블록을 각각 "가리켜야" 한다(그림 2.3에 있는 계통 연결(strain links). 대부분의 모든 블록들은 이 정수들을 사용하지 않는다. 그러나 그럼에도 불구하고 이 8 바이트를 이런 방법으로 사용하는 것이 가장 공간 효율적인 방식이다. 만약 이웃 리스트가 유연하게 유지되려면, 최소한 인접 블록들의 구조를 가리키는 한 개의 포인터가 필요하고, 이 한 포인터는 포인터 자체만으로 8 바이트의 공간을 차지할 것이다(64 비트 운영체제의 경우). 만약 계통 서열이 한 개 블록 이상을 차지할 경우 오직 한 블록만을 포함한 분기가 두 다른 계통 블록들을 가리켜야 할 수도 있기 때문에, 두 포인터가 별개로 저장되어야 한다.
블록 테이블의 설계가 암시하는 것은 새로운 염색체가 시작할 때마다 새로운 블록이 생성되어야 한다는 것을 암시하고, 이는 블록 테이블 안의 염색체 정보가 변하기 때문이다. 염색체들 사이의 블록들은 연결되어있지 않고 염색체 당 하나의 그래프를 생성하게 된다.
분기하기
분기 지점은 참조의 첫 씨드 중 계통 서열에서는 다른 위치에 있겠지만, 계통 서열과 참조 서열 모두에 있는 씨드를 선택하는 방식으로 선정된다. 이 말은 브랜치의 서열이 두 서열 간의 차이를 포함하고 있을 뿐 아니라 다형성이 시작되는 위치의 왼쪽의 n-1 염기(씨드 길이가 n인 경우)를 포함하고 있다는 것을 의미한다. 예를 들어, 그림 2.3은 씨드 길이 3을 가정했고, 비록 SNP가 4번째 블록의 마지막 염기에서 나타나지만 첫 분기는 4번째 블록의 시작 부분에서 시작한다. 이것은 더더군다나 하위지역(downstream) 변이가 n 염기 보다 가까운 위치에서 발생할 때, 분기가 확장될 수 있음을 암시한다. 그림 2.3에서 계통 1의 삽입은 새로운 브랜치를 시작하지 않는데, 이것은 마지막 SNP(TCC) 다음의 씨드가 여전히 참조와 다르기 때문이다.
더욱이, 참조 블록들과 분기 블록들은 동시에 시작되어야 한다. 그래서 분기를 야기하는 첫 변이는 또한 분기 위치에서 참조 서열 안의 블록 쪼개짐을 야기할 것이다(그러나 더 존재하는 다형성은 참조 서열에서는 더이상 블록 쪼개짐을 야기하지 않는다). 그림 2.3을 다시 보자. 참조 서열의 5번째 블록은 그 블록의 위에 있는 서열 구조와 비교해서 1개의 염기가 적게 있다. 왜냐하면 이어지는 염기가 모든 계통 서열들에서 공유되고 있고, 그로 인해 이 이어지는 염기가 다음의 보존 블록을 구성하기 때문이다.
이런 동작은 모든 블록이 다른 블록들 안에 있는 특정한 위치를 가리키는 것 대신에 간단히 이웃 블록들을 가리킬 수 있도록 해주고, 또한 그래프로부터 서열을 추출하는 동안 한 블록 안의 모든 위치에서 분기가 시작되는지 아닌지 검사할 필요가 없도록 해준다. 그런 까닭에, 분기 지점의 검색은 오직 블록 쪼개짐의 위치에서만 수행되면 된다.
같은 목적으로, 병렬의 분기들은 동시에 종결 되어야 한다. 예를 들어, 참조 서열은 분기 종결 위치에서 새로운 블록을 시작해야 한다. 분기 안에서 모든 계통은 그 자신의 블록 쪼개짐을 가질 수 있다.
이러한 동작은 중복되는 정보를 저장할 수도 있게 만든다. 왜냐하면 모든 계통은 SNP, indel과 같은 변이들 사이에서 동일하게 확장된 구조를 가진 매우 유사한 서열들을 저장하고 있기 때문이다. 가령 심하게 안 좋은 경우를 생각해 보면, 다른 계통 서열의 긴 분기에 의해서 모델링된 영역에 오직 약간의 변이만 있는(가령 하나의 염기만 다른 경우) 한 계통 서열이 있는 경우라도 우리는 전체 분기 서열을 저장해야할 필요가 있다. 하지만, 여기에서 사용한 접근법은 구현을 쉽게 만들고, 오직 실제 다른점이 있는 부분에 대해서 이해하고 저장하는 것은 어떤 계통으로부터 한 씨드가 나왔는지 분간하는데 아무런 도움을 주지 못할 것이다. 게다가 어떤 계통에서 해당 씨드가 확장될 수 있는 지 결정하는 것을 불가능하게 만든다. 더 나아가, 한 씨드가 오직 한 계통으로 부터 나온 염기들을 구성하는데 이용되었는지 여부와 다른 계통들과 아무런 연결이 발생하지 않았는지를 확인해야 하는 추가적인 작업이 필요하게 된다.
분기 안에서 블록 쪼개기
각 블록은 참조 서열에 정렬된 것으로 고려될 수 있다. 왜냐하면, 그것은 참조 지놈에서 그것의 시작 위치를 저장하고 있기 때문이다. 그런 까닭에, 블록에 저장된 염기들도 동시에 정렬되게 된다. 하지만, 계통 서열들에서 indel이 합쳐짐으로 이 염기 대 염기 정렬은 방해를 박데 된다. 왜냐하면 indel은 블록 시작 위치에 대한 차후의 염기의 오프셋을 변경하기 때문이다.
그런 까닭에, 블록 쪼개기는 다른 계통에 아무런 영향도 주지 않은 채로 모든 삽입과 삭제 후에 계통 분기의 안에서 일어나야 한다. 이는 새로운 블록을 시작하는 것은 블록을 참조 서열에 대해 정렬하는 것에 관해서 블록의 새로운 시작 위치를 저장하도록 하기 때문이다.
이것은 블록 테이블 안의 indel 오프셋(2 바이트)와 삽입 위치(4 바이트)의 두 변수를 모든 블록에 저장함으로써 구현될 수 있다.
하나의 삽입으로 종결되는 블록은 앞으로 "삽입 블록"이라고 부를 것이고, 하나의 삭제로 종결되는 블록은 앞으로 "종결 블록"이라고 부를 것이다.
삽입 블록에서, indel 오프셋은 블록 안에서 삽입이 시작되는 위치(1로 시작되는)를 나타낸다. 이 정보를 가지고, 하나의 삽입된 영역에 매핑되는 시작 위치를 가지는 리드는 참조 서열에서 마지막 염기의 위치에 대한 정보를 가지게 된다. 삭제 블록에서 이 변수는 삭제된 길이 + 1의 값을 저장한다. 삽입과 삭제의 블록을 구분하기 위해서 삭제 블록의 경우 음수의 값이 저장된다. 매핑 프로그램을 위한 이 정보의 기능은 서열을 추출하는 동안 삭제 영역들을 "건너 뛰기"할 수 있다는 점이다. 그래서 우리가 관심이 있는 실제 서열 자체에는 아무런 기여도 하지 않은 긴 삭제된 영역이 나타나더라도 이를 순회할 필요가 없어진다.
삽입 위치 변수는 오직 긴 삽입된 영역들을 위해서만 사용된다. 가령 256 염기보다 더 길게 삽입된 영역은 1 블록 이상에 저장되어야 한다. 오직 삽입된 염기들만을 포함하는 블록들은 마지막으로 정렬된 참조 서열의 염기의 왼쪽 방향에 있는 위치와 마찬가지로 그 지점까지의 오프셋을 알지 못한다. 삽입 위치 변수는 마지막으로 매칭된 참조 서열의 위치로 부터 블록의 시작 위치 오프셋을 저장함으로써 이를 해결한다.
참조 서열과 차이가 없는 염기만을 가지고 있는 블록이나 오직 SNP들 만을 가지고 있는 블록은 indel 오프셋과 삽입 위치 변수가 사용되지 않고 0으로 초기화 된다.
블록 테이블
여기에서 소개한 그래프 구조는 블록 테이블에 의해서 완전히 설명된다. 모든 계통의 완전한 지놈들이 복원될 수 있는 모든 정보가 이 블록 테이블 구조에 저장된다. 더군다나, 이것은 각 계통 별로 전체 지놈 정렬에 대한 정보와 정확한 위치 정보를 저장한다. 요약하자면, 블록 테이블 변수와 설명이 표 2.1에 있다.
표. 2.1. 시퀀스 그래프에서 블록 테이블 표현
변수 이름 |
바이트 |
설명 |
| pos | 4 |
참조 서열에서 블록의 시작 위치 |
| strainpos | 4 |
계통 서열에서의 블록의 시작 위치 |
| chr | 4 |
염색체 |
| strain | 4 |
계통 |
| indel_offset | 2 |
삽입의 시작 오프셋 또는 삭제의 길이 + 1의 음수 값 |
ins_pos |
4 |
왼쪽에 있는 첫 일치 염기까지의 시작 오프셋 |
seq |
256 |
인코딩된 시퀀스 |
| prev_block | 4 |
이전 블록의 블록 번호 |
| next_block | 4 |
다음 블록의 블록 번호 |
| next_strain_front | 4 |
오직 첫 분기 블록에만 있음: 다음 계통의 첫 블록의 블록 번호 |
next_strain_end |
4 |
오직 마지막 분기 블록에만 있음: 다음 계통의 마지막 블록의 블록 번호 |
전체 바이트 수 |
294 |
결과적으로 만약 모든 블록이 필요할 때, 블록 테이블에 대해 최대 공간 요구사항은 
그래프 생성
이제 프로그램에서 블록 테이블이 어떻게 그래프를 표현하는지 설명했으므로, 다음 단계는 어떻게 블록 테이블이 채워지는 지를 볼 차례이다. 즉, 어떻게 그래프가 생성되는 지 살펴 보자.
프로그램은 각 염색체 별로 별개로 동작한다. 먼저, 한 염색체 서열이 읽어진다. 다음에 각 게통 서열들의 편집 연산들이 메모리 상의 쌍방향 리스트(snindels라 불림)로 로딩된다. 이와 동시에 각 계통의 오직 한 snindel이 저장된다.
"snindels"는 SNP와 삽입, 삭제를 모두 조합해서 만든 단어이다. 즉, 편집 연산을 뜻한다.
단일 snindels는 가장 왼쪽에 돌연변이 위치가 있도록 정렬된다. 예를 들어, snindel이 가장 앞의 위치에 있는 경우 리스트의 앞에 있게 된다. 이 리스트의 첫 snindel이 추출될 때마다, 특정 계통의 입력 파일의 다음 snindel이 로딩되고, 현재 처리 중인 염색체에서의 위치에 따라서 정렬된다. 이런 방법으로 염색체와 입력 계통 파일들을 딱 한번씩만 처리할 수 있고, 부가적으로 각 계통의 다음 snindel과 모든 계통의 가장 왼쪽에 있는 snindel에 상수 시간에 접근할 수 있게 된다.
snindels 리스트에 있는 첫 snindel은 첫 분기 지점을 결정한다. 이 위치까지, 모든 계통들과 참조 서열들은 동일한 서열을 가지고, 이 시퀀스를 저장하기 위해 필요한 블록들이 생성된다. 분기 지점에 이르면, 수퍼 블록과 그것의 다음의 보존 블록이 그림 2.4의 방법으로 생성된다.
모든 브랜치에 대해서, 한 서열 변수가 생성된다. 그것은 첫 블록이 쪼개지기 전까지(가령, indel의 위치 또는 분기 종결 위치) 분기 서열을 저장할 것이다. 분기는 이어지는 두 snindels 사이에서 한 조각 다음에 다른 조각 방식으로 채워지게 된다. 먼저, 마지막과 실제 snindel 사이에 있는 참조 서열 분기 서열로 복사가 된다. 다음에 갈라지는 snindel 서열은 인코딩 되는 방식으로 붙여지게 된다.
다음의 snindels 리스트로부터 다음의 snindel이 로딩되고, 가장 마지막 snindel까지의 위치의 차이가 계산된다. 씨드 길이 보다 짧고, 계통에 독립적이며, 마지막 snindel과 동일한 계통에 있는 브랜치라면 확장되게 된다. 그렇지 않으면, 분기의 시작점에서부터 새로운 계통 블록이 생성된다. 이 작업은 마지막으로 처리된 snindel까지의 거리가 씨드 길이보다 짧은 다음의 각 snindel에 대해 반복된다. 모든 삽입 또는 삭제에 대해서 블록 쪼개기가 일어나고 이 위치까지 요구되는 블록들이 생성되고 분기 서열의 염기들로 채워진다. 분기 서열 변수는 비워지고, 오직 이 시점부터 이 계통에 있는 다음의 snindel은 분기 서열을 생성한다.
두 이어지는 snindels 사이의 거리가 씨드 길이보다 크게 된다면, 수퍼 블록이 종료될 수 있다. 하지만, 오직 마지막 snindel과 합쳐진 계통만이 완전한 분기 서열을 가질 수 있음이 보장된다. 다른 계통들은 그들의 마지막 snindel 위치에서 멈추고, 분기 종결 위치까지 채워져야 한다. 모든 계통 서열이 완료될 때, 그들의 서열들은 최대 256의 길이를 가지는 새로운 블록들로 쪼개질 수 있다. 그 이후에, 수퍼블록을 따르는 보존 서열을 위한 블록이 생성되고 채워지게 된다. 이 보존 블록의 길이는 이미 계산 가능하다. 왜냐하면 언제나 갱신되는 snindels 리스트의 첫 snindel은 새로운 분기 위치를 결정하기 때문이다. 수퍼블록과 오른쪽의 이어진 보존 블록 쌍은(그런 까닭에 "그래프 유닛"이라고 불린다) 분기 이벤트의 결과이고 그런 쌍들은 염색체의 종결지점까지 반복적으로 생성된다.
각 그래프 유닛의 생성 이후에, 이제 남아 있는 작업은 모든 계통으로부터의 발견된 모든 씨드들을 전향, 후향 색인 안에 저장하는 것이다. 이 때 저장되는 범위는 이제 막 처리된 분기의 분기 위치에서 부터 다음의 분기 지점 혹은 염색체의 종결 지점까지이다.
그림 2.4. 그래프 생성 프로시져. 각 블록의 블록 번호는 각 블록 아래의 원에 표시되어 있다. 또한 그것은 블록이 생성된 순서를 나타낸다. 계통 연결(strain links)은 회색의 수직 화살표로 표현되어 있다. 블록들 사이의 수평 연결은 표시되어 있지 않다. 미스매치는 빨강색으로 강조되어 있다. 생성: 씨드 길이가 7이고 블록 길이가 10인 경우, 블록 3에서의 삽입은 분기가 시작되도록 한다. 삽입 뒤의 모든 계통의 염기에 대해서 참조 서열에 대한 상대적인 위치는 더 이상 결정될 수 없기 때문에, 삽입 후에 새로운 블록이 시작되어져야 한다. 전체 분기 길이가 최대 블록 길이인 10을 넘기 때문에 두 블록이 생성되어져야 한다. 다음의 snindel은 블록 6에서 시작하는 계통 2의 삭제이다. 각 snindels의 거리가 씨드 길이보다 작기 때문에 수퍼블록이 확장된다. 이것은 두 이어지는 snindels의 거리가 씨드 길이 보다 커질 때까지 반복된다(SNP이 블록 12에 있다고 가정한다). 다음으로, 수퍼블록이 끝나고, 분기 종결 지점까지 분기 서열이 "채워질" 수 있다. 분기 종결 지점은 수퍼블록의 마지막 snindel에 의해서 결정되낟. 다음으로 보존 블록(블록 13부터 시작)을 채운 후에, 단일 분기들에 대해 이런 과정들이 반복되고, 모든 가능한 씨드가 해시 색인에 저장된다(회색에서 검정색으로 점진적으로 색상이 변하는 화살표, 숫자 5는 반복 횟수를 나타낸다). 블록 테이블: refpos는 참조 서열에서의 위치이다. next/prev는 수평으로 이웃한 블록의 블록 번호이다. nsf/nse는 수직으로 이웃한 블록의 블록 번호로 첫 분기 블록의 이웃, nse는 마지막 분기 블록의 이웃이다. indel은 indel의 위치이다. ioffs는 indel 오프셋이다.
색인 생성
길이 n의 모든 씨드들을 그들의 지놈 상의 위치와 연관 시키는 전역 해시 테이블은 완전 해시(충돌이 없는 해시)로 구현되었다. 이것은 모든 4가지 염기를 2비트 표기로 인코딩하고, 이 2 비트 값들을 합쳤기 때문에 가능하다. 그 결과는 1개의 정수이다.
모든 서열의 n-mer는 4개 염기 이외의 다른 문자가 있지 않은 한은 2 비트 표기로 인코딩 된다. 0에서 시작해서 씨드 길이 n에서 끝나는 씨드의 각 i 번째 염기를 해시키(부가적으로 전향과 후향 가닥에서 씨드의 색인 슬롯으로 각각 사용되는)로 변환하기 위해 사용하는 수식은 다음과 같다. c는 4 염기 중 하나의 비트 코드이고, (c|11)은 비트의 보수 표현이다. 역방향 가닥에 있는 씨드는 대응되는 전향 씨드에 보수를 취하고 역 방향으로 인코딩 된다.
|
A |
C |
G |
T |
|
c |
00 |
01 |
10 |
11 |
|
c |
11 |
11 |
10 |
01 |
00 |
만약 지놈에서 위치 p에 있는 씨드 A가 그것의 2비트 표현인 a로 변환되고, p+1에 있는 씨드 B가 적합하면, 그것의 2비트 표현인 b는 a로 부터 비트 연산을 통해 빠르게 계산될 수 있다. 전향 씨드에 대해서 그것은 단순히 a를 2만큼 오른쪽으로 시프트 하고, 최상위 비트(MSB, Most Significant Bit)를 p+1+n 위치에 있는 염기에 대응되는 2비트 코드로 채운다. 이것은 불필요한 시프트 연산을 줄이기 위해서 모든 염기와 모든 씨드 길이에 대해 미리 정의된(hardcoded) 비트 마스크 값을 이용해서 처리될 수 있다. 다음 단계에서 역방향 색인의 슬롯을 나타내는 정수가 계산된다. a의 2개의 MSB는 왼쪽으로 2비트 시프트 하고 비트 마스크와 AND연산을 수행함으로써 제거되어야 한다. 두 LSB 비트를 채우는 것은 간단한데, 이것은 단지 보수 염기 코드를 OR 연산(c | 11)하면 되기 때문이다.
이 방법으로, 전향과 역방향 가닥에 대해서 오직 2에서 3비트 연산만을 수행함으로써 반복적으로 전체 씨드의 해시키를 계산하기 위한 연산을 반복하는 대신에 다음의 이미 인코딩된 씨드에 부합하는 씨드의 해시 키를 얻을 수 있다. 이 성능 향상 단계는 오직 ACGT 외의 문자가 나타나거나 염색체 경계에 의해서 방해될 수 있다. 하지만, 분기의 경계에 의해서는 방해받지 않는다. 각 계통의 첫 씨드는 수퍼 블록에 남아있는 보존 블록의 마지막 씨드로 부터 계산할 수 있다. 왜냐하면 그것은 참조 서열과 계통 서열 간의 마지막으로 보존된 것이기 때문이다. 보존 블록의 첫 번째 씨드는 이전의 수퍼 블록의 참조 서열 부분을 확장하는 것으로 계산할 수 있다.
단일 정수(integer)는 4 바이트(모든 x86 운영 체제에서 32 비트)를 차지하기 때문에, 씨드 길이 n은 긴 정수(64비트 long integer)를 사용하는 경우에도 16 - 또는 32의 이론적 제한이 있다. 하지만, 실제적 제한은 16 이하이다. 왜냐하면 GenomeMapper는 모든 발견 가능한 씨드를 인코딩 하기 위해서 
13의 길이는 실제 사용의 다른 제한 사항을 설명한다. 애기장대의 대략 ~120 Mbp(120 메가 염기쌍) 지놈 중에 오직 58%의 모든 발생 가능한 씨드(13개의 연결된 염기의 모든 수열의 갯수)가 발견될 수 있다. 반면에 이 숫자는 더 긴 씨드 길이에 대해서 훨씬 빠르게 증가한다 (12의 씨드 길이에 대해서는 85 %, 그리고 씨드 길이 11에서는 거의 100%). 씨드 길이의 증가는 다른 저장 구조를 요구할 것이다. 왜냐하면, 색인의 부하가 지수적으로 감소하게 되고 매우 성기게 생성된 해시 색인이 되기 때문이다.
다음으로 동일한 색인 구조가 메모리에 할당된다. 다만, 이것은 역방향 가닥에 대한 색인으로 각 염색체 별로 씨드의 위치를 저장한다.
각 씨드의 해시 키는 배열에서의 위치를 나타내고(색인 배열) 그런 까닭에 슬롯이라고 불린다. 각 슬롯은 지놈에서 씨드가 발견될 때 할당되는 빈(bin)이라는 자료구조를 가리키게 된다. 빈은 씨드가 세번 나타날 때까지 위치 정보를 담고, 만약 그 숫자가 넘어가면, 확장된 빈이 생성되서 그것의 원래 빈에 포인터를 통해 연결되게 된다. 확장된 빈에는 20개의 씨드 발생이 저장될 수 있고 특정 n-mer가 생기게 하는 확장된 빈의 개수에는 제한이 없다.
그림 2.6. 씨드 길이 4를 사용하는 에제를 보이는 mkindex의 색인 해시 구조. 씨드 GGCA는 현재 처리 중인 염색체에서 오직 두번만 나타나고(occ./chr.으로 표기), 그리고 모든 염색체들에서는 7번 나타난다(occ. total로 표기). 그것의 해시 키가 4-mer GTAG는 지놈에서 처음으로 나타났으며, 이는 occ./chr.이 occ./total과 동일하기 때문에 알 수 있다. 비록 GTAC의 5번 등장이 3의 크기를 가지는 빈의 크기를 넘어서지만, 확장된 빈이 할당되었고, 두 개의 추가적인 위치를 저장한다.
출력 쓰기
그래프의 생성과 씨드 생성 이후에, 색인 내용의 저장이 각 염색체 별로 수행된다. 이것은 이전 버전의 잔여물이고, 염색체 정보는 저장 구조에 따라 암시적으로 저장되었다. 현재는 블록 테이블에 의해서 수행된다. 하지만, 그런 방식은 여전히 몇몇 장점을 가지고 있다. 예를 들어, 한 염색체에 요구되는 메모리만을 사용하고, 전체 지놈을 위한 메모리를 사용하지 않는다. 두 출력 파일들이 생성될 것이고, 하나는 블록 정보/모든 씨드에 대한 오프셋 정보(색인 파일이라 불린다)를 담고 있고 다른 파일은 블록 테이블과 다른 추가적인 정보(메타 파일이라 불린다)를 저장한다. 후자는 모든 염색체가 처리된 후에 생성된다. 두 출력 파일들은 이진 포맷으로 되어 있고, 사람이 읽을 수 없다.
색인 파일의 헤더는 염색체 번호(0으로 시작하는), 염색체 길이, 그리고 입력 fasta 파일의 헤더에 명시된 것처럼 염색체에 대한 설명을 가지고 있다. 이 데이터는 genomemapper가 지놈 파스타 파일을 다시 파싱하지 않기 때문에 중요하다. 왜냐하면 전체 
폴리(A) 확장(stretch)는 폴리아데닐레이션(polyadenylation)으로 한 RNA 분자에 폴리(A) 꼬리가 붙여지는 것을 말한다. 폴리(A) 꼬리는 다수의 아데노신 모노포스페시트(adenosine monophosphate)들을 포함한다. 다시 말하면, RNA의 확장 부분이 오직 아데닌(adenine)으로만 되어 있는 것을 말한다. 진핵 생물에서, 폴리아데닐레이션은 번역(translation)을 위한 성숙한 메신저 RNA(mRNA)를 생성하는 작업이다. 그런 까닭에, 이 과정은 유전자 발현의 큰 프로세스의 일부를 형성한다.
메타 색인은 순서대로 역방향 가닥이 색인의 생성 과정에서 포함되었는지 여부를 담는 표시자(flag), 씨드 길이, 전체 염색체 수, 그리고 전체 저장된 씨드의 수(중복 허용 또는 비허용), 가능한 계통 서열의 염색체를 포함하여 가장 긴 염색체의 길이, 모든 계통에 대한 짧은 액세션(accession) 정보와 함께 전체 블록 테이블에 대한 정보를 저장한다. 끝으로, 전체 지놈에서 최소한 한 번은 나타났던 각 씨드에 대해서 지놈 상에서 그것의 전체 발생횟수를를 리스트에 저장한다. 마찬가지로, 음수의 해시 키를 사용하여 역방향 씨드에 대해서도 저장한다.
댓글