부분 컴파일 추론 방식

윤지희(Jeehee YOON),高木利久(Toshihisa TAKAGI),牛島和夫(Kszuo USHIJIMA) 한국정보과학회 1988 한국정보과학회 학술발표논문집 Vol.15 No.1

본 논문에서는 연역(deductive) 데이타 베이스 시스템의 추론 방식으로서 부분 컴파일 추론 방식(Partial Compilation Inference Method)을 제안하고 이 방식에 의한 추론 시스템의 개발에 대하여 논한다. 부분 컴파일 추론 방식은 기존의 인터프리터 추론 방식(Interpretive Inference Method)과 컴파일 추론 방식(Compilation Inference Method)의 융합형으로서, fact가 내부(Internal) 데이타 베이스와 외부(External) 데이타 베이스에 공존할 경우에도 negative literal을 바르게 평가할 수 있다는 특색을 갖는다. 단, 본 논문의 추론 시스템은 cycle-free, function-free의 Horn clause 형식을 갖는 질문(Query)과 연역 rule만을 처리 대상으로 한다.

한국어 텍스트상의 String Matching 알고리듬의 비교

윤지희(Jeehee YOON),이영진(Youngjin LEE) 한국정보과학회 1989 한국정보과학회 학술발표논문집 Vol.16 No.1

본 논문에서는 한국어 텍스트를 대상으로 하여 임의의 문자열을 검색해 내는 고속 string matching 알고리듬의 개발에 대하여 논한다. 한국어는 문자의 수가 많기 때문에 컴퓨터 상에서 1 문자당 복수 바이트로 표현되어야 하는등 고유의 특성을 갖는다. 여기에서는 이와 같은 한국어 텍스트의 특성에 근거하여 이미 영문 텍스트상에서는 그 유효성이 알려진 string matching 알고리듬을 한국어 텍스트에 적용시킬 때의 문제점을 제시한다. 또한, 그 해결책으로 텍스트를 정규화 시킴으로써 패턴 검색 작업이 단순화됨을 보이며, 정규화 한국어 텍스트상에서의 고속 string matching 알고리듬의 개발에 대하여 논한다.

시계열 데이타베이스에서 유사한 서브시퀀스의 모양 기반 검색

윤지희(JeeHee Yoon),김상욱(Sang-Wook Kim),김태훈(Tae-Hoon Kim),박상현(Sang-Hyun Park) 한국정보과학회 2002 정보과학회논문지 : 데이타베이스 Vol.29 No.5

본 논문에서는 시계열 데이타베이스에서의 모양 기반 검색 문제에 관하여 논의한다. 모양 기반검색은 실제 요소 값과 관계없이 질의 시퀀스와 유사한 모양을 갖는 (서브)시퀀스를 찾는 연산이다. 본 연구에서는 모양 기반 서브시퀀스 검색을 위한 새로운 기법을 제안한다. 먼저, 시프팅, 스케일링, 이동 평균, 타임 워핑 등 변환들의 다양한 조합을 지원하는 모양 기반 검색을 위하여 새로운 유사 모델을 제시한다. 또한, 이러한 유사 모델을 기반으로 하는 모양 기반 검색을 효과적으로 처리하기 위하여 효율적인 인덱싱 및 질의 처리 기법들을 제안한다. 제안된 기법의 유용성을 규명하기 위하여 실제 데이타인 S&P 500 주식데이타를 이용한 다양한 실험을 수행한다. 실험 결과에 의하면, 제안된 기법은 질의 시퀀스의 모양과 유사한 모양을 갖는 서브시퀀스들을 성공적으로 검색할 뿐만 아니라 순차 검색 기법과 비교하여 66배까지의 상당한 성능 개선 효과를 갖는 것으로 나타났다. This paper deals with the problem of shape-based retrieval in time-series databases. The shape-based retrieval is defined as the operation that searches for the (sub)sequences whose shapes are similar to that of a given query sequence regardless of their actual element values. In this paper, we propose an effective and efficient approach for shape-based retrieval of subsequences. We first introduce a new similarity model for shape-based retrieval that supports various combinations of transformations such as shifting, scaling, moving average, and time warping. For efficient processing of the shape-based retrieval based on the similarity model, we also propose the indexing and query processing methods. To verify the superiority of our approach, we perform extensive experiments with the real-world S&P 500 stock data. The results reveal that our approach successfully finds all the subsequences that have the shapes similar to that of the query sequence, and also achieves significant speedup up to around 66 times compared with the sequential scan method.

