KR101576794B1

KR101576794B1 - 리드 길이를 고려한 염기 서열 정렬 시스템 및 방법

Info

Publication number: KR101576794B1
Application number: KR1020130009790A
Authority: KR
Inventors: 박민서
Original assignee: 삼성에스디에스 주식회사
Priority date: 2013-01-29
Filing date: 2013-01-29
Publication date: 2015-12-11
Also published as: US20140214332A1; KR20140096782A; WO2014119848A1

Abstract

리드 길이를 고려한 염기 서열 정렬 시스템 및 방법이 개시된다. 본 발명의 일 실시예에 따른 염기 서열 정렬 시스템은, 입력된 리드의 길이에 따라 상기 리드로부터 생성될 시드의 길이를 계산하는 시드 길이 계산부, 상기 리드로부터 계산된 상기 시드 길이를 가지는 하나 이상의 시드를 생성하는 시드 생성부, 및 생성된 상기 시드를 이용하여 상기 리드의 참조 서열에 대한 전역 정렬(global alignment)을 수행하는 정렬부를 포함한다.

Description

리드 길이를 고려한 염기 서열 정렬 시스템 및 방법{SYSTEM AND METHOD FOR ALIGNING OF GENOME SEQUENCE CONSIDERING READ LENGTH}

본 발명의 실시예들은 시퀀서로부터 얻어진 단편 서열들을 재조합하여 염기 서열을 생성하기 위한 기술과 관련된다.

저렴한 비용과 빠른 데이터 생산으로 인해 대용량의 짧은 서열을 생산하는 차세대 시퀀싱(NGS; Next Generation Sequencing)이 전통적인 생거(Sanger) 시퀀싱 방식을 빠르게 대체하고 있다. 또한 다양한 NGS 서열재조합 프로그램들이 정확도에 초점을 맞추어 개발되었다. 그러나, 최근 차세대 시퀸싱 기술이 발전함에 따라 단편서열을 만들어 내는 비용이 예전의 절반 이하가 되었고, 이에 따라 사용할 수 있는 데이터의 양이 많아지게 되면서, 대용량의 짧은 서열들을 빠른 시간에 정확하게 처리하기 위한 기술이 필요하게 되었다.

서열 재조합의 첫 번째 단계는 염기 서열 정렬(alignment) 알고리즘을 통해 리드를 참조 서열의 정확한 위치에 맵핑(mapping)하는 것이다. 여기서의 문제점은 같은 종의 개체라 할지라도 다양한 유전적 변이로 인해 유전체 서열에 차이가 있을 수 있다는 점이다. 또한 시퀀싱 과정에서의 오류로 인해서도 염기 서열에 차이가 생길 수 있다. 따라서 염기 서열 정렬 알고리즘은 이러한 차이와 변이를 효과적으로 고려해서 맵핑 정확도를 높이지 않으면 안 된다. 결론적으로, 유전체 정보의 분석을 진행하기 위해서는, 될 수 있는 한 많은 수의 정확한 전체 유전체 정보 데이터가 필요하다. 또 이를 위해서는 무엇보다도 뛰어난 정확도와 큰 처리량을 갖는 염기 서열 정렬 알고리즘을 개발하는 것이 선행되어야 한다. 그러나 종래의 방법들은 이러한 요구 조건들을 만족시키는 데 한계가 있었다.

본 발명의 실시예들은 시퀀서로부터 출력되는 리드를 참조 서열에 정렬함에 있어서, 맵핑의 속도 및 정확도를 고려한 최적의 시드를 추출하기 위한 수단을 제공하기 위한 것이다.

본 발명의 일 실시예에 따른 염기 서열 정렬 시스템은, 입력된 리드의 길이에 따라 상기 리드로부터 생성될 시드의 길이를 계산하는 시드 길이 계산부, 상기 리드로부터 계산된 상기 시드 길이를 가지는 하나 이상의 시드를 생성하는 시드 생성부, 및 생성된 상기 시드를 이용하여 상기 리드의 참조 서열에 대한 전역 정렬(global alignment)을 수행하는 정렬부를 포함한다.

본 발명의 일 실시예에 따른 염기 서열 정렬 방법은, 시드 길이 계산부에서 입력된 리드의 길이에 따라 상기 리드로부터 생성될 시드 길이를 계산하는 단계, 시드 생성부에서 상기 리드로부터 상기 시드 길이를 가지는 하나 이상의 시드를 생성하는 단계, 및 정렬부에서 생성된 상기 시드를 이용하여 상기 리드의 참조 서열에 대한 전역 정렬(global alignment)을 수행하는 단계를 포함한다.

