정렬된 리드의 통계적 분석을 기반으로 하는 CNV 검색 알고리즘

홍상균,홍동완,윤지희,김백섭,박상현,Hong, Sang-Kyoon,Hong, Dong-Wan,Yoon, Jee-Hee,Kim, Baek-Sop,Park, Sang-Hyun 한국정보처리학회 2009 정보처리학회논문지D Vol.16 No.5

인간의 유전체 서열에는 유전체 단위반복변위(copy number variation, CNV)를 포함하는 다양한 유전적 구조 변이(genetic structural variation)가 존재하며, 이는 기능적으로 질병에 대한 감수성, 치료에 대한 반응, 유전적 특성 등과 밀접한 관련이 있다. 본 논문에서는 기가 시퀀싱(giga sequencing)의 결과 산출되는 대량의 짧은 길이의 DNA 서열 데이터를 이용한 새로운 CNV 검색 방식을 제안한다. 제안하는 알고리즘에서는 레퍼런스 시퀀스에 DNA 서열 데이터를 서열 정렬시켜 각 레퍼런스 시퀀스의 위치에 대한 서열 데이터의 출현 빈도 정보를 얻은 후, 출현 빈도 정보의 패턴을 분석하여 통계적 유의성을 갖는 1kbp 이상의 연속 영역을 CNV 후보 영역으로 추출한다. 또한 제안된 알고리즘을 효율적으로 지원하기 위한 서열 정렬 방식에 대한 비교 및 분석을 수행한다. 제안된 기법의 유용성을 규명하기 위하여 다양한 실험을 수행하였다. 실험 결과에 의하면, 제안된 기법은 비교적 낮은 커버리지의 기가 시퀀싱 데이터를 이용하여 반복되거나 결실되는 다양한 형태의 CNV 영역을 효율적으로 검출하며, 또한 작은 사이즈의 CNV 영역에서부터 큰 사이즈의 CNV 영역까지 다양한 크기의 CNV 영역을 효율적으로 검출 할 수 있는 것으로 나타났다. Recently it was found that various genetic structural variations such as CNV(copy number variation) exist in the human genome, and these variations are closely related with disease susceptibility, reaction to treatment, and genetic characteristics. In this paper we propose a new CNV detection algorithm using millions of short DNA sequences generated by giga-sequencing technology. Our method maps the DNA sequences onto the reference sequence, and obtains the occurrence frequency of each read in the reference sequence. And then it detects the statistically significant regions which are longer than 1Kbp as the candidate CNV regions by analyzing the distribution of the occurrence frequency. To select a proper read alignment method, several methods are employed in our algorithm, and the performances are compared. To verify the superiority of our approach, we performed extensive experiments. The result of simulation experiments (using a reference sequence, build 35 of NCBI) revealed that our approach successfully finds all the CNV regions that have various shapes and arbitrary length (small, intermediate, or large size).

통합 마이크로어레이 데이터를 위한 기능 분석 시스템의 구현

홍상균(Sang-Kyoon Hong),이종근(Jong-Keun Lee),홍동완(Dong-wan Hong),윤지희(Jee-Hee Yoon) 한국정보과학회 강원지부 2007 한국정보과학회 강원지부 학술대회 논문집 Vol.1 No.1

마이크로어레이 실험에서는 샘플 수가 많을수록 통계적으로 유의한 실험 결과를 보장할 수 있다. 그러나 마이크로어레이 실험은 아직 고가의 실험으로 분류되어 다수의 샘플을 동시에 사용한 실험 결과를 얻기 어려운 상황이다. 기존의 다수의 실험 데이터를 통합하여 전체 샘플 사이즈를 늘릴 수 있다면 통계적으로 보다 유의한 분석결과를 도출할 수 있다. 본 연구에서는 통합 마이크로어레이를 위한 유전자 기능 분석 시스템을 제안한다. 본 시스템은 사용자 지정에 따라 플랫폼, 정규화 기법, 데이터 포맷 등이 상이한 다수의 마이크로어레이 실험 데이터를 통합하고, 통합 데이터로부터 유의 유전자를 추출하며, 유전자 온토로지를 기반으로 유전자 기능 분석을 수행한다.

