%%%   연구 동기   %%%
% BLAST 탐색의 문제점
    % 시간
    % 인디렉트 프로세싱(메일)
    % 참고자료 : 워싱턴대학 pt 자료
    % 출처 : https://homes.cs.washington.edu/~billhowe/cs410/lectures/Kepler1.pdf
    % 원문
    % Can only search for a single query (e.g. find all genes similar to TTGGACAGGATCGA)
    % • What about more complex queries?
    % • “Find all genes in the human genome that are expressed in the liver and
    % have a TTGGACAGGATCGA (allowing 1 or 2 mismatches) followed by GCCGCG within 40 symbols in a 4000 symbol stretch upstream from the gene.
    % 요지
    % 단일 쿼리만 찾을 수 있다. 예를 들어, 특정 쿼리와 유사한 모든 유전자 찾아내기
    % 좀 더 복잡한 쿼리에서는 어떻게 되는가?
    % '~~'를 포함하면서 (1~2개 미스매치를 허용하는) 인간의 모든 유전자를  찾아라.
    % BLAST는 비효율적, 불편 - MB 단위 seqeucne에서

%%차세대 유전자 분석 기술(Next Generation Sequencing)의 발달은 생물학 연구자로 하여금 전장유전체와 같은 대량의 생물체 정보를 쉽게 구할 수 있도록 하였다.
%The development of next-generation genetic analysis technology (next-generation sequencing) has enabled researchers to easily obtain a large amount of information on biological organisms, such as whole genome sequences.
%%이에 따라, 방대해진 유전 정보를 어떻게 효율적으로 처리하고, 표현할 것인가에 대한 연구가 활발히 진행 중이다.
%Accordingly, studies on how to efficiently process and represent vast amounts of genetic information are actively conducted.
%%대부분의 유전 정보 분석은 상동성 및 상이성 등 생물체 서열의 비교를 통해 유사한 생물체, 유사한 기능을 밝혀내 방법으로 진행되므로, 특정 서열의 탐색 및 비교는 유전체 연구에서 반드시 필요한 중요한 기술이다.
%Because most genetic information analyses are based on similar organisms and similar functions through the comparison of organism sequences such as homology and heterogeneity,
%the search and comparison of specific sequences are essential for genome research.
%%서열의 탐색 및 비교시에는 가장 보편적으로 서열 정렬(sequence alignment)기법이 활용되는데,공간복잡도가 높아 대용량의 유전체 정보를 개인컴퓨터에서 처리하기에는 많은 어려움이 따른다.
%Sequence alignment techniques are most commonly used for searching and comparing sequences. Owing to the high spatial complexity, it is difficult to process a large amount of genome information on a personal computer.
%%이를 위해 서열 정렬에 비해 정확도는 낮지만, 보다 빠른 시간내 결과를 얻기 위해 heuristic 기법의 연구들이 진행되고 있다.\\
%Although heuristic techniques have lower accuracy than sequence alignment techniques, they are being studied to obtain faster results. \\



% (새로추가)
% 유전체 데이터 연구는 서열의 비교를 통해 이루어지며, 대부분 alignment algorithm을 기반으로한 모델을 사용한다.
Genomic data studies are done through sequence comparisons, mostly using a model based on an alignment algorithm.
% 예를 들어 데이터베이스에서 서열을 탐색하는 가장 보편적인 방법은 BLAST로서,
For example, Basic Local Alignment Search Tool (BLAST)\cite{altschul1990basic} is the most common method to search for sequences in a database.
%쿼리 서열을 3글자 단위로 쪼개어 매치 되는 구간을 찾은 다음, 점차 영역을 넓혀서 alignment 대상이 되는 후보를 추려낸다.
It divides the query sequence into three characters, finds the matching region, and gradually widens the region to select candidates for alignment.
%짧은 쿼리를 전체 DB에서 탐색하고자 할 때 매우 유용하게 사용되고 있지만, alignment를 기반으로 하기 때문에 MB 단위의 염색체과 같이 용량이 큰 서열을 처리하기 위해서는 계산량이 막대하게 증가하여 즉각적인 처리 결과를 얻기 어렵다.
Although it is very useful when searching for a short query in the whole database, since it is based on alignment, it is difficult to obtain an immediate processing result in the case of a large sequence such as a megabyte-scale chromosome owing to a large increase in computational cost.
%실제 BLAST 서비스를 활용할 때, 쿼리 크기가 MB 단위인 경우, 데이터베이스 검색 범위를 축소하도록 권고되고 있으며, 탐색 시간이 많이 소요되어 결과를 즉각적으로 제공하기 보다는, 메일로 제공하는 경우가 많다.
When utilizing the actual BLAST service, it is recommended to reduce the database search scope when the query size is of the order of megabytes, and it is often time consuming to search and provide results by mail, rather than providing it immediately. \par