mRNA 리드 시퀀스 데이터를 이용한 선택 스플라이싱 유형 분석

공진화(JinHwa Kong),윤지희(JeeHee Yoon),이은주(UnJoo Lee),이종근(JongKeun Lee),원정임(JungIm Won) 한국정보과학회 2011 정보과학회논문지 : 데이타베이스 Vol.38 No.6

선택 스플라이싱은 단백질 생성 과정의 핵심 메카니즘으로서, DNA 조각들이 mRNA(messenger RNA)로 전사될 때 유전자의 엑손 영역들이 여러 가지 유형으로 다시 연결되는 과정을 말한다. 선택 스플 라이싱의 유형은 현재 7가지가 알려져 있으며, 이들 유형은 인간의 질병과 매우 밀접한 관련을 가지고 있다. 본 연구에서는 차세대 시퀀싱 기술로 생성된 mRNA 리드 시퀀스 데이터로부터 각 유전자 영역에 대한 선택 스플라이싱 유형을 분류/추출하는 새로운 알고리즘을 제안한다. 제안된 알고리즘에서는 mRNA 리드 시퀀스 데이터를 DNA 시퀀스와 mRNA 트랜스크립트 시퀀스에 동시 매핑하고, 각 엑손 영역에 정렬된 mRNA 리드 시퀀스 데이터의 커버리지 정보 및 엑손의 접합 정보를 이용하여 발현된 트랜스크립트의 종류와 양을 측정한다. 알고리즘의 유효성을 입증하기 위하여 시뮬레이션 데이터를 이용한 실험을 수행 하였으며, 실험 결과에 의하여 제안된 방식이 발현된 선택 스플라이싱 유형과 양을 매우 효율적으로 추출함을 보인다. Alternative splicing is a main source of generating a highly dynamic human proteome. It enables exons of genes to recombine in different ways when a segment of DNA is transcribed into messenger RNAs (mRNAs). There are seven patterns of alternative splicing which are known as typical ways in human genes. Alternative splicing has been found to be associated with many human diseases. This work proposes a novel method to identify alternative splicing patterns and analyze the distribution variations in a given gene expression process from mRNA read sequence data generated by next-generation sequencing (NGS) technology. The proposed method is based on parallel mapping of mRNA read sequence data to both genomic and transcriptomic reference sequences, and analyzes the mRNA read sequence data coverage and junctions spanning two exons. The preliminary results conducted with simulated data showed the prominent efficiency in identifying and quantifying events of alternative splicing.

차세대 시퀀싱 데이터에서 클라우드 스케일의 단위 반복 변이 추출 기법

홍상균(Sangkyoon Hong),윤지희(Jeehee Yoon) 한국정보과학회 2012 정보과학회논문지 : 데이타베이스 Vol.39 No.1