본 발명의 실시예들에 따를 경우, 시퀀서로부터 출력되는 리드의 길이를 고려하여 최적의 시드 길이, 시드 개수 및 오버랩 길이를 계산하고 계산된 결과에 따라 리드로부터 시드를 추출함으로써, 염기 서열 정렬의 정확도를 보장하는 동시에 정렬 속도를 향상시킬 수 있는 장점이 있다.

도 1은 본 발명의 일 실시예에 따른 염기 서열 정렬 방법(100)을 설명하기 위한 도면이다.
도 2는 본 발명의 일 실시예에 따른 염기 서열 정렬 방법의 에러 개수 계산 과정을 예시하기 위한 도면이다.
도 3은 본 발명의 일 실시예에서 시드간의 오버랩(overlap)을 설명하기 위한 도면이다.
도 4 및 도 5는 본 발명의 일 실시예에서 시드간의 오버랩 길이에 따른 효과를 비교하여 설명하기 위한 도면이다.
도 6은 본 발명의 일 실시예에 따른 염기 서열 정렬 시스템(600)의 블록도이다.

이하, 도면을 참조하여 본 발명의 구체적인 실시형태를 설명하기로 한다. 그러나 이는 예시에 불과하며 본 발명은 이에 제한되지 않는다.

본 발명을 설명함에 있어서, 본 발명과 관련된 공지기술에 대한 구체적인 설명이 본 발명의 요지를 불필요하게 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명을 생략하기로 한다. 그리고, 후술되는 용어들은 본 발명에서의 기능을 고려하여 정의된 용어들로서 이는 사용자, 운용자의 의도 또는 관례 등에 따라 달라질 수 있다. 그러므로 그 정의는 본 명세서 전반에 걸친 내용을 토대로 내려져야 할 것이다.

본 발명의 기술적 사상은 청구범위에 의해 결정되며, 이하의 실시예는 본 발명의 기술적 사상을 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 효율적으로 설명하기 위한 일 수단일 뿐이다.

본 발명의 실시예들을 상세히 설명하기 앞서, 먼저 본 발명에서 사용되는 용어들에 대하여 설명하면 다음과 같다.

먼저, "리드(read)"란 게놈 시퀀서(genome sequencer)에서 출력되는 짧은 길이의 염기서열 데이터이다. 리드의 길이는 게놈 시퀀서의 종류에 따라 일반적으로 35~500bp(base pair) 정도로 다양하게 구성되며, 일반적으로 DNA 염기의 경우 A, C, G, T의 알파벳 문자로 표현된다.

"참조 서열(reference sequence)"이란 상기 리드들로부터 전체 염기 서열을 생성하는 데 참조가 되는 염기 서열을 의미한다. 염기 서열 분석에서는 게놈 시퀀서에서 출력되는 다량의 리드들을 참조 서열을 참조하여 맵핑함으로써 전체 염기 서열을 완성하게 된다. 본 발명에서 상기 참조 서열은 염기 서열 분석 시 미리 설정된 서열(예를 들어 인간의 전체 염기 서열 등)일 수도 있으며, 또는 게놈 시퀀서에서 만들어진 염기 서열을 참조 서열로 사용할 수도 있다.

"베이스(base)"는 참조 서열 및 리드를 구성하는 최소 단위이다. 전술한 바와 같이 DNA 염기의 경우 A, C, G 및 T의 네 종류의 알파벳 문자로 구성될 수 있으며, 이들 각각을 베이스라 표현한다. 즉, DNA 염기의 경우 4개의 베이스로 표현되며, 이는 리드 또한 마찬가지이다.

"시드(seed)"란 리드의 맵핑을 위하여 리드와 참조 서열을 비교할 때의 단위가 되는 시퀀스이다. 이론적으로 리드를 참조 서열에 맵핑하기 위해서는 리드 전체를 참조 서열의 가장 첫 부분부터 순차적으로 비교해 나가면서 리드의 맵핑 위치를 계산하여야 한다. 그러나 이와 같은 방법의 경우 하나의 리드를 맵핑하는 데 너무 많은 시간 및 컴퓨팅 파워가 요구되므로, 실제로는 리드의 일부분으로 구성된 조각인 시드를 먼저 참조 서열에 맵핑함으로써 전체 리드의 맵핑 후보 위치를 찾아 내고 해당 후보 위치에 전체 리드를 맵핑(Global Alignment)하게 된다.

도 1은 본 발명의 일 실시예에 따른 염기 서열 정렬 방법(100)을 설명하기 위한 도면이다. 본 발명의 실시예에서, 염기 서열 정렬 방법(100)이란 게놈 시퀀서(genome)에서 출력되는 리드를 참조 서열과 비교하여 리드의 상기 참조 서열에서의 맵핑(또는 정렬) 위치를 결정하는 일련의 과정을 의미한다.