CNV 영역 검색 알고리즘

홍상균 ( Sang-kyoon Hong ),홍동완 ( Dong-wan Hong ),윤지희 ( Jee-hee Yoon ) 한국정보처리학회 2008 한국정보처리학회 학술대회논문집 Vol.15 No.2

최근 생물정보학 분야에서 인간 유전체에 존재하는 CNV(copy number variation)에 관한 연구가 주목 받고 있다. CNV 영역은 lkbp~3Mbp 사이의 서열이 반복되거나 결실되는 변이 영역으로 정의된다. 우리는 선행 연구에서 기가 시퀀싱(giga sequencing)의 결과 산줄되는 DNA 서열 조각인 리드(read)를 레퍼런스 시퀀스에 서열 정렬하여 CNV 영역을 찾아내는 새로운 CNV 검색 방식을 제안하였다. 후속 연구로서 본 논문에서는 DNA 서열에 존재하는 repeat 영역 문제를 해결하기 위한 새로운 방안을 제안하고, 리드의 출현 빈도 정보를 분석하여 CNV 영역을 찾아내는 CNV 영역 검색 알고리즘을 보인다. 제안된 알고리즘은 Gaussian 분포를 갖는 출현 빈도 정보로부터 통계적 유의성을 갖는 영역을 추출하여 CNV 영역 후보로 하고, 다음 정제 과정을 거쳐 최종의 CNV 영역을 추출한다. 성능 평가를 위하여 프로토타입 시스템을 개발하였으며, 시뮬레이션 실험을 수행하였다. 실험 결과에 의하여 제안된 방식은 반복되거나 결실되는 형태의 CNV 영역을 효율적으로 검출하며, 또한 다양한 크기의 CNV 영역을 효율적으로 검출할 수 있음을 입증한다.

차세대 시퀀싱 데이터를 위한 SNP 분석 방법

홍상균 ( Sang-kyoon Hong ),이덕해 ( Deok-hae Lee ),공진화 ( Jin-hwa Kong ),김덕근 ( Deok-keun Kim ),홍동완 ( Dong-wan Hong ),윤지희 ( Jee-hee Yoon ) 한국정보처리학회 2010 한국정보처리학회 학술대회논문집 Vol.17 No.2

최근 차세대 시퀀싱 기술의 급속한 발전에 따라 서열 정보의 해독이 비교적 쉬워지면서 개인별 맞춤 의학의 실현에 대한 기대와 관심이 높아지고 있다. 각 개인의 서열 정보 사이에는 SNP (single nucleotide polymorphism), Indel, CNV (copy number variation) 등의 다양한 유전적 구조 변이가 존재하며, 이러한 서열 정보의 부분적 차이는 각 개인의 유전적 특성 및 질병 감수성 등과 밀접한 관련을 갖는다. 본 연구에서는 차세대 시퀀싱 결과로 산출되는 수많은 짧은 DNA 서열 조각인 리드 데이터를 이용한 SNP 추출 알고리즘을 제안한다. 제안된 알고리즘에서는 레퍼런스 시퀀스의 각 위치에 대한 리드 시퀀스의 매핑 정보를 기반으로 SNP 후보 영역을 추출하며, 품질 정보 등을 활용하여 에러 발생률을 최소화한다. 또한 대규모 시퀀싱 데이터와 SNP 구조 변이 데이터의 효율적인 저장/검색을 지원하는 시각적 분석 도구를 구현하여 제안된 방식의 유용성을 검증한다.

GSDAT : 기가 시퀀싱 데이터 분석을 위한 도구

홍상균(Sang-Kyoon Hong),이상진(Sang-Jin Lee),김덕근(Deok-Keun Kim),공진화(Jin-Hwa Kong),윤지희(Jee-Hee Yoon) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2C

