| 1 |
1
암 환자의 기수를 판별하기 위한, 단백질의 생물학적 기능 연관성을 갖는 바이클러스터 형태의 매크로 클러스터를 생성하는 매크로 클러스터링 방법으로서,
(a) 마이크로어레이 데이터에서 적어도 하나의 유전자를 포함하는 유전자 샘플을 추출하며, 상기 추출된 유전자 샘플에 따른 유전자 발현값이 적어도 하나의 비닝(binning) 기준 범위에 속하는지 여부를 판별하는 단계;
(b) 상기 판별 결과로 상기 유전자가 상기 비닝 기준 범위에 속하면, 상기 비닝 기준 범위에 속하는 상기 유전자의 집합 및 상기 유전자가 속하는 상기 유전자 샘플을 결합하여 바이클러스터 형태의 매크로 클러스터들을 생성하는 단계; 및
(c) 상기 생성된 매크로 클러스터들 중에서 상기 유전자의 집합의 크기가 미리 정해진 최대가 아니라는 조건에 부합하는 매크로 클러스터들을 추출하고, 상기 추출된 매크로 클러스터들을 노드로 하는 탐색 트리를 생성하며, 상기 생성된 탐색 트리를 이용하여 상기 조건에 부합하는 매크로 클러스터를 추가 생성하는 단계
를 포함하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 2 |
2
제 1 항에 있어서,
상기 (c) 단계는 더이상 상기 조건에 부합하는 매크로 클러스터가 추가 생성되지 않거나, 상기 추가 생성된 매크로 클러스터에 포함되는 상기 마이크로어레이 데이터의 부분 행렬 데이터 값이 상기 추가 생성된 매크로 클러스터에 포함되는 상기 유전자의 개수보다 작거나 같으면 상기 매크로 클러스터의 추가 생성을 종료하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 3 |
3
제 1 항에 있어서,
상기 (a) 단계는,
(aa) 상기 마이크로어레이 데이터의 각 열을 정규화시키며, 상기 정규화로부터 상기 유전자 샘플을 추출하는 단계;
(ab) 상기 유전자 발현값으로부터 최소값과 최대값을 구하고, 상기 최소값과 상기 최대값 사이를 범위로 하는 적어도 하나의 상기 비닝 기준 범위를 생성하는 단계; 및
(ac) 상기 (aa) 단계에서 추출된 유전자 샘플에 포함되는 상기 유전자 발현값이 상기 (ab) 단계에서 생성된 비닝 기준 범위에 비닝하는지 여부를 판별하는 단계
를 포함하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 4 |
4
제 1 항에 있어서,
상기 (c) 단계에서 상기 탐색 트리를 생성하는 단계는 상기 유전자 샘플의 개수가 적어도 두개인 제1 매크로 클러스터 및 상기 제1 매크로 클러스터에 포함된 유전자 집합을 모두 포함하며 상기 제1 매크로 클러스터보다 상기 유전자 샘플의 개수가 더 많은 제2 매크로 클러스터를 이용하여 상기 탐색 트리를 생성하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 5 |
5
제 4 항에 있어서,
상기 (c) 단계에서 상기 탐색 트리를 생성하는 단계는,
(ca) 상기 생성된 매크로 클러스터들을 노드로 하는 트리를 생성하는 단계;
(cb) 적어도 하나의 우선순위 큐를 이용하여 상기 생성된 트리의 레벨마다 프루닝을 수행하는 단계; 및
(cc) 상기 프루닝을 통하여 상기 제1 매크로 클러스터를 부모 노드로 하고 상기 제2 매크로 클러스터를 자식 노드로 하는 상기 탐색 트리를 구축하는 단계
를 포함하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 6 |
6
제 1 항에 있어서,
상기 (c) 단계에서 상기 조건에 부합하는 매크로 클러스터들을 추출하는 단계는,
(ca') 상기 생성된 매크로 클러스터가 상기 마이크로어레이 데이터의 전체 유전자 샘플 중 일부만을 포함하면, 포함하지 않는 적어도 하나의 상기 유전자 샘플을 이용하여 상기 매크로 클러스터가 다른 매크로 클러스터에 대해 가지는 유사도 값을 측정하는 단계; 및
(cb') 상기 측정 결과로부터 상기 조건에 부합하지 않는 매크로 클러스터를 제거시켜 상기 조건에 부합하는 매크로 클러스터들을 추출하는 단계
를 포함하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 7 |
7
삭제
|
| 8 |
8
제 5 항에 있어서,
상기 (cb) 단계는 상기 유전자 집합의 크기를 우선순위 측정 함수로 하는 상기 우선순위 큐를 이용하여 상기 프루닝을 수행하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 9 |
9
제 5 항에 있어서,
상기 (cb) 단계는 상기 우선순위 큐를 2개 이용하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 10 |
10
제 1 항에 있어서,
상기 (a) 단계는 상기 유전자 샘플을 추출하기 위한 입력값으로 상기 마이크로어레이 데이터의 전체 유전자 집합과 상기 마이크로어레이 데이터의 전체 샘플 집합을 포함하는 상기 마이크로어레이 데이터, 상기 생성된 매크로 클러스터를 만족하는 유전자의 최소 개수, 상기 생성된 매크로 클러스터를 만족하는 유전자 샘플의 최소 개수, 사용자 입력값, 비교 대상인 두 매크로 클러스터의 유사성 판단 기준값, 우선순위 큐의 개수, 및 상기 우선순위 큐의 크기 중 적어도 하나를 입력하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 11 |
11
제 1 항에 있어서,
상기 (c) 단계에 따라 생성되는 매크로 클러스터들은 상기 생성된 탐색 트리에서의 레벨이 적어도 2인 것을 특징으로 하는 매크로 클러스터링 방법
|
| 12 |
12
제 1 항에 있어서,
상기 (b) 단계는 아래 조건을 만족하는 클러스터를 상기 매크로 클러스터로 생성하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 13 |
13
제 12 항에 있어서,
상기 (b) 단계는 아래 조건을 만족하는 상기 매크로 클러스터를 적어도 하나 생성하며, 최초에 적어도 하나의 상기 유전자 집합과 1개의 상기 유전자 샘플로 이루어진 상기 매크로 클러스터를 생성하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 14 |
14
제 9 항에 있어서,
상기 (cb) 단계에서의 상기 2개의 우선순위 큐 중에서 적어도 하나는 아래 수학식을 우선순위 측정 함수로 설정하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 15 |
15
제 1 항에 있어서,
상기 (c) 단계는,
(ca'') 상기 p가 1일 때, |T| ≥ mg를 만족하는 p-MAC이 생성되는지 여부를 판별하는 단계;
(cb'') 상기 p-MAC이 더 생성된다면, 미리 정해진 샘플 si를 샘플 집합으로 하는 1-MAC을 고려하여 p-MAC으로부터 (p+1)-MAC을 검출하는 단계;
(cc'') 상기 검출된 (p+1)-MAC이 |T'| ≥ mg를 만족하면 상기 검출된 (p+1)-MAC을 제1 우선순위 큐 또는 제2 우선순위 큐에 저장하며, 상기 검출된 (p+1)-MAC이 |T'| ≥ mg를 만족하지 않으면 두 매크로 클러스터의 유사성 판단 기준값에 의해 두 큐에 저장된 (p+1)-MAC를 제거하는 단계;
(cd'') (p+1) ≥ ms이면 상기 제1 우선순위 큐에 저장된 모든 (p+1)-MAC과 상기 제2 우선순위 큐에 저장된 모든 (p+1)-MAC을 출력하는 단계;
(ce'') 상기 두 큐를 비우는 단계; 및
(cf'') 상기 p를 p+1로 설정하는 단계
를 포함하며,
상기 p는 상기 유전자 샘플의 개수, 상기 T는 상기 마이크로어레이 데이터의 전체 샘플 집합에 속하는 상기 마이크로어레이 데이터의 부분 행렬 데이터, 상기 mg는 상기 생성된 매크로 클러스터를 만족하는 유전자의 최소 개수, 상기 p-MAC은 상기 유전자 샘플의 개수가 p인 매크로 클러스터, 상기 O는 상기 마이크로어레이 데이터의 전체 유전자 집합에 속하는 상기 마이크로어레이 데이터의 부분 행렬 데이터, 상기 ms는 상기 생성된 매크로 클러스터를 만족하는 상기 유전자 샘플의 최소 개수, 및 T'=T∪{si}인 것을 특징으로 하는 매크로 클러스터링 방법
|
| 16 |
16
제 6 항에 있어서,
상기 (ca') 단계에서 측정된 유사도 값은 아래 수학식으로부터 도출되는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 17 |
17
제 1 항에 있어서,
상기 (c) 단계는 상기 생성된 탐색 트리로 넓이 우선 탐색 트리를 이용하는 것을 특징으로 하는 매크로 클러스터링 방법
|
| 18 |
18
삭제
|
| 19 |
19
컴퓨터로 판독 가능한 기록매체에 있어서,
제 1 항 내지 제 6 항 중 어느 한 항에 따른 방법, 또는 제 8 항 내지 제 17 항 중 어느 한 항에 따른 방법을 구현하는 프로그램이 기록되는 기록매체
|
| 20 |
20
암 환자의 기수를 판별하기 위한, 단백질의 생물학적 기능 연관성을 갖는 바이클러스터 형태의 매크로 클러스터를 생성하는 매크로 클러스터링 장치로서,
마이크로어레이 데이터에서 적어도 하나의 유전자를 포함하도록 추출된 유전자 샘플에 따른 유전자 발현값이 적어도 하나의 비닝(binning) 기준 범위에 속하는지 여부를 판별하는 비닝 판별부;
상기 판별 결과로 상기 유전자가 상기 비닝 기준 범위에 속하면, 상기 비닝 기준 범위에 속하는 상기 유전자의 집합 및 상기 유전자가 속하는 상기 유전자 샘플을 결합하여 바이클러스터 형태의 매크로 클러스터들을 생성하는 매크로 클러스터 생성부; 및
상기 생성된 매크로 클러스터들 중에서 상기 유전자의 집합의 크기가 미리 정해진 최대가 아니라는 조건에 부합하는 매크로 클러스터들이 도출되면, 상기 도출된 매크로 클러스터들을 노드로 하는 탐색 트리를 생성하며, 상기 매크로 클러스터 생성부와 연동하여 상기 조건에 부합하는 매크로 클러스터가 추가 생성되면 상기 추가 생성된 매크로 클러스터를 상기 생성된 탐색 트리에 반영시키는 탐색 트리 생성부
를 포함하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 21 |
21
제 20 항에 있어서,
상기 매크로 클러스터 생성부는 더이상 상기 조건에 부합하는 매크로 클러스터가 추가 생성되지 않거나, 상기 추가 생성된 매크로 클러스터에 포함되는 상기 마이크로어레이 데이터의 부분 행렬 데이터 값이 상기 추가 생성된 매크로 클러스터에 포함되는 상기 유전자의 개수보다 작거나 같으면 상기 매크로 클러스터의 추가 생성을 종료하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 22 |
22
제 21 항에 있어서,
상기 마이크로어레이 데이터의 각 열을 정규화시키며, 상기 정규화로부터 상기 유전자 샘플을 추출하는 유전자 샘플 추출부; 및
상기 유전자 발현값으로부터 최소값과 최대값을 구하고, 상기 최소값과 상기 최대값 사이를 범위로 하는 적어도 하나의 상기 비닝 기준 범위를 도출하는 비닝 기준 범위 생성부
를 더 포함하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 23 |
23
제 21 항에 있어서,
상기 탐색 트리 생성부는 상기 탐색 트리를 생성할 때에 상기 매크로 클러스터로 상기 유전자 샘플의 개수가 적어도 두개인 제1 매크로 클러스터 및 상기 제1 매크로 클러스터에 포함된 유전자 집합을 모두 포함하며 상기 제1 매크로 클러스터보다 상기 유전자 샘플의 개수가 더 많은 제2 매크로 클러스터를 이용하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 24 |
24
제 23 항에 있어서,
상기 탐색 트리 생성부는,
상기 생성된 매크로 클러스터들을 노드로 하는 트리를 생성하는 토대 마련부;
적어도 하나의 우선순위 큐를 이용하여 상기 생성된 트리의 레벨마다 프루닝을 수행하는 프루닝부; 및
상기 프루닝을 통하여 상기 제1 매크로 클러스터를 부모 노드로 하고 상기 제2 매크로 클러스터를 자식 노드로 하는 상기 탐색 트리를 구축하는 트리 구축부
를 포함하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 25 |
25
제 21 항에 있어서,
상기 조건에 부합하는 매크로 클러스터들을 추출하는 매크로 클러스터 추출부
를 더 포함하며,
상기 매크로 클러스터 추출부는,
상기 생성된 매크로 클러스터가 상기 마이크로어레이 데이터의 전체 유전자 샘플 중 일부만을 포함하면, 포함하지 않는 적어도 하나의 상기 유전자 샘플을 이용하여 상기 매크로 클러스터가 다른 매크로 클러스터에 대해 가지는 유사도 값을 측정하는 유사도 값 측정부; 및
상기 측정 결과로부터 상기 조건에 부합하지 않는 매크로 클러스터를 제거시키는 클러스터 제거부
를 포함하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 26 |
26
삭제
|
| 27 |
27
제 24 항에 있어서,
상기 프루닝부는 상기 유전자 집합의 크기를 우선순위 측정 함수로 하는 상기 우선순위 큐를 이용하여 상기 프루닝을 수행하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 28 |
28
제 24 항에 있어서,
상기 프루닝부는 상기 우선순위 큐를 2개 이용하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 29 |
29
제 22 항에 있어서,
상기 유전자 샘플 추출부로 상기 유전자 샘플을 추출하기 위한 입력값을 입력하는 입력부
를 더 포함하며,
상기 입력부는 상기 마이크로어레이 데이터의 전체 유전자 집합과 상기 마이크로어레이 데이터의 전체 샘플 집합을 포함하는 상기 마이크로어레이 데이터, 상기 생성된 매크로 클러스터를 만족하는 유전자의 최소 개수, 상기 생성된 매크로 클러스터를 만족하는 유전자 샘플의 최소 개수, 사용자 입력값, 비교 대상인 두 매크로 클러스터의 유사성 판단 기준값, 우선순위 큐의 개수, 및 상기 우선순위 큐의 크기 중 적어도 하나를 상기 입력값으로 입력하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 30 |
30
제 21 항에 있어서,
상기 매크로 클러스터 생성부는 최초에 적어도 하나의 상기 유전자 집합과 1개의 상기 유전자 샘플로 이루어진 상기 매크로 클러스터를 생성하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 31 |
31
제 21 항에 있어서,
상기 탐색 트리 생성부는 상기 탐색 트리로 넓이 우선 탐색 트리를 생성하는 것을 특징으로 하는 매크로 클러스터링 장치
|
| 32 |
32
삭제
|