먼저, 게놈 시퀀서(genome sequencer)로부터 리드가 입력되면(102), 리드 전체와 상기 참조 서열과의 일치 정합(exact matching)을 시도한다(104). 만약 상기 102 단계의 수행 결과 리드 전체에 대한 일치 정합이 성공한 경우에는 이후의 정렬 단계를 수행하지 않고 정렬에 성공한 것으로 판단한다(106). 인간의 염기 서열을 대상으로 한 실험 결과, 게놈 시퀀서에서 출력되는 100만 개의 리드를 인간의 염기 서열에 일치 정합할 경우 총 200만회의 정렬 중(정방향 시퀀스 100만회, 역상보(reverse complement) 방향 시퀀스 100만회) 231,564회의 일치 정합이 발생되는 것으로 나타났다. 따라서 상기 104 단계의 수행 결과 약 11.6%만큼의 정렬 소요량을 감소시킬 수 있었다.

그러나, 이와 달리 상기 106 단계에서 해당 리드가 일치 정합되지 않는 것으로 판단되는 경우에는, 다음으로 해당 리드를 상기 참조 서열에 정렬했을 때 나타날 수 있는 에러의 개수를 추정한다(108).

도 2는 상기 108 단계에서의 에러 개수 추정 과정을 예시하기 위한 도면이다. 먼저, 도 2의 (1)에 도시된 바와 같이 최초 에러 개수 추정치를 0으로 설정하고 리드의 가장 첫 베이스부터 리드의 끝 방향으로 한 베이스씩 이동하면서 일치 정합을 시도한다. 이때 (2)에 도시된 바와 같이 리드의 특정 베이스(도면에서 두번째 T로 표기된 부분)에서부터 더 이상 일치 정합이 불가능하다고 가정하자. 이 경우는 리드의 정합 시작 위치부터 현재 위치 사이의 구간 어딘가에서 에러가 발생한 것을 의미한다. 따라서 이 경우에는 에러 개수 추정치를 1만큼 증가시키고, 다음 위치에서 새로 일치 정합을 시작한다(도면에서 (3)으로 표기). 이후 특정 위치에서 재차 일치 정합이 불가능하다고 판단되는 경우에는, 일치 정합을 새로 시작한 위치부터 현재 위치 사이의 구간 어디에서 다시 에러가 발생한 것이므로, 에러 개수 추정치를 다시 1만큼 증가시키고, 다음 위치에서 새로 일치 정합을 시작한다(도면에서 (4)로 표기). 이와 같은 과정을 거쳐 리드의 끝까지 도달한 경우의 에러 개수 추정치가 해당 리드에 존재할 수 있는 에러의 개수가 된다.

상기와 같은 과정을 거쳐 리드의 에러 개수 추정치가 계산되면, 계산된 에러 개수 추정치가 기 설정된 최대 에러 허용치(maxError)를 초과하는지의 여부를 판단하고(110), 초과하는 경우 해당 리드에 대한 정렬이 실패한 것으로 판단하여 정렬을 종료한다. 전술한 인간의 염기 서열을 대상으로 한 실험에서, 최대 에러 허용치(maxError)를 3으로 하고 나머지 리드들의 에러 개수 추정치를 계산한 결과, 총 844,891회에 해당하는 리드들이 상기 최대 에러 허용치를 초과하는 것으로 나타났다. 즉, 상기 108 및 110 단계의 수행 결과 약 42.2%만큼의 정렬 소요량을 감소시킬 수 있었다.

그러나 이와 달리 상기 110 단계에서의 판단 결과, 에러 개수 추정치가 상기 최대 에러 허용치 이하인 경우에는, 다음으로 상기 리드의 길이를 이용하여 상기 리드로부터 생성할 시드의 길이(112), 생성할 시드의 개수(114), 및 각 시드 간의 오버랩 길이(116)를 계산한다. 이후, 계산된 상기 시드의 길이, 개수 및 오버랩 길이를 이용하여 상기 리드로부터 시드를 생성하고(118), 생성된 상기 리드에 대한 전역 정렬(global alignment)을 수행한다(120). 이때 상기 전역 정렬의 결과 리드의 에러 개수가 기 설정된 최대 에러 허용치(maxError)를 초과하는 경우에는 정렬 실패로, 그렇지 않은 경우에는 정렬에 성공한 것으로 판단된다(122).

이하에서는 상기 112 내지 116 단계에서 상기 리드의 길이로부터 추출될 시드의 길이, 개수 및 오버랩 길이를 결정하기 위한 과정을 상세히 설명한다.