최근, 기가시퀀싱(giga-sequencing) 기술의 발달로 비교적 저렴한 비용으로 개인의 유전체 시퀀싱이 가능해지고 있다. 하지만 기가시퀀싱 기술의 빠른 발전 속도에 비해 이들 데이터 처리를 위한 분석 도구의 개발은 매우 미비한 상황이다. 본 논문에서는 기가 시퀀싱 결과로 산출되는 수많은 짧은 DNA 서열조각인 리드를 레퍼런스 서열에 매핑한 결과를 관리, 분석하는 도구, GSDAT를 제안한다. GSDAT는 다양한 매핑결과 포맷을 통합하는 스키마와 이를 데이터베이스화하여 저장, 관리하는 시스템을 제공한다. 또한 매핑결과의 커버리지 분석을 위한 고해상도의 뷰어 기능을 제공하며, 사용자의 요구에 따라 다양한 유전체 데이터베이스와 연동되어 유전자 정보, 리피트 영역, 변이 영역 등과 같은 생물학 정보를 실시간으로 제공한다.

DNA 시퀀스 검색을 위한 효율적인 인덱스 기법

홍상균(Sang-Kyoon Hong),원정임(JungIm Won),윤지희(JeeHee Yoon) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.2C

DNA 시퀀스 데이터베이스 규모의 급격한 증가 추세를 고려할 때, DNA 시퀀스 검색 연산을 보다 효과적으로 지원할 수 있는 인덱싱 및 질의 처리 기술이 요구 된다. 접미어 트리는 DNA 시퀀스 검색을 위한 좋은 인덱스 구조로 알려져 왔다. 그러나 접미어 트리는 그 구조적 특성으로 인하여 저장공간, 검색 성능, DBMS와의 통합 등의 문제점을 갖는다. 본 논문에서는 이와 같은 접미어 트리의 문제점들을 해결하는 DNA 시퀀스 검색을 위한 새로운 인덱스 구조를 제안하고, 이를 기반으로 하는 효율적인 질의 처리 방식을 제안한다. 제안된 인덱스 기법은 이진 트라이를 기본 구조로 채택하며 DNA 시퀀스의 윈도우 서브 시퀀스를 인덱싱 대상으로 한다. 유사 서브 시퀀스 검색을 위한 질의 처리 알고리즘은 기본적으로 다이나믹 프로그래밍 기법에 근거하여 이진 트라이를 루트로부터 너비 우선(breadth-first) 방식으로 운행하며, 경로 상에 존재하는 모든 유사 서브 시퀀스를 검색해 낸다. 제안된 기법의 우수성을 검증하기 위하여, 기존의 접미어 트리와의 비교 실험을 통한 성능 평가를 수행하였다. 실험 결과에 의하면, 제안된 인덱스 기법은 접미어 트리에 비하여 약 30%의 작은 저장 공간을 가지고도 수배에서 수십배의 검색 성능의 개선 효과를 나타낸다.

클라우드 컴퓨팅 기반의 병렬 CNV 검출 알고리즘

홍상균 ( Sang-kyoon Hong ),윤지희 ( Jee-hee Lee ),이은주 ( Un-joo Lee ) 한국정보처리학회 2011 한국정보처리학회 학술대회논문집 Vol.18 No.1

시퀀싱 기술의 발달로 최근에는 비교적 저렴한 비용으로 개인의 유전체 시퀀싱 데이터를 산출할 수 있게 되었다. 하지만 이를 기반으로 하는 기존의 분석 방법은 매우 고가의 컴퓨팅 환경을 요구하기 때문에 분석을 위한 비용이 매우 높은 문제가 있다. 본 논문에서 클라우드 컴퓨팅 환경의 병렬 CNV 검출알고리즘을 제안한다. 제안하는 방법은 모양 기반의 CNV 검출 알고리즘인 CNV_shape을 MapReduce기법으로 개발한 것으로 시퀀싱 데이터를 레퍼런스 서열에 매핑한 결과로부터 리드 커버리지 (read coverage)를 계산하여 커버리지가 감소하거나 증가하는 일정 길이 이상의 영역을 검출하는 방법이다. 클라우드 컴퓨팅 환경에 적용하고 노드의 밸런싱 유지를 위한 방법으로 파티셔닝 기법을 사용하였다. 또한 실 데이터를 이용한 실험을 통해 제안하는 방법의 효율적 데이터 처리를 보인다.