최근 차세대 시퀀싱 기술의 발달에 따라 인간 유전체 시퀀싱을 위한 비용이 현저히 낮아지고 있으며, 이에 따라 전 세계적으로 생성되는 대규모 차세대 시퀀싱 데이터가 매우 빠른 속도로 축적되고 있다. 그러나 이와 같은 대규모 유전체 데이터를 실시간에 효율적으로 처리, 분석할 수 있는 소프트웨어 개발에 관한 연구는 아직 매우 미흡한 상황이다. 본 연구에서는 클라우드 컴퓨팅 기반의 단위 반복 변이(Copy Number Variation, CNV) 추출 알고리즘, CloudCNV를 제안한다. 제안하는 알고리즘은 차세대 시퀀싱 데이터를 표준 서열(reference sequence)에 매핑(mapping)하여 얻어지는 커버리지(coverage) 데이터의 모양 변화를 기반으로 단위 반복 변이 영역을 추출한다. CloudCNV에서는 대표적인 클라우드 컴퓨팅 플랫폼인 하둡(Hadoop)과 맵리듀스(MapReduce) 기법을 이용하고, 클라우드 컴퓨팅 환경에서 데이터의 분산 처리 및 노드간의 로드 밸런싱을 위해 데이터의 확장 파티셔닝 기법을 사용한다. 성능 평가를 위하여 "1000 게놈 프로젝트"에서 제공하는 공용의 시퀀싱 데이터를 이용한 로컬 및 상용 클라우드 컴퓨팅 환경에서의 실험을 수행하였으며, 그 결과 제안하는 알고리즘이 클라우드 환경에서 대규모 데이터로부터 다양한 크기와 모양의 단위 반복 변이 영역을 효율적으로 추출하고 있음을 보인다. Recently, the cost of whole-genome sequencing has decreased dramatically due to the development of next generation sequencing (NGS) technology, and a huge amount of sequencing data has been generated and released by research laboratories worldwide. However, it is difficult to develop mature genome analysis software and high-performance computing resources which are available to assay genome data in real time. This paper proposes a cloud-computing algorithm that detects CNVs (Copy Number Variations) from next generation sequencing data. The proposed method, which we call CloudCNV was developed using a shape-based CNV detection algorithm, which is based on variations in the shape of read coverage data obtained by aligning NGS data onto a reference sequence. CloudCNV uses the open-source Hadoop implementation of MapReduce, and uses an extended partitioning method to maintain load balancing of each node in the cloud computing environment. To verify the superiority of our approach, we performed extensive experiments using publicly available sequencing data. The result of experiments revealed that our CloudCNV method efficiently finds the CNV regions that have various shapes and arbitrary length from enormous NGS data.

시계열 데이터베이스에서의 모양 기반 서브시퀀스 매칭

김태훈(Tae-Hoon Kim),윤지희(Jeehee Yoon),김상욱(Sang-Wook Kim),박상현(Sanghyun Park) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.2Ⅰ

모양 기반 검색은 주어진 질의 시퀀스의 요소 값에 상관없이, 모양이 유사한 시퀀스 혹은 부분시퀀스를 찾는 연산이다. 본 논문에서는 시프트, 스케일링, 타임 워핑 등 동일 모양 변환의 다양한 조합을 지원할 수 있는 새로운 모양 기반유사 검색 모델을 제안하고, 효과적인 유사 부분 시퀀스 검색을 위한 인덱싱과 질의 처리 방법을 제안한다. 또한 실세계의 증권데이터를 이용한 다양한 실험 결과에 의하여, 본 방식이 질의 시퀀스와 유사한 모양의 모든 서브시퀀스를 성공적으로 찾는 것은 물론 순차검색 방법과 비교하여 매우 빠른 검색 효율을 가짐을 보인다.

비정규 관계를 위한 연역 데이타 베이스 시스템의 설계 및 구현

이영진(YoungJin Lee),윤지희(Jeehee Yoon) 한국정보과학회 1990 한국정보과학회 학술발표논문집 Vol.17 No.2

본 논문에서는 속성의 정의역으로 집합치를 허용한 비정규 관계 데이타 베이스를 대상으로 하는 연역 데이타 베이스 시스템의 설계 및 구현에 대하여 논한다. 본 시스템에서는 내부 데이타 베이스와 외부 데이타 베이스에 집합치를 허용함으로써 자연스럽고 압축된 데이타 구조의 표현방식을 도입하였다. 또한, 비정규 관계 unification 알고리즘과 부분 컴파일 알고리즘을 제안하여 시스템 전체의 효율 향상을 꾀하였다. 한편, 기존의 부분 컴파일 방식을 확장하여 차집합 연산에 근거한 negation 처리 방식을 도입하여 fact가 내부 데이타 베이스와 외부 데이타 베이스에 공존하는 경우에도 negative literal을 바르게 평가할 수 있다.