시드의 길이 계산

본 발명의 실시예에서, 리드로부터 산출되는 시드의 길이는 상기 리드의 길이에 따라 정해진다. 즉, 상기 시드의 길이는 상기 리드의 길이가 길수록 길어지는 일종의 비례 관계를 가진다. 구체적으로, 상기 시드의 길이는 다음의 수학식 1에 따라 정해질 수 있다.

이때, R_length는 리드의 길이, S_length는 시드의 길이이며, A, B, k₁, 및 k₂는 시드와 리드 간의 구체적인 비례 관계를 설정하기 위한 파라미터이다. 이때, 각각의 파라미터의 범위는 리드 및 참조 서열의 종류 등에 따라 달라질 수 있으나, 대부분의 DNA 시퀀스에서 상기 파라미터들은 다음의 범위를 가지는 것이 바람직하다.

A: 2.8 이상 3.1 이하의 실수

B: 2.6 이상 3.0 이하의 실수

k₁ 및 k₂: 각각 0 이상 4 이하의 실수

한편, 상기 수학식에서 ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수를 의미한다.

예를 들어, A=2.966, B=2.804, k₁=k₂=0으로 가정하면, 리드 길이가 100일때의 시드 길이는 ceil[2.966*ln(100)+2.804] = ceil(16.4629) = 17이 된다. 또한, 리드 길이가 500일 경우의 시드 길이는 ceil[2.966*ln(500)+2.804] = ceil(21.2365) = 22가 된다.

또한, A=2.966, B=2.804, k₁=k₂=1로 가정할 경우, 상기 수학식 1에 의하여 계산되는 리드 길이에 따른 시드 길이는 다음과 같은 범위를 가진다.

i) 리드 길이가 75bp인 경우, 15bp ≤ 시드 길이 ≤ 17bp

ii) 리드 길이가 100bp인 경우, 16bp ≤ 시드 길이 ≤ 18bp

iii) 리드 길이가 150bp인 경우, 17bp ≤ 시드 길이 ≤ 19bp

iv) 리드 길이가 500bp인 경우, 21bp ≤ 시드 길이 ≤ 23bp

일반적으로 시드의 길이가 짧을수록 참조 서열에서 해당 시드의 맵핑수가 증가하며, 시드의 길이가 길어질수록 참조 서열에서의 해당 시드의 맵핑수는 감소하게 된다. 다시 말해, 리드로부터 생성되는 시드의 길이가 전술한 수학식 1에서의 범위보다 짧을 경우에는 시드의 참조 서열에서의 맵핑수가 지나치게 증가하게 되므로, 이후 전역 정렬 과정에서의 전역 정렬 횟수가 불필요하게 증가하게 되는 문제가 발생한다. 반대로, 상기 시드의 길이가 상기 수학식 1에서의 범위보다 길 경우에는 시드의 참조 서열에서의 맵핑수가 지나치게 감소하게 되는 바, 맵핑의 정확도가 떨어지게 된다. 따라서 본 발명에서는 리드의 길이를 고려하여 상기 수학식 1에 따라 시드의 길이를 설정함으로써 맵핑의 퀄리티를 보장하면서 맵핑 시 발생할 수 있는 복잡도를 최소화할 수 있도록 하였다.

또한, 상기 참조 서열이 인간의 염기 서열일 경우, 상기 시드는 15bp 내지 30bp의 범위 내에서 설정되도록 구성될 수 있다. 전술한 바와 같이, 일반적으로 시드의 길이가 짧을수록 참조 서열에서 해당 시드의 맵핑수가 증가하며, 시드의 길이가 길어질수록 참조 서열에서의 해당 시드의 맵핑수는 감소하게 된다. 특히 인간의 염기 서열의 경우 시드의 길이가 14 이하일 경우 참조 서열 내에서의 맵핑 위치의 개수가 급격히 증가하게 된다. 아래의 표 1은 시드 길이에 따른 인간 유전체 내에서의 시드의 평균 등장 빈도를 나타낸 것이다.

시드의 길이	평균 등장 빈도
10	2,726.1919
11	681.9731
12	170.9185
13	42.7099
14	10.6470
15	2.6617
16	0.6654
17	0.1664