맵리듀스 기반의 암 특이적 단위 반복 변이 영역 추출

신재문(Jae-Moon Shin),홍상균(Sang-Kyoon Hong),공진화(Jin-Hwa Kong),이은주(Un-Joo Lee),윤지희(Jee-Hee Yoon) 한국정보과학회 2013 정보과학회논문지 : 데이타베이스 Vol.40 No.5

모든 암 세포는 체세포 변이를 동반한다. 암 유전체 변이 분석에 의하여 암을 발생시키는 유전자 및 진단/치료법을 찾아낼 수 있다. 본 연구에서는 차세대 시퀀싱 데이터를 이용하여 암 특이적 단위 반복 변이(copy number variation, CNV) 영역을 찾아내는 새로운 데이터 마이닝 알고리즘을 제안한다. 제안하는 방식에서는 암 환자의 암 유전체와 동일인의 정상 유전체에 존재하는 CNV 후보 영역을 각각 추출한 후, 이 들 결과를 상호 비교 분석하여 암 특이적 CNV 영역만을 선별해낸다. 본 연구에서 개발한 병렬 알고리즘은 암과 정상 유전체 데이터를 동시에 분석하여 암 특이적 CNV 영역을 추출/보고하며, 하둡(Hadoop) 환경의 맵리듀스(Map/Reduce) 함수에 의하여 이들 데이터를 분산, 병행 처리한다. 성능 평가를 위하여 악성 흑색종과 유방암 환자의 암/정상 유전체 데이터를 이용한 실험을 수행하였으며, 그 결과를 통해 제안된 방식이 대규모의 유전체 데이터로부터 암 특이적 CNV 영역의 타입 및 위치를 효율적으로 추출하고 있음을 보인다. The genomes of all cancer cells carry somatic mutations. Therefore, analyses of cancer genomes provide insight for understanding cancer-causing genes, diagnosis and therapy. In this work, we propose a data mining algorithm to detect cancer-specific copy number variation (CNV) regions by using next generation sequencing (NGS) data. The proposed method detects the candidate CNV regions from a cancer genome and the matched normal genome from the same individual, respectively, and identifies the cancer-specific CNVs by comparing the candidate CNV regions of a cancer genome with those of the matched normal genome. In this study, we also propose a novel parallel algorithm which simultaneously analyzes data from the cancer and patient-matched normal samples to identify cancer-specific CNV regions. This method is able to simultaneously perform tasks with large numbers of computing nodes using map and reduce functions in Hadoop project. The preliminary results conducted with the malignant melanoma and breast cancer data showed the prominent efficiency in identifying the types (gains or losses) and the exact locations of the cancer-specific CNVs.

DNA 시퀀스 데이타베이스를 위한 실용적인 유사 서브 시퀀스 검색 기법

원정임(Jung-Im Won),홍상균(Sang-Kyoon Hong),윤지희(Jee-Hee Yoon),박상현(Sang-Hyun Park),김상욱(Sang-Wook Kim) 한국정보과학회 2007 정보과학회논문지 : 데이타베이스 Vol.34 No.2

