http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
올리고뉴클레오타이드 제작을 위해 효율적이고 차별적인 시드를 고르는 방법에 대한 고찰
정원형(Won-Hyong Chung),박성배(Seong-Bae Park) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.1
생물정보분야에서 올리고뉴클레오타이드(oligonucleotide)를 제작하는 문제는 시간을 많이 소모하는 문제이다. 이 문제를 해결하기 위하여 해시를 이용한 가속계산이 주로 쓰이고 있고 BLAST란 프로그램이 대표적으로 생물정보분야에서 사용되고 있다. BLAST류의 프로그램들은 DNA서열의 특성에 따라 시드를 변형하여 해시를 개선하는 알고리즘을 적용하여 서열간의 유사도가 높은 부분을 찾는다. 그러나 이 프로그램들은 원래 올리고뉴클레오타이드 제작을 위해서가 아닌 지역정렬 문제를 해결하기 위한 방법들로써 발전하여 왔으므로 본 문제에 효율적인가에 대한 검증이 아직까지 이루어지지 않았다. 우리는 BLAST류의 프로그램에서 사용된 시드(seed)들이 올리고뉴클레오타이드 제작에 효과적인가를 판단할 수 있는 효율적이고 차별적인 잣대를 제시하고 이에 따라 다섯 종류의 대표적인 시드를 평가하였다. 평가에서 spaced seed라는 시드가 가장 좋은 결과를 보임을 정량적으로 계산할 수 있었다. Oligonucleotide design is known as a time-consuming work in Bioinformatics. In order to accelerate the oligonucleotide design process, one of the most widely used approaches is the prescreening unreliable regions using hashing(or seeding) method represented by BLAST. Since the seeding is originally proposed to increase the sensitivity for local alignment, the specificity should be considered as well as the sensitivity for the oligonucleotide design problem. However, a measure of evaluating the seeds regarding how adequate and efficient they are in the oligo design is not yet proposed. we propose a novel measure of evaluating the seeding algorithms based on the discriminability and the efficiency. By the proposed measure, five well-known seeding algorithms are examined. The spaced seed is recorded as the best efficient discriminative seed for oligo design.
박준영(Joon-Young Park),정원형(Won-Hyong Chung),김삼묘(Sam-Myo Kim) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.2Ⅰ
DNA 염기 서열을 분석하는데 효율적으로 쓸 수 있는 자료구조서 서픽스 트리(Suffix Tree)가 제시되었다. 그러나 매우 큰 유전자 서열에 대한 서픽스 트리는 대용량의 메모리 공간을 필요로 한다. 따라서 메모리 공간의 절약을 위해서 단어 서픽스 트리를 이용하는 방법이 제안되었다. 단어 서픽스 트리는 이러한 장점에도 불구하고 단어에 의미를 두고 만든 트리 구조이기 때문에 완전 매칭 문제를 해결하기 위한 정보가 부족해서 제한적 완전 매칭 알고리즘이 제시되었다. 제한적 완전 매칭 알고리즘에서는 찾으려는 패턴이 어떤 단어의 부-문자열에 위치하거나, 두 단어 이상에 걸쳐 나오면 찾지 못하는 문제가 발생한다. 본 논문에서는 단어 서픽스 트리의 완전 매칭 문제를 해결하기 위해 각 단어들의 서픽스에 대한 정보로 구성된 Generalized 서픽스 트리를 사용하여 확장된 단어 서픽스 트리를 제시하고, 완전 매치 알고리즘을 제안한다.