상기 표에서 알 수 있는 바와 같이, 시드의 길이가 14 이하일 경우에는 시드 별 참조 서열에서의 평균 등장 빈도가 10 이상이나, 15일 경우에는 3 이하로 감소하는 것을 알 수 있다. 즉, 시드의 길이를 15 이상으로 구성할 경우 14 이하로 구성할 경우에 비해 시드의 중복을 대폭 감소시킬 수 있다. 또한, 상기 시드의 길이가 30 이상일 경우에는 시드의 참조 서열에서의 맵핑수가 지나치게 감소하게 되는 바, 맵핑의 정확도가 감소하게 된다. 따라서 본 발명에서는 참조 서열이 인간의 염기 서열일 경우 시드의 길이를 15 내지 30으로 구성함으로써 맵핑의 퀄리티를 보장하면서 맵핑 시 발생할 수 있는 복잡도를 최소화할 수 있도록 하였다.

시드의 개수 계산

상기와 같은 방법을 거쳐 시드의 길이가 정해지면, 다음으로 상기 리드의 길이 및 시드의 길이를 이용하여 상기 리드로부터 추출될 시드의 개수를 계산한다.

본 발명의 실시예에서, 리드로부터 산출되는 시드의 개수는 상기 리드의 길이 및 이로부터 추출될 시드의 길이에 따라 정해진다. 구체적으로, 상기 시드의 개수는 상기 리드의 길이가 길수록 많아지는 일종의 비례 관계를 가짐과 동시에, 상기 시드 길이가 길어질수록 적어지는 일종의 반비례 관계를 가진다. 구체적으로, 상기 시드의 개수는 다음의 수학식 2에 따라 정해질 수 있다.

이때, R_length는 리드의 길이, S_length는 시드의 길이, S_num은 시드 개수, k₃ 및 k₄는 상기 시드 개수의 범위를 정하기 위한 파라미터로서 각각 0 이상 4 이하의 실수로 정해질 수 있다. 또한 ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수를 의미한다.

예를 들어, k₃=k₄=1으로 가정할 경우 리드 길이 및 시드 길이에 따른 시드 개수는 다음과 같이 정해진다.

1) 리드 길이가 100이고, 시드 길이가 16인 경우

ceil(100/16-1) = ceil(5.25) = 6

ceil(100/16+1) = ceil(7.25) = 8

따라서, 6 ≤ 시드 개수 ≤ 8

2) 리드 길이가 75이고, 시드 길이가 16인 경우

ceil(75/15-1) = ceil(3.6875) = 4

ceil(75/15+1) = ceil(5.6875) = 6

따라서, 4 ≤ 시드 개수 ≤ 6

3) 리드 길이가 150이고, 시드 길이가 17인 경우

ceil(150/17-1) = ceil(7.823) = 8

ceil(150/17+1) = ceil(9.823) = 10

따라서, 8 ≤ 시드 개수 ≤ 10

오버랩 길이 계산

상기와 같은 방법을 거쳐 시드의 길이 및 개수가 정해지면, 다음으로 상기 리드로부터 추출될 시드의 오버랩 길이를 계산한다.

도 3은 본 발명에서 시드간의 오버랩(overlap)을 설명하기 위한 도면이다. 도시된 바와 같이, 본 발명의 실시예에서 시드 간의 오버랩이란 시드들 간의 겹치는 영역, 다시 말해 두 시드가 공통으로 가지고 있는 영역을 의미한다. 예를 들어 도시된 바와 같이 시드 1과 시드 2의 경우 회색 음영으로 표시된 부분을 서로 공통으로 가지게 되므로 이 부분이 두 시드간의 오버랩 영역이 된다. 또한, 이 경우 오버랩 길이란 두 시드 사이의 겹치는 영역(오버랩 영역)의 길이를 의미한다. 예를 들어, 도시된 실시예에서 시드 1이 리드의 5-19째 베이스를, 시드 2가 16-30째 베이스를 각각 가질 경우 시드 1 및 2 간의 오버랩 영역은 16-19가 되므로, 이 경우 오버랩 길이는 4가 된다. 한편, 시드 2 및 시드 3의 경우 오버랩되는 영역이 없으므로 두 시드 사이의 오버랩 길이는 0이 된다.

도 4 및 도 5는 본 발명의 일 실시예에서 시드 간의 오버랩 길이에 따른 효과를 비교하여 설명하기 위한 도면이다. 예를 들어, 도 4에 도시된 바와 같이, 시드 간의 오버랩 길이가 지나치게 크게 설정된 경우에는 시드가 리드의 일부분에서만 추출되게 되므로 리드 내부에 시드로 추출되지 못하는 영역이 존재하게 된다. 이와 반대로, 도 5에 도시된 바와 같이 시드 간의 오버랩 길이가 지나치게 작게 설정된 경우에는 시드의 일부가 리드 길이 범위를 벗어나게 되므로 이 경우 리드로부터 시드를 추출하는 것이 불가능하다. 따라서 본 발명의 실시예에서는 이와 같은 점을 고려하여 리드에서 시드가 추출되는 영역을 최대화하는 동시에 리드의 범위를 초과하지 않도록 오버랩 길이를 정할 수 있다.