%(새로추가)
% 이 밖에도 유전자 재조합 및 유전자 셔플링은 연속성 보존을 전제로 하는 서열 정렬과는 다르기 때문에, 이를 극복하기 위해 단어 빈도 통계, 빈도 벡터에 의해 정의된 공간상의 거리 계산 방법 등 정렬없는 방법을 유도하기 위한 연구도 활발히 진행되고 있다.
% camera--> shuffling 단어 제외
In addition, since gene recombination is different from sequence alignment based on conservation of contiguity between homologous segments, in order to overcome this problem, alignment-free comparison method such like word-frequency statistics, a method of calculating distance in space defined by frequency vectors, is also actively underway\cite{vinga2003alignment}.
%이와 같은 연구는 정렬 기반 모델의 쿼리를 처리하기 위한 사전 필터로서도 널리 사용되고 있다.
Such research is also widely used as a prefilter for processing queries of alignment-based models.

%본 연구에서는 개인 컴퓨터에서도 빠른 시간 내에 서열 비교 및 탐색이 가능한 geometric 기반의 휴리스틱 기법을 제안하고자 한다.
In this paper, we propose a geometric-based heuristic technique that enables the rapid comparison and search of sequences in personal computers.
%이와 관련해 AMSS는 Time series data를 vector의 sequence로 가정하고 shape 기반의 유사도 비교를 제안한 모델이다.
%time series data의 개별 포인트에 초점을 두기 보다는 vector에 초점을 두어 코사인 유사도를 이용해 data간 유사도를 비교하였다.
%이와 같은 방법은 시계열 데이터의 시간이나 각도의 이동 또는 스케일에 견고하다는 장점을 가진다.
In this regard, AMSS\cite{nakamura2013shape} is a model that provides shape-based similarity comparison, assuming that the time series data is a vector sequence.
Instead of focusing on individual points of time series data, the model focuses on vectors and compares similarities between data using cosine similarity.
This method is advantageous in that it is effective for amplitude and time shifting.
%본 연구에서도 유전체 서열 데이터가 순서가 있는 문자열 데이터라는 점에 착안하여, 유전체 서열을 geometric object로 변환하여 비교 및 탐색을 수행함으로써 시간 및 공간 복잡도를 개선하고자 한다.
In this study, we also aimed to reduce the time and space complexity by converting the genetic sequence into a geometric object such as a random plot and performing comparison and search, taking into account that the genetic sequence data is ordered sequence data.
%alignment 알고리즘과 같이 개별 염기 하나하나를 고려하는 것이 아니라, 일정 단위의 서열을 기반으로 생성된 벡터를 한 번씩만 비교하는 방법을 사용함으로써, 비교 연산 횟수를 대폭 줄일 수 있고, 서열 탐색 결과를 시각화하여 정보를 보다 직관적으로 제시하고자 한다.
Instead of considering a single separate base, as in the alignment algorithm, the method compares the vector generated based on the sequence of the predetermined unit only once, and it is possible to significantly reduce the time required for comparison operation by visualizing a sequence search result and presenting the information more intuitively.
%또한 대용량 데이터에도 적용할 수 있는 고속의 휴리스틱한 탐색 기법으로서, 추후 alignment 등 정밀 분석이 필요한 부분을 특정할 수 있다.
In addition, the high-speed heuristic search technique can be applied to large amounts of data, and it is possible to specify the necessary precise alignment analysis.

Compared to [14], we present an improved similarity computation algorithm that considers input sequences with different lengths. 
We show  the effectiveness of the proposed method with experiments on searching for short query sequences on a long sequence.

%
%본 연구에서는 전장유전체를 3D Random plot형태로 가시화하는 Web-GL 기반의 웹 시스템을 개발하고,
%시각화 정보를 기반으로 특정 유전체 질의 서열을 빠른 시간에 탐색하는 모델을 제안하고자 한다.
%먼저 참조서열의 각 2-mer 염기에 대해 벡터를 설정하고, 유전체 서열을 순차적으로 읽어들여 할당된 벡터를 기준으로 좌표를 계산한다.
%각 염기에 대한 모든 좌표 정보는 3차원상의 Random Plot 시각화 정보가 된다.
%그리고 질의 서열에 대해서도 동일한 과정을 거쳐 좌표를 계산한 다음, 마지막 좌표를 추출하여 원점과 연결하면 질의 서열의 대표 벡터가 된다.
%서열 탐색은 이 질의 서열의 대표 벡터를 참조 서열 벡터에서 찾는 방법으로 진행된다.
%이는 문자열 매칭 문제를 3차원 공간상의 벡터 비교의 문제로 치환하여 문제를 보다 단순화하고,
%두 서열의 시각화 정보를 한 번씩만 읽는 방법으로 서열을 탐색함으로써, 서열정렬에 비해 개선된 속도로 특정 서열을 탐색할 수 있다. \newline
%본 논문의 구성은 다음과 같다. 다음 장에서는 유전체 정보 분석을 위한 alignment 방법 및 유전체 정보 시각화에 대해 관련 연구를 설명하고,
%시각화 결과를 토대로 유전체 정보를 분석한 연구를 설명한다. 3장에서는 3D Random plot 시각화를 위한 벡터 계산에 대해 설명하고,
%시각화 결과 정보를 토대로 특정 서열을 탐색하는 새로운 방안을 소개한다. 4장에서는 실험 결과 및 가시화 결과를 보이고 5장에서 본 연구의 최종 결론을 밝힌다.
