본 내용은 내 동료인 Jorg의 diploma thesis의 일부를 번역한 것이다.
개념
GenomeMapper는 프로그래밍 언어 C를 이용하여 구현되었다. 포인터 연산과 수동 메모리 관리가 이점이며, 다른 프로그래밍 언어에 비해서 실행 시간을 줄여준다.
Read란, 예를 들어 fasta 포맷으로 된 염기 서열 데이터 파일을 보면 시퀀싱 머신에서 한 싸이클 당 읽어들인 염기 서열들이 한 줄마다 있게 된다. 즉 이 한 줄에 담긴 염기 서열을 read 라고 부른다.
GenomeMapper는 약간씩 다른 지놈들에 있는 수백만의 리드들의 위치를 검출하기 위해 개발되었다. 리드들은 알려지지 않은 지놈으로부터 왔기 때문에, 대부분의 리드들은 원래의 염기 서열에 있어야 하는 영역을 찾지 못할 것이다. 그런 까닭에, 리드와 지놈 간에 약간의 불일치를 인정하면서 정렬을 수행해야 이런 영역을 찾을 수 있게 된다.
발견적(heuristic) seed-and-extend 접근법
참고적으로 발견적이라는 의미는 중요 변수를 먼저 분석하고, 차차 부가 변수도 분석해 나가는 방법을 말한다.
예를 들어서, 수백 수천만의 염기들을 포함하고 있는 상대적으로 큰 지놈에서 몇 십개의 염기 쌍을 찾기 위해서, 엄청나게 커다란 지역 정렬을 수행하려고 하는 것은 명백히 비현실적이다. 대신에 잠재적으로 리드 매칭이 될 가능성 있는 지역에 대해 먼저 검색을 해야 한다. seed-and-extend 접근법은 이 작업을 위해서 고안되었다. 하나의 씨드는 리드와 지놈 사이에서 동일한 DNA 조각이다. 만약 그러한 씨드들이 찾아질 수 있다면, 첫 미일치 염기 쌍이 나타날 때까지 양쪽 방향으로 일치하는 영역을 계속 증가시킬 수 있을 것이다.
이렇게 최대한으로 확장된 일치된 영역을 "hits"라고 부르고, 정렬이 일어나야 할 영역을 결정하게 된다.
씨드를 길게 만들면, 지놈 상에서 정렬될 가능성이 있는 영역이 더 적게 찾아지게 되고 그래서 더 적은 정렬 연산이 요구되기 때문에 매핑 속도를 높일 수 있게 된다. 하지만, 동시에, 씨드의 길이를 늘리게 되면, 잠재적으로 정렬이 될 가능성이 있는 영역을 놓치게 된다. 특정 길이의 씨드는 최소한 서로가 씨드 길이만큼 떨어진 미스매치를 가진 지놈에 대해 매핑되는 리드들만을 찾을 수 있다. 그래서 주어진 씨드 길이들과 최대 미스매치와 갭의 숫자에 따라서 모든 일치되는 정렬 결과를 얻지 못하게 된다. 그래서 seed-and-extend 접근법은 발견적이다. 이 알고리즘의 발견 감도는 씨드 길이에 의해 조정될 수 있다. 씨드 길이를 증가시키는 것은 놓치는 매핑이 많아진다는 뜻이다.
시퀀스 그래프
다른 매핑 툴들과 다르게 GenomeMapper는 짧은 리드를 단일 참조 지놈에 매핑할 수 있을 뿐만 아니라, 질의한 염기 서열이 동시에 정렬되어지는 다른 지놈들과 통합될 수 있다. 이런 기능을 구현하기 위한 기본적인 아이디어는 대상이 되는 서열 데이터를 표현하는데 있어서, 단일 참조 서열의 긴 문자열에서 다양한 통합된 참조들의 시퀀스 그래프로 변환하는데 있다. 보존되는 영역, 즉, 모든 계통([생물]strains)들 간에 동일한 영역은 오직 한 번만 저장되고, 다른 계통에 대한 분리된 문자열들은 염기가 달라져서 분기하는 영역(소위 말하는 트리 자료구조의 브랜치)을 표현하기 위해서 사용된다. 지놈은 블록이라고 불리는 염기서열의 부분(chunk)들로 쪼개어지고, 각 블록들은 노드를 표현하며, 상응하는 서열에 대한 정보와 그들의 연결 정보를 저장한다. 자세한 그래프 구조의 구성도와 구현은 차후에 설명한다.
지놈에 대한 해싱
엄청난 양의 짧은 리드들과 수천만에 이르는 염기쌍들을 포함하는 생물의 큰 지놈들은 리드들에 대해서나 지놈 데이터에 대해 필연적으로 색인을 생성하도록 만든다.이러한 룩업 테이블은 각 씨드의 모든 위치를 저장하기 때문에 모든 씨드 위치에 대한 접근은 현실적인 시간 안에 수행될 수 있다.
입력 리드를 해싱하는 다른 매핑 도구들과 다르게 GenomeMapper는 입력 DNA 서열에 대해 해시 색인을 생성한다. 각 서열의 n-mer는 이 씨드에 대한 모든 서열 정보(2 비트 표현)를 가진 단일 정수로 변환된다. 그런 까닭에, 다른 n-mer들은 다른 키로 변환되기 때문에 충돌이 없는 완전한 해시로 동작하게 된다. GenomeMapper는 씨드 길이를 5에서 13까지 지원한다.
그래프 구조와 색인은 차후에 이뤄질 이들 특정한 시퀀스들에 대한 매핑 단계의 속도를 향상시키기 위해서 디스크에 저장된다.
매핑 단계
DNA 데이터에 대한 색인이 한 번 생성되면, 매핑 단계가 모든 리드에 대해서 이뤄질 것이다. GenomeMapper는 두 가지의 일반 모드들이 있다. 기본적으로, 프로그램은 모든 리드에 대해서 최대한 일치하는 정렬들만 표시할 것이다. 다른 모드는, 미스매치와 갭 제한을 허용한 상태로 진행된 모든 정렬이 출력에 나타날 것이다.
이 모드에 따라서, 프로그램은 다른 방식으로 동작할 것이다. 최대-일치(best-hit) 모드(그리고 몇몇 모두-일치(all-hit) 모드)에서, "fast mapping"이라고 명명된 프로시져가 시작된다. 이 프로시져는 오직 리드의 몇몇 겹치지 않는(non-overlapping) 씨드들만을 선택하고, 해시 색인으로 부터 지놈 상의 위치를 찾고, 많은 연산 비용이 드는 정렬 없이 여분의 리드들을 즉시 해당 영역에 매핑하려고 시도한다. 만약, 적합한 정렬이 발견되지 않으면, 모두-일치 모드와 동일한 프로시져가 시작된다.
GenomeMapper는 발견적 seed-and-extend 접근법을 따른다. 모든 색인을 생성하기 위해서 사용된 n과 같은 길이의 리드 길이를 가지는 모든 씨드들이 추출되고, 만약 그 씨드들이 지놈에서 찾아질 수 있다면 hit가 생성되게 한다. 지놈 상에서 이웃 관계인 두 씨드들이 리드에서도 이웃 관계일 때, 이들은 합쳐지고, 다음에 오직 하나의 hit으로 간주되게 된다. 만약 두 hit들이 오직 하나의 염기 차이로 쪼개져 있다면, 하나의 hit으로 합쳐질 수 있다. 그리고, 그 중간에 있던 염기쌍은 미스매치로 간주될 수 있다.
모든 hit들이 최대로 확장되면, 그 중에 전체 리드 길이까지 확장되지 못한 hit들은 지놈의 특별한 영역에 정렬되어야 한다. 만약 사용자가 허용되는 갭을 0으로 명시하면, 비용이 많이 드는 정렬 행렬이 계산되어질 필요가 없고, hit 바깥에 있는 리드의 부분들은 쌍별 염기 비교(pairwise base comparison)를 통해 지놈에 매칭될 수 있다. 이 방법은 "단순 매핑"이라는 방법으로 구현되었다.
그림 2.1. 단일 리드에 대한 매핑 프로세스의 기본 흐름도.모두-일치(all-hit) 전략이 seed-and-extend 전에 fast mapping 알고리즘을 시작하는 경우에 대한 것은 차후에 설명된다.
정렬
만약 갭이 허용된다면, 처음은 "돌출부 정렬(overhang alignment)"이라는 단계가 수행된다. 이 방법은 Needleman-Wunsch 알고리즘과 유사한 k-테두리 정렬(k-banded alignment)로 대응하는 hit에 의해서 처리되지 않은 리드의 돌출된 양 끝 부분들에 대해서 적용된다. k는 허용된 갭의 갯수를 의미한다.
만약 가장 적합한 경로가 갭들을 포함하고 있다면, 그들은 k-테두리 덕분에 발견될 것이다. 만약 그런 경우라면, 두 번째 프로시져가 시작되어야 한다. 이것은 전체 리드를 확장하는 전역 k-테두리 정렬이라고 한다. 이것은 일관적이고 유일한 정렬을 보장하기 위해 필요하다.
각 매핑 단계들에 의해 얻어진 모든 적합한 정렬은 출력되고 그것의 점수에 의해서 순위가 매겨진다. 최대-일치 전략이 이용된 경우 오직 특정 간격 안에 있는 점수를 가진 정렬들만 출력되고, 아닌 경우 모든 정렬들이 출력된다.
다른 매핑 프로시져는 그들의 시간 복잡도를 증가시키고 그렇기 때문에 오직 필요할 때만 시작될 수 있다. 많은 전역 정렬들은 프로그램을 심각하게 느리게 만들 것이다. 그래서, GenomeMapper는 전역 정렬을 가능한 방지하려고 시도한다.
낮은 빈도의 삽입과 삭제의 빈도 때문에, 매핑 루틴은 전역 정렬이 소비하는 시간을 줄이려고 하는 것이다. 세 가지의 기본 편집 연산들 중에 대략 오직 3%만 삽입과 삭제(indels)이다. 그럼에도 불구하고, 많은 리드의 씨드들이 "잘못된" 위치에 매핑되기 대문에, 씨드에 의해서 제안된 지놈 상의 위치가 많은 차이를 보이게 되고, 그로 인해 많은 전역 정렬이 시작된다. 이는 GenomeMapper의 주요 런타임 시간을 차지한다.
이 프로그램은 Korbinian Schneeberger에 의해서 구현된 기본적인 원래의 프로그램 버전에 기반하여 작성되었다. 그 기본 버전은 해시 색인 생성과 seed-and-extend 접근법을 이용하지만 편집 연산을 허용하지 않은 상태로 리드들을 참조 서열의 전향 가닥(forward strand)에 매핑할 수 있었다. 사용자 정의가 가능한 편집 연산이 가능하고, 앞서 언급한 모든 매핑 프로시져가 가능한 완전히 동작하는 전은 2008년 10월에 시작되었고, 인터넷 상에 이미 공개되었다. 그것은 리드들을 단일 참조 시퀀스에 매핑한다. 이 버전은 이제부터 릴리즈 1이라고 부를 것이다. 최신 버전은 시퀀스 그래프를 구현했고, 리드를 다수의 지놈에 동시에 매핑하도록 해준다. 이전에 설명한 방법과 개념은 여전히 같지만, 매핑과 정렬을 위해 시퀀스를 추출하는 부분은 현저히 변했다. 이 새로운 버전은 다음에 더 자세히 설명된다.
GenomeMapper는 두 프로그램들을 포함한다: mkindex는 해시 색인과 실제 매핑 프로그램인 genomemapper에서 사용되는 그래프 구조를 생성한다.
댓글