본 발명의 실시예에서, 시드 간의 오버랩 길이는 입력되는 리드의 길이, 시드의 길이 및 개수에 따라 정해진다. 구체적으로, 상기 오버랩 길이는 다음의 수학식 3에 따라 정해질 수 있다.

이때, overlap은 오버랩 길이, R_length는 리드 길이, S_length는 시드 길이, S_num은 시드 개수, k₅ 및 k₆는 각각 오버랩 길이의 범위를 정하기 위한 파라미터로서 각각 0 이상 4 이하의 정수로 정해질 수 있다. 또한 ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수를 각각 의미한다.

한편, 상기 오버랩 길이는 그 의미상 음수가 될 수 없으므로, 상기 k₅ 및 k₆ 경우 다음의 범위를 만족하여야 한다.

예를 들어, k₅=k₆=0으로 가정할 경우, 리드 길이가 75, 시드 길이가 16, 시드 개수가 5로 정해질 때의 오버랩 길이는 상기 수학식 3에 따라 다음과 같이 정해진다.

오버랩 길이 = ceil(max(16*5-75/4,0)) = ceil(1.25) = 2

한편, 본 발명에서 리드로부터 시드를 생성하는 구체적인 방법은 특별히 제한되지 않는다. 즉, 상기 118 단계에서는 리드의 일부 또는 전체를 고려하여 상기 112 단계 내지 116에서 계산된 길이, 개수 및 오버랩 길이를 가지는 복수 개의 시드들을 생성하게 된다. 예를 들어, 리드의 전체, 또는 특정 구간을 복수 개의 조각으로 분할하거나, 분할된 조각들을 조합합으로써 시드들을 생성할 수 있다. 이 경우 생성된 시드들은 서로 연속적으로 연결될 수 있으나 반드시 그러한 것은 아니며, 리드 내에서 서로 떨어진 조각들의 조합으로 시드들을 구성하는 것 또한 가능하다. 요컨대, 본 발명에서 리드로부터 시드를 생성하는 방법은 특별히 제한되지 않으며, 리드의 일부 또는 전체로부터 시드를 추출하는 다양한 알고리즘이 제한 없이 사용될 수 있다.

도 6은 본 발명의 일 실시예에 따른 염기 서열 정렬 시스템(600)의 블록도이다. 본 발명의 일 실시예에 따른 염기 서열 정렬 시스템(300)은 전술한 염기 서열 정렬 방법을 수행하기 위한 장치로서, 시드 길이 계산부(602), 시드 생성부(608) 및 정렬부(610)를 포함하며, 필요에 따라 시드 개수 계산부(604) 및 오버랩 길이 계산부(606)를 더 포함할 수 있다.

시드 길이 계산부(602)는 입력된 리드의 길이에 따라 상기 리드로부터 생성될 시드의 길이를 계산한다. 전술한 바와 같이, 상기 시드의 길이는 상기 리드 길이에 비례하도록 설정될 수 있으며, 구체적으로 전술한 수학식 1에 의하여 상기 시드 길이를 계산할 수 있다.

시드 개수 계산부(604)는 상기 리드 길이 및 시드 길이 계산부(602)에서 계산된 상기 시드 길이에 따라 상기 리드로부터 생성될 시드의 개수를 계산한다. 상기 시드의 개수는 상기 리드 길이에 비례하는 동시에 상기 시드 길이에 반비례하도록 설정될 수 있으며, 구체적으로 전술한 수학식 2에 의하여 상기 시드 개수를 계산할 수 있다.

오버랩 길이 계산부(606)는 상기 리드 길이, 상기 시드 길이 및 상기 시드 개수에 따라 상기 리드로부터 생성될 각 시드들의 오버랩 길이를 계산한다. 이때 상기 오버랩 길이는 전술한 수학식 3에 의하여 계산될 수 있다.

시드 생성부(608)는 계산된 상기 시드 길이, 시드 개수 및 상기 오버랩 길이에 따라 상기 리드로부터 시드를 생성한다.

정렬부(610)는 시드 생성부(608)에서 생성된 상기 시드를 이용하여 상기 리드의 참조 서열에 대한 전역 정렬(global alignment)을 수행한다.

