| 1 |
1
적어도 하나의 프로그램이 기록된 메모리; 및프로그램을 실행하는 프로세서를 포함하며,프로그램은, 참조 유전체에 대한 필수 인덱스를 메모리에 로딩하는 단계; 메모리 가용량에 상응하는 추가 인덱스를 메모리에 로딩하는 단계; 유전체 서열 정렬할 대상 염기 서열을 읽어들이는 단계;추가 인덱스를 기반으로 대상 염기 서열이 참조 유전체에 일치 정합하는지를 확인하는 단계; 및일치 정합할 경우, 대상 염기 서열과 일치 정합하는 참조 유전체에서의 위치를 이용하여 대상 염기 서열 정렬 결과를 생성하는 단계를 수행하는, 유전체 서열 정렬 가속 장치
|
| 2 |
2
제1 항에 있어서, 프로그램은,추가 인덱스를 메모리에 로딩하는 단계에서, 유전체 서열 정렬의 인덱스에 사용될 메모리 총량에서 필수 인덱스의 크기를 뺀 메모리 가용량을 추가 인덱스 로딩에 사용하는, 유전체 서열 정렬 가속 장치
|
| 3 |
3
제2 항에 있어서, 프로그램은, 추가 인덱스를 메모리에 로딩하는 단계에서, 추가 인덱스가 둘 이상일 경우, 순차적으로 추가 인덱스를 로딩하되, 추가 인덱스를 로딩하는 순서는, 각 인덱스의 유전체 서열 정렬 성능에 미치는 영향을 기준으로 결정되는, 유전체 서열 정렬 가속 장치
|
| 4 |
4
제2 항에 있어서, 프로그램은, 추가 인덱스를 메모리에 로딩하는 단계에서, 메모리 가용량이 로딩 대상인 추가 인덱스의 크기 이상인의 여부에 따라, 추가 인덱스 전체 또는 일부를 로딩하되, 추가 인덱스의 일부를 로딩하는 경우, 해당 추가 인덱스의 필수 부분을 우선적으로 로딩하는, 유전체 서열 정렬 가속 장치
|
| 5 |
5
제1 항에 있어서, 추가 인덱스는, 대상 염기 서열이 참조 유전체에 일치 정합하는지를 확인하는 단계에서 사용되는 제1 인덱스를 포함하되, 제1 인덱스는, 참조 유전체에서 추출된 소정 길이의 시드들 각각에 상응하는 해시 엔트리로 구성된 시드 테이블 및 동일한 시드를 가지는 참조 유전체상의 둘 이상의 위치들을 취합하여 하나의 인덱스에 매핑된 다중 위치 테이블을 포함하는, 유전체 서열 정렬 가속 장치
|
| 6 |
6
제5 항에 있어서, 해시 엔트리는, 시드의 참조 유전체에서의 위치 정보, 해시 엔트리의 해시 충돌 여부 정보, 동일한 해시값을 가지는 다음 번 해시 엔트리의 인덱스 번호 및 다중 위치 테이블 상의 인덱스 정보를 포함하는, 유전체 서열 정렬 가속 장치
|
| 7 |
7
제6 항에 있어서, 프로그램은, 추가 인덱스를 기반으로 참조 유전체에 일치 정합하는지를 확인하는 단계에서, 대상 염기 서열의 해시 값을 계산하는 단계; 해시 값이 시드 테이블 중 로드된 해시 엔트리 개수보다 작은 경우, 해시 값에 해당하는 해시 엔트리를 탐색하는 단계; 해시값에 해당하는 엔트리가 탐색되고, 탐색된 엔트리가 해시 충돌 엔트리가 아닐 경우, 탐색된 엔트리에 저장된 위치 정보를 이용하여 참조 유전체로부터 시드를 추출하는 단계; 추출된 시드(Seed)와 대상 염기 서열의 일치 여부를 확인하는 단계; 및 일치하는 것으로 확인되면, 다중 위치 테이블에서 입력 염기서열에 해당하는 참조 유전체의 모든 일치 정합 부분을 검색하는 단계를 수행하는, 유전체 서열 정렬 가속 장치
|
| 8 |
8
제7 항에 있어서, 프로그램은, 추출된 시드(Seed)와 대상 염기 서열의 일치 여부를 확인하는 단계에서 일치하지 않는 것으로 확인되면, 해시 엔트리의 다음 값에 해당하는 시드 테이블의 엔트리를 탐색하여, 탐색된 시드와 대상 염기 서열의 일치 여부를 확인하는 단계를 더 수행하는, 유전체 서열 정렬 가속 장치
|
| 9 |
9
제1 항에 있어서, 프로그램은,일치 정합하지 않을 경우, 필수 인덱스를 기반으로 참조 유전체에서 대상 염기 서열과 정합되는 최대 부분 정합 탐색을 수행하는 단계;참조 유전체에서 탐색된 최대 부분과 대상 염기 서열의 일치도를 측정하는 단계;일치도의 결과를 생성하는 단계를 포함하되, 최대 부분 정합 탐색을 수행하는 단계에서, 추가 인덱스 중 제2 인덱스를 기반으로 최대 부분 정합 탐색의 초기 부분을 가속하는, 유전체 서열 정렬 가속 장치
|
| 10 |
10
참조 유전체에 대한 필수 인덱스를 메모리에 로딩하는 단계; 메모리 가용량에 상응하는 추가 인덱스를 메모리에 로딩하는 단계; 유전체 서열 정렬할 대상 염기 서열을 읽어들이는 단계;추가 인덱스를 기반으로 대상 염기 서열이 참조 유전체에 일치 정합하는지를 확인하는 단계; 및일치 정합할 경우, 대상 염기 서열과 일치 정합하는 참조 유전체에서의 위치를 이용하여 대상 염기 서열 정렬 결과를 생성하는 단계를 포함하는, 유전체 서열 정렬 가속 방법
|
| 11 |
11
제10 항에 있어서, 추가 인덱스를 메모리에 로딩하는 단계는, 메모리 가용량이 로딩 대상인 추가 인덱스의 크기 이상인의 여부에 따라, 추가 인덱스 전체 또는 일부를 로딩하되, 추가 인덱스의 일부를 로딩하는 경우, 해당 추가 인덱스의 필수 부분을 우선적으로 로딩하는, 유전체 서열 정렬 가속 방법
|
| 12 |
12
제10 항에 있어서, 추가 인덱스는, 대상 염기 서열이 참조 유전체에 일치 정합하는지를 확인하는 단계에서 사용되는 제1 인덱스를 포함하되, 제1 인덱스는, 참조 유전체에서 추출된 소정 길이의 시드들 각각에 상응하는 해시 엔트리로 구성된 시드 테이블 및 동일한 시드를 가지는 참조 유전체상의 둘 이상의 위치들을 취합하여 하나의 인덱스에 매핑된 다중 위치 테이블을 포함하는, 유전체 서열 정렬 가속 방법
|
| 13 |
13
제12 항에 있어서, 해시 엔트리는, 시드의 참조 유전체에서의 위치 정보, 해시 엔트리의 해시 충돌 여부 정보, 동일한 해시값을 가지는 다음 번 해시 엔트리의 인덱스 번호 및 다중 위치 테이블 상의 인덱스 정보를 포함하는, 유전체 서열 정렬 가속 방법
|
| 14 |
14
제13 항에 있어서, 추가 인덱스를 기반으로 참조 유전체에 일치 정합하는지를 확인하는 단계는, 대상 염기 서열의 해시 값을 계산하는 단계; 해시 값이 시드 테이블 중 로드된 해시 엔트리 개수보다 작은 경우, 해시 값에 해당하는 해시 엔트리를 탐색하는 단계; 해시값에 해당하는 엔트리가 탐색되고, 탐색된 엔트리가 해시 충돌 엔트리가 아닐 경우, 탐색된 엔트리에 저장된 위치 정보를 이용하여 참조 유전체로부터 시드를 추출하는 단계; 추출된 시드(Seed)와 대상 염기 서열의 일치 여부를 확인하는 단계; 및 일치하는 것으로 확인되면, 다중 위치 테이블에서 입력 염기서열에 해당하는 참조 유전체의 모든 일치 정합 부분을 검색하는 단계를 포함하는, 유전체 서열 정렬 가속 방법
|
| 15 |
15
제14 항에 있어서, 추출된 시드(Seed)와 대상 염기 서열의 일치 여부를 확인하는 단계에서 일치하지 않는 것으로 확인되면, 해시 엔트리의 다음 값에 해당하는 시드 테이블의 엔트리를 탐색하여, 탐색된 시드와 대상 염기 서열의 일치 여부를 확인하는 단계를 더 포함하는, 유전체 서열 정렬 가속 방법
|
| 16 |
16
제10 항에 있어서, 일치 정합하지 않을 경우, 필수 인덱스를 기반으로 참조 유전체에서 대상 염기 서열과 정합되는 최대 부분 정합 탐색을 포함하는 단계;참조 유전체에서 탐색된 최대 부분과 대상 염기 서열의 일치도를 측정하는 단계;일치도의 결과를 생성하는 단계를 포함하되, 최대 부분 정합 탐색을 수행하는 단계에서, 추가 인덱스 중 제2 인덱스를 기반으로 최대 부분 정합 탐색의 초기 부분을 가속하는, 유전체 서열 정렬 가속 방법
|
| 17 |
17
참조 유전체에 대한 필수 인덱스를 메모리에 로딩하는 단계; 메모리 가용량에 상응하는 추가 인덱스를 메모리에 로딩하는 단계; 유전체 서열 정렬할 대상 염기 서열을 읽어들이는 단계;추가 인덱스 중 제1 인덱스를 기반으로 대상 염기 서열이 참조 유전체에 일치 정합하는지를 확인하는 단계; 일치 정합할 경우, 대상 염기 서열과 일치 정합하는 참조 유전체에서의 위치를 이용하여 대상 염기 서열 정렬 결과를 생성하는 단계;일치 정합하지 않을 경우, 필수 인덱스를 기반으로 참조 유전체에서 대상 염기 서열과 정합되는 최대 부분 정합 탐색을 수행하는 단계;참조 유전체에서 탐색된 최대 부분과 대상 염기 서열의 일치도를 측정하는 단계; 및일치도의 결과를 생성하는 단계를 수행하되, 최대 부분 정합 탐색을 수행하는 단계에서, 추가 인덱스 중 제2 인덱스를 기반으로 최대 부분 정합 탐색의 초기 부분을 가속하는, 유전체 서열 정렬 가속 방법
|
| 18 |
18
제17 항에 있어서, 제1 인덱스는, 참조 유전체에서 추출된 소정 길이의 시드들 각각에 상응하는 해시 엔트리로 구성된 시드 테이블 및 동일한 시드를 가지는 참조 유전체상의 둘 이상의 위치들을 취합하여 하나의 인덱스에 매핑된 다중 위치 테이블을 포함하되, 해시 엔트리는, 시드의 참조 유전체에서의 위치 정보, 해시 엔트리의 해시 충돌 여부 정보, 동일한 해시값을 가지는 다음 번 해시 엔트리의 인덱스 번호 및 다중 위치 테이블 상의 인덱스 정보를 포함하는, 유전체 서열 정렬 가속 장치
|
| 19 |
19
제18 항에 있어서, 제1 인덱스를 기반으로 참조 유전체에 일치 정합하는지를 확인하는 단계는, 대상 염기 서열의 해시 값을 계산하는 단계; 해시 값이 시드 테이블 중 로드된 해시 엔트리 개수보다 작은 경우, 해시 값에 해당하는 해시 엔트리를 탐색하는 단계; 해시값에 해당하는 엔트리가 탐색되고, 탐색된 엔트리가 해시 충돌 엔트리가 아닐 경우, 탐색된 엔트리에 저장된 위치 정보를 이용하여 참조 유전체로부터 시드를 추출하는 단계; 추출된 시드(Seed)와 대상 염기 서열의 일치 여부를 확인하는 단계; 및 일치하는 것으로 확인되면, 다중 위치 테이블에서 입력 염기서열에 해당하는 참조 유전체의 모든 일치 정합 부분을 검색하는 단계를 수행하는, 유전체 서열 정렬 가속 방법
|
| 20 |
20
제19 항에 있어서, 추출된 시드(Seed)와 대상 염기 서열의 일치 여부를 확인하는 단계에서 일치하지 않는 것으로 확인되면, 해시 엔트리의 다음 값에 해당하는 시드 테이블의 엔트리를 탐색하여, 탐색된 시드와 대상 염기 서열의 일치 여부를 확인하는 단계를 더 포함하는, 유전체 서열 정렬 가속 방법
|
