일반기술

바이클러스터링 방법 및 장치

본 기술은 높은 생물학적 기능관련성을 지니는 바이클러스터를 찾아내기 위한 폴리노미얼(polynomial) 시간 복잡도를 가지는 바이클러스터링 기법에 관한 것이다. 바이클러스터링은 2차원 마이크로어레이 데이터에 대해서 같은 기능을 하는 유전자와 그 기능이 발현되는 샘플들을 클러스터링하는 기법을 통칭한다. 일부의 기존 바이클러스터링기법은 트리를 유지하며 바이클러스터를 도출하고 있다. 이러한 트리는 허용 노이즈 정도를 높일 수록, 시간 복잡도가 지수적으로 커지는 특징을 가지고 있다. 따라서 트리를 탐색해 나가며 바이클러스터를 찾아나가는 프로세스 또한 지수적인 시간 복잡도를 가지며, 결과적으로 얻어지는 바이클러스터의 개수와 찾아진 바이클러스터 간의 유사성 또한 커진다. 본 발명은 노이즈가 심한 마이크로어레이 데이터에 대해서도 생물학적인 의미를 가지는 숨은 바이클러스터를 찾아낼 수 있도록 하기 위해서, 허용 노이즈값을 크게 설정해도 시간 복잡도가 지수적으로 증가하지 않도록 하는 새로운 트리 및 큐 구조를 제시하는 것을 특정으로 한다. 트리는 넓이 우선 탐색 트리를 기본 골격으로 하나, 효율적인 트리의 탐색을 위해서 트리의 각 레벨마다 특정 우선 순위 계산법을 도입한 복수 개의 우선 순위 큐를 운영함으로써 프루닝을 수행한다. 우선 순위 큐의 집합에 남아 있는 바이클러스터들은 결과적으로 생물학적 검증 가능한 연관 관계를 가지는 유전자 집합을 포함하며, 서로 간에 많이 중복되지 않으며 그 다양성을 유지할 수 있는 특징을 가진다.