한편, 본 발명의 실시예는 본 명세서에서 기술한 방법들을 컴퓨터상에서 수행하기 위한 프로그램을 포함하는 컴퓨터 판독 가능 기록매체를 포함할 수 있다. 상기 컴퓨터 판독 가능 기록매체는 프로그램 명령, 로컬 데이터 파일, 로컬 데이터 구조 등을 단독으로 또는 조합하여 포함할 수 있다. 상기 매체는 본 발명을 위하여 특별히 설계되고 구성된 것들이거나 컴퓨터 소프트웨어 분야에서 통상의 지식을 가진 자에게 공지되어 사용 가능한 것일 수도 있다. 컴퓨터 판독 가능 기록매체의 예에는 하드 디스크, 플로피 디스크 및 자기 테이프와 같은 자기 매체, CD-ROM, DVD와 같은 광 기록 매체, 플로피 디스크와 같은 자기-광 매체, 및 롬, 램, 플래시 메모리 등과 같은 프로그램 명령을 저장하고 수행하도록 특별히 구성된 하드웨어 장치가 포함된다. 프로그램 명령의 예에는 컴파일러에 의해 만들어지는 것과 같은 기계어 코드뿐만 아니라 인터프리터 등을 사용해서 컴퓨터에 의해서 실행될 수 있는 고급 언어 코드를 포함할 수 있다.

이상에서 대표적인 실시예를 통하여 본 발명에 대하여 상세하게 설명하였으나, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 상술한 실시예에 대하여 본 발명의 범주에서 벗어나지 않는 한도 내에서 다양한 변형이 가능함을 이해할 것이다.

그러므로 본 발명의 권리범위는 설명된 실시예에 국한되어 정해져서는 안 되며, 후술하는 특허청구범위뿐만 아니라 이 특허청구범위와 균등한 것들에 의해 정해져야 한다.

600: 염기 서열 정렬 시스템
602: 시드 길이 계산부
604: 시드 개수 계산부
606: 오버랩 길이 계산부
608: 시드 생성부
610: 정렬부

Claims

입력된 리드의 길이, 상기 리드의 종류 및 참조 서열의 종류에 따라 상기 리드로부터 생성될 시드의 길이를 계산하는 시드 길이 계산부;
상기 리드로부터 계산된 상기 시드 길이를 가지는 하나 이상의 시드를 생성하는 시드 생성부; 및
생성된 상기 시드를 이용하여 상기 리드의 상기 참조 서열에 대한 전역 정렬(global alignment)을 수행하는 정렬부를 포함하고,
상기 시드 길이는 다음의 수학식

(이때, R_length는 리드 길이, S_length는 시드 길이, A는 2.8 이상 3.1 이하의 실수, B는 2.6 이상 3.0 이하의 실수, k₁ 및 k₂는 각각 0 이상 4 이하의 실수, ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수)
에 의하여 계산되는 염기 서열 정렬 시스템.
청구항 1에 있어서,
상기 시드 길이는 상기 리드 길이에 비례하도록 설정되는, 염기 서열 정렬 시스템.
삭제
청구항 1에 있어서,
상기 시드 길이는 15bp 내지 30bp의 범위 내에서 설정되는, 염기 서열 정렬 시스템.
청구항 1에 있어서,
상기 리드 길이가 75bp일 경우, 상기 시드 길이 계산부에서 계산되는 시드의 길이는 15bp 내지 17bp인, 염기 서열 정렬 시스템.
청구항 1에 있어서,
상기 리드 길이가 100bp일 경우, 상기 시드 길이 계산부에서 계산되는 시드의 길이는 16bp 내지 18bp인, 염기 서열 정렬 시스템.
청구항 1에 있어서,
상기 리드 길이가 150bp일 경우, 상기 시드 길이 계산부에서 계산되는 시드의 길이는 17bp 내지 19bp인, 염기 서열 정렬 시스템.
청구항 1에 있어서,
상기 리드 길이 및 계산된 상기 시드 길이에 따라 상기 리드로부터 생성될 시드의 개수를 계산하는 시드 개수 계산부를 더 포함하며,
상기 시드 생성부는, 계산된 상기 시드 길이 및 시드 개수에 따라 상기 리드로부터 시드를 생성하는, 염기 서열 정렬 시스템.
청구항 8에 있어서,
상기 시드 개수는 상기 리드 길이에 비례하는 동시에 상기 시드 길이에 반비례하도록 설정되는, 염기 서열 정렬 시스템.
청구항 8에 있어서,
상기 시드 개수는 다음의 수학식