한국어 택스트를 위한 pattern matching 알고리즘의 개발

이영진(Youngjin Lee),윤지희(Jeehee Yoon) 한국정보과학회 1990 한국정보과학회 학술발표논문집 Vol.17 No.1

텍스트 처리용 프로그램을 위한 가장 기본적인 알고리즘의 하나로 pattern matching 알고리즘을 들 수 있다. 본 논문에서는 한국어 텍스트의 고유 특성을 고려한 한국어 텍스트용 pattern matching 알고리즘의 개발에 관하여 논한다. 영문 텍스트 상에서 유효성이 확인된 5종의 기존 알고리즘을 한국어 텍스트에 적용시킬 경우 그 적용 가능성과 문제점에 대하여 논한 후, 이들 문제점의 해결방안 및 알고리즘의 개선 방안을 제시, 이들 방안에 근거한 한국어 텍스트용의 pattern matching 알고리즘을 보인다.

한국어 문서 작성 지원 틀의 설계 및 구현

이홍수(Hongsu Lee),홍순재(Soonjae Hong),윤지희(Jeehee Yoon) 한국정보과학회 언어공학연구회 1992 한국정보과학회 언어공학연구회 학술발표 논문집 Vol.1992 No.10

분산병렬 클러스터 컴퓨팅을 이용한 GVCF(Genome Variant Call Format) 파일의 정렬 및 병합 방법

이진우(JinWoo Lee),원정임(Jung-Im Won),윤지희(JeeHee Yoon) 한국정보과학회 2021 정보과학회논문지 Vol.48 No.3

차세대 시퀀싱(next-generation sequencing, NGS) 기법의 발달로 인하여 방대한 유전체 데이터의 분산, 병렬처리가 필수적인 방법론으로 대두되고 있다. NGS 유전체 데이터 처리는 데이터 규모로 인하여 일반적으로 매우 긴 실행 시간을 필요로 한다. 본 논문에서는 GVCF 파일 정렬/병합 실행 시간을 단축하기 위하여 분산병렬 클러스터 컴퓨팅을 이용한 새로운 GVCF 파일 정렬/병합 모듈을 제안한다. 제안하는 모듈에서는 분산병렬 클러스터인 Spark를 사용하며, 클러스터 내의 자원을 효율적으로 사용하기 위해 GVCF 파일의 특성을 고려한 두 단계의 과정으로 정렬/병합을 진행한다. 성능 평가를 위하여 GATK의 Combine-GVCFs 모듈과 제안하는 모듈의 GVCF 파일의 개수에 따른 정렬/병합 실행시간을 측정하여 비교 및 평가를 진행하였다. 실험 결과에 의하여 제안하는 방식이 실행시간을 매우 효율적으로 단축시키고 있음을 확인하였으며, 제안하는 방식의 유용성을 입증하였다. With the development of next-generation sequencing (NGS) techniques, a large volume of genomic data is being produced and accumulated, and parallel and distributed computing has become an essential tool. Generally, NGS data processing entails two main steps: obtaining read alignment results in BAM format and extracting variant information in genome variant call format (GVCF) or variant call format (VCF). However, each step requires a long execution time due to the size of the data. In this study, we propose a new GVCF file sorting/merging module using distributed parallel clusters to shorten the execution time. In the proposed algorithm, Spark is used as a distributed parallel cluster. The sorting/merge process is performed in two steps according to the structural characteristics of the GVCF file in order to use the resources in the cluster efficiently. The performance was evaluated by comparing our method with the GATK"s CombineGVCFs module based on sorting and merging execution time of multiple GVCF files. The outcomes suggest the effectiveness of the proposed method in reducing execution time. The method can be used as a scalable and powerful distributed computing tool to solve the GVCF file sorting/merge problem.