| 1 |
1
리드 서열들로부터 시드들을 생성하는 시드 생성부;상기 시드들 중 중복된 시드들을 검색하고, 상기 중복된 시드들에 대한 정보를 기초로 상기 시드들을 색인하며, 상기 시드들로부터 상기 중복된 시드들이 제거된 시드 집합을 생성하는 중복 시드 제거부;상기 시드 집합을 참조 유전체에 대하여 정렬하는 시드 정렬부; 및상기 시드들의 색인 결과 및 상기 시드 집합의 정렬 결과를 참조하여, 상기 리드 서열들을 상기 참조 유전체에 대하여 정렬하는 리드 서열 정렬부를 포함하는 리드 서열 정렬 장치
|
| 2 |
2
제 1항에 있어서,상기 중복 시드 제거부는 시드 테이블을 이용하여 상기 시드들을 색인하며,상기 시드 테이블은 해시 테이블 알고리즘을 기반으로 생성되는 리드 서열 정렬 장치
|
| 3 |
3
제 2항에 있어서,상기 시드 테이블은 각 시드에 대한 중복 횟수, 상기 각 시드가 포함되는 리드 서열 ID 및 상기 리드 서열에 대한 상기 각 시드의 위치 정보를 포함하는 리드 서열 정렬 장치
|
| 4 |
4
제 3항에 있어서,상기 리드 서열 ID 및 상기 리드 서열에 대한 상기 각 시드의 위치 정보는 연결 리스트 형태로 저장되는 리드 서열 정렬 장치
|
| 5 |
5
제 2항에 있어서,상기 시드 테이블을 저장하는 시드 테이블 저장부를 더 포함하고,상기 리드 서열 정렬부는 상기 시드 테이블 저장부로부터 상기 시드 테이블을 로드하여 상기 리드 서열들을 상기 참조 유전체에 대하여 정렬하는 리드 서열 정렬 장치
|
| 6 |
6
제 2항에 있어서,상기 참조 유전체는 미리 색인되며, 상기 시드 정렬부는 상기 참조 유전체의 색인 결과 및 상기 시드 테이블을 참조하여 상기 시드 집합을 상기 참조 유전체에 대하여 정렬하는 리드 서열 정렬 장치
|
| 7 |
7
제 6항에 있어서,상기 참조 유전체는 해시 테이블을 이용하여 색인되며,상기 시드 정렬부는 상기 해시 테이블 및 상기 시드 테이블을 참조하여 상기 시드 집합을 상기 참조 유전체에 대하여 정렬하는 리드 서열 정렬 장치
|
| 8 |
8
제 2항에 있어서,상기 리드 서열 정렬부는 상기 시드 테이블 및 시드 집합 정렬 결과를 참조하여 시드 클러스터들을 생성하고, 상기 시드 클러스터들을 기초로 리드 서열 후보 위치들을 선정하며, 상기 선정된 리드 서열 후보 위치들에 대하여 상기 리드 서열들을 정렬하는 리드 서열 정렬 장치
|
| 9 |
9
제 8항에 있어서,상기 리드 서열 정렬부는 상기 시드 클러스터들을 후보 조건을 기초로 스코어링하여 상기 리드 서열 후보 위치들을 선정하며, 상기 후보 조건은 상기 시드 클러스터들에 포함되는 시드들의 수, 상기 시드 클러스터들에 포함되는 상기 시드들 사이의 순서 및 상기 시드 클러스터들에 포함되는 상기 시드들 사이의 거리를 포함하는 리드 서열 정렬 장치
|
| 10 |
10
리드 서열들로부터 시드들을 생성하는 단계;상기 시드들 중 중복되는 시드들을 검색하는 단계;상기 중복된 시드들에 대한 정보를 기초로 상기 시드들을 색인하는 단계;상기 시드들로부터 상기 중복된 시드들이 제거된 시드 집합을 생성하는 단계;상기 시드 집합을 참조 유전체에 대하여 정렬하는 단계; 및상기 시드들의 색인 결과 및 상기 시드 집합의 정렬 결과를 참조하여, 상기 리드 서열들을 상기 참조 유전체에 대하여 정렬하는 단계를 포함하는 리드 서열 정렬 방법
|
| 11 |
11
제 10항에 있어서,상기 중복된 시드들에 대한 정보를 기초로 상기 시드들을 색인하는 단계는 상기 중복된 시드들에 대한 정보를 기초로 시드 테이블을 생성하는 단계이고,상기 시드 테이블은 해시 테이블 알고리즘을 기반으로 생성되는 리드 서열 정렬 방법
|
| 12 |
12
제 11항에 있어서,상기 시드들의 색인 결과 및 상기 시드 집합의 정렬 결과를 참조하여, 상기 리드 서열들을 상기 참조 유전체에 대하여 정렬하는 단계는상기 시드 집합 정렬 결과를 참조하여 시드 클러스터들을 생성하는 단계;상기 시드 테이블을 참조하여, 상기 시드 클러스터들을 후보 조건을 기초로 스코어링하는 단계;상기 시드 클러스터들의 스코어링된 스코어와 미치 지정된 임계값을 비교하여 리드 서열 후보 위치들을 선정하는 단계; 및상기 리드 서열 후보 위치들에 대하여 리드 서열들을 정렬하는 단계를 포함하는 리드 서열 정렬 방법
|
| 13 |
13
제 12항에 있어서,상기 후보 조건은 상기 시드 클러스터들에 포함되는 시드들의 수, 상기 시드 클러스터들에 포함되는 상기 시드들 사이의 순서 및 상기 시드 클러스터들에 포함되는 시드들 사이의 거리를 포함하는 리드 서열 정렬 방법
|
| 14 |
14
제 13항에 있어서,상기 리드 서열 후보 위치의 길이는 상기 시드 클러스터들에 포함된 최선행 및 최후행 시드의 위치 및 미리 지정된 허용 갭 길이를 고려하여 결정되는 리드 서열 정렬 방법
|