(이때, R_length는 리드 길이, S_length는 시드 길이, S_num은 시드 개수, k₃ 및 k₄는 각각 0 이상 4 이하의 실수, ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수)
에 의하여 계산되는, 염기 서열 정렬 시스템.
청구항 8에 있어서,
상기 리드 길이가 75bp, 상기 시드 길이가 16bp일 경우, 상기 시드 개수 계산부에서 계산되는 시드의 개수는 4 내지 6개인, 염기 서열 정렬 시스템.
청구항 8에 있어서,
상기 리드 길이가 100bp, 상기 시드 길이가 16bp일 경우, 상기 시드 개수 계산부에서 계산되는 시드의 개수는 6 내지 8개인, 염기 서열 정렬 시스템.
청구항 8에 있어서,
상기 리드 길이가 150bp일, 상기 시드 길이가 17bp일 경우, 상기 시드 개수 계산부에서 계산되는 시드의 개수는 8 내지 10개인, 염기 서열 정렬 시스템.
청구항 8에 있어서,
상기 리드 길이, 상기 시드 길이 및 상기 시드 개수에 따라 상기 리드로부터 생성될 각 시드들의 오버랩 길이를 계산하는 오버랩 길이 계산부를 더 포함하며,
상기 시드 생성부는, 계산된 상기 시드 길이, 시드 개수 및 오버랩 길이에 따라 상기 리드로부터 시드를 생성하는, 염기 서열 정렬 시스템.
청구항 14에 있어서,
상기 오버랩 길이는 다음의 수학식

(이때, overlap은 오버랩 길이, R_length는 리드 길이, S_length는 시드 길이, S_num은 시드 개수, k₅ 및 k₆는 각각 0 이상 4 이하의 실수, ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수)
에 의하여 계산되는, 염기 서열 정렬 시스템.
시드 길이 계산부에서, 입력된 리드의 길이, 상기 리드의 종류 및 참조 서열의 종류에 따라 상기 리드로부터 생성될 시드 길이를 계산하는 단계;
시드 생성부에서, 상기 리드로부터 상기 시드 길이를 가지는 하나 이상의 시드를 생성하는 단계; 및
정렬부에서, 생성된 상기 시드를 이용하여 상기 리드의 상기 참조 서열에 대한 전역 정렬(global alignment)을 수행하는 단계를 포함하고,
상기 시드 길이는 다음의 수학식

(이때, R_length는 리드 길이, S_length는 시드 길이, A는 2.8 이상 3.1 이하의 실수, B는 2.6 이상 3.0 이하의 실수, k₁ 및 k₂는 각각 0 이상 4 이하의 실수, ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수)
에 의하여 계산되는 염기 서열 정렬 방법.
청구항 16에 있어서,
상기 시드 길이는 상기 리드 길이에 비례하도록 설정되는, 염기 서열 정렬 방법.
삭제
청구항 16에 있어서,
상기 시드 길이는 15bp 내지 30bp의 범위 내에서 설정되는, 염기 서열 정렬 방법.
청구항 16에 있어서,
상기 시드 길이를 계산하는 단계의 수행 이후,
시드 개수 계산부에서, 상기 리드 길이 및 계산된 상기 시드 길이에 따라 상기 리드로부터 생성될 시드의 개수를 계산하는 단계를 더 포함하며,
상기 시드를 생성하는 단계는, 계산된 상기 시드 길이 및 시드 개수에 따라 상기 리드로부터 시드를 생성하는, 염기 서열 정렬 방법.
청구항 20에 있어서,
상기 시드 개수는 상기 리드 길이에 비례하는 동시에 상기 시드 길이에 반비례하도록 설정되는, 염기 서열 정렬 방법.
청구항 20에 있어서,
상기 시드 개수는 다음의 수학식

(이때, R_length는 리드 길이, S_length는 시드 길이, S_num은 시드 개수, k₃ 및 k₄는 각각 0 이상 4 이하의 실수, ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수)
에 의하여 계산되는, 염기 서열 정렬 방법.
청구항 20에 있어서,
상기 시드 개수를 계산하는 단계의 수행 이후,
오버랩 길이 계산부에서, 상기 리드 길이, 상기 시드 길이 및 상기 시드 개수에 따라 상기 리드로부터 생성될 각 시드들의 오버랩 길이를 계산하는 단계를 더 포함하며,
상기 시드를 생성하는 단계는, 계산된 상기 시드 길이, 시드 개수 및 오버랩 길이에 따라 상기 리드로부터 시드를 생성하는, 염기 서열 정렬 방법.
청구항 23에 있어서,
상기 오버랩 길이는 다음의 수학식

(이때, overlap은 오버랩 길이, R_length는 리드 길이, S_length는 시드 길이, S_num은 시드 개수, k₅ 및 k₆는 각각 0 이상 4 이하의 실수, ceil(X)는 X보다 크거나 같은 정수 중 가장 작은 정수)
에 의하여 계산되는, 염기 서열 정렬 방법.