유사 서브 시퀀스 검색은 분자 생물학 분야에서 사용되는 매우 중요한 연산이다. 본 논문에서는 대규모 DNA 시퀀스 데이타베이스를 처리 대상으로 하여 효율성과 정확도를 보장하는 실용적인 유사서브 시퀀스 검색 기법을 제안한다. 제안된 기법은 이진 트라이를 인덱스 구조로 채택하여 DNA 시퀀스로부터 추출한 일정 길이의 윈도우 서브 시퀀스를 인덱싱 대상으로 한다. 유사 서브 시퀀스 검색 알고리즘은 기본적으로 다이나믹 프로그래밍 기법에 근거하여 이진 트라이를 루트로부터 너비 우선(breadth-first) 방식으로 운행하며, 경로 상에 존재하는 모든 유사 서브 시퀀스를 검색해 낸다. 그러나 질의 길이가 윈도우의 크기보다 큰 일반적인 경우에는 질의를 일정 길이의 서브 시퀀스로 분해하여 각 서브 시퀀스에 대하여 유사 서브 시퀀스 검색을 수행한 후, 후처리 과정에 의하여 정확도에 손상 없이 이 들 결과를 결합하는 분할 질의 처리 방식을 채택한다. 제안된 기법의 우수성을 검증하기 위하여, 실험을 통한 성능 평가를 수행한다. 실험 결과에 의하면, 제안된 인덱스 기법은 접미어 트리에 비하여 약 40%의 작은 저장 공간을 가지고도 약 4~17배의 검색 성능의 개선 효과를 나타낸다. 또한 분할 질의 처리 방식에 의한 유사 서브시퀀스 검색 알고리즘은 질의 길이가 긴 경우에도 효율적으로 동작하여 Suffix와 Smith-Waterman 알고리즘에 비하여 각각 수배에서 수십배의 검색 성능의 개선 효과를 나타낸다. In molecular biology, approximate subsequence search is one of the most important operations. In this paper, we propose an accurate and efficient method for approximate subsequence search in large DNA databases. The proposed method basically adopts a binary trie as its primary structure and stores all the window subsequences extracted from a DNA sequence. For approximate subsequence search, it traverses the binary trie in a breadth-first fashion and retrieves all the matched subsequences from the traversed path within the trie by a dynamic programming technique. However, the proposed method stores only window subsequences of the pre-determined length, and thus suffers from large post-processing time in case of long query sequences. To overcome this problem, we divide a query sequence into shorter pieces, perform searching for those subsequences, and then merge their results. To verify the superiority of the proposed method, we conducted performance evaluation via a series of experiments. The results reveal that the proposed method, which requires smaller storage space, achieves 4 to 17 times improvement in performance over the suffix tree based method. Even when the length of a query sequence is large, our method is more than an order of magnitude faster than the suffix tree based method and the Smith-Waterman algorithm.

웹 서비스 기반의 마이크로어레이 실험 데이터 공유 시스템 설계

이종근(Jong-Keun Lee),홍상균(Sang-Kyoon Hong),홍동완(Dong-Wan Hong),윤지희(Jee-Hee Yoon) 한국정보과학회 강원지부 2007 한국정보과학회 강원지부 학술대회 논문집 Vol.1 No.1

마이크로어레이 데이터베이스는 아직 그 규모가 서열 데이터베이스에 비해 작으며, 활용도 매우 제한적이다. 최근 주요 생물학 분야 저널에서는 실험에 사용된 마이크로어레이 데이터를 의무적으로 공용 데이터베이스에 공개하도록 규정하고 있으며, MAQC 프로젝트 등에 의해 실험 데이터의 질과 재생산성에 대한 신뢰성이 증가하고 있어 금후 마이크로어레이 데이터베이스의 규모 및 활용이 급속히 증가할 것으로 예상된다. 그러나 마이크로어레이 데이터는 데이터 교환 표준이 아직 실용화, 범용화 단계에 이르지 못하고 있어, 현재 부분적으로 공개되어 있는 국내, 외 마이크로어레이 실험 데이터도 이질의 포맷으로 구성되어 있어 실제적 접근 및 활용이 매우 어려운 상황이다. 본 연구에서는 마이크로어레이 데이터의 지능적 검색을 지원하는 웹 서비스 기반의 정보 공유 시스템 개발에 대하여 논한다. 실험 플랫폼, 데이터 포맷, 정규화 기법 등이 서로 다른 기존의 마이크로어레이 실험 데이터를 효율적으로 통합, 검색할 수 있는 시스템 구조를 제안하고 이를 웹 서비스 기반의 시스템으로 구현하는 실질적 방법론을 제시한다.