\subsection{ Sequence Searching method with 3D Random Plot Structure }
An overview of our algorithm framework is shown in Figure \ref{Space-trans}.
Generally, all types of biological sequence comparison exploit the sequence alignment based on a dynamic programming approach.
One popular alignment algorithm is the Needlemann--Wunsch algorithm, which is widely used in molecular biology.
There are many variations in sequence alignment, such as global alignment, local alignment, and semi-global alignment.
Though the alignment approach has many advantages, it has a critical drawback in that it involves high complexity in terms of execution-time complexity and space complexity.
The complexity of the basic alignment algorithm is $O(m \cdot n)$ if the lengths of two input sequences are $n$ and $m$.
If $\Theta(n)=\Theta(m)$, the complexity is quadratic: $O(n^2)$.
When the size of the input sequence is greater than 100 megabytes, this alignment is impractical, because it requires a main memory greater than the order of gigabytes.
To overcome these problems, researchers developed heuristic alignment techniques such as BLAST-like tools.
Another problem in the alignment algorithm is that it is not easy to define the score/penalty matrix to meet the many different constraints in biological sequence comparison. \par

\begin{figure}[htb]
\begin{center}
    \includegraphics[width=.5\textwidth]{./figures/seq-geo-space02.eps}
    \caption{Space transform from sequence to 3D geometric shape.}
    \label{Space-trans}
\end{center}
\end{figure}
The basic idea of our approach is that we compute the similarity of two sequences in `geometric random plot' space, rather than `string sequence' space.
As shown in Figure \ref{Space-trans}, we first transform the input sequences into random plot in 3D space.
Then, we compare or search for a target sequence in 3D geometric object.


%--------------camera begin--------------
%Since the size of the transformed random plot can be represented in a $500 \times 500 \times 500$ grid, the sequence, tens of megabytes in length, can be represented as a list with less than 100,000 linked pixels.
%이처럼 transformed random plot은 적정 크기의 그리드에 시각화 될 수 있으며, 메가바이트 크기의 서열도 실제 bp 개수보다 훨씬 작은 개수의 픽셀로 구성된 list로 표현될 수 있다.
This transformed random plot can be visualized on an appropriately sized grid, and a sequence of megabytes in size can be represented by a list of pixels much smaller than the actual number of bp.
%--------------camera end--------------


Thus, we can say that our geometric transformation is a type of approximation with visualization.
The advantage of our transformation is that the global structure can be shown by hiding the biological noise embedded in the sequence.
The main merit of our approach is that it is useful and efficient in comparing very long sequences.
Assume that we are asked to find the location of a sequence that is a few megabytes in length in a whole genome longer than 100 megabytes.


\subsection{ Vector Allocation for random Plot }
%\subsection{3D Random Plot Visualization}
%서열 데이터는 \{ `A',`G',`T',`C'\}로 구성된 string 정보이므로, 시각화를 위해서는 그래픽 정보로 변환을 필요로 한다.
Sequence data are string information composed of \{a,g,t,c\}; therefore, they must be converted into graphical information for visualization.
%기존 2차원 시각화 방법들은 x, y 각 축의 양, 음의 방향에 개별 염기를 할당하여 유전체 서열을 시각화 하였다.
Previous 2-D visualization methods have visualized genome sequences by assigning a separate base in the positive and negative directions of each axis (x and y).
%이와 같은 방법은 서로 반대되는 염기가 반복될 경우, 정보의 손실이 발생하고, 특정 패턴만 반복적으로 등장할 경우, 제한된 공간에 대용량 데이터를 시각화할 수 없다는 단점이 있다.
%이와 같은 방법은 서로 반대 방향의 벡터를 할당 받은 염기가 지속적으로 반복될 경우, 막대한 정보의 손실이 발생한다는 단점이 있다.
This method has a disadvantage in that a large amount of information is lost when a base having a vector in opposite directions is continuously repeated.
%또 동일 패턴이 지속적으로 반복될 경우, 제한된 공간에 대용량 데이터를 시각화 할 수 없게 된다.
Furthermore, if the same pattern is continuously repeated, it is impossible to visualize a large volume of data in a limited space.
%이를 개선하기 위해, 각 염기의 벡터 방향은 정하되, 염기를 2개씩 묶어 random plot을 진행하고,
%서로 반대 방향의 염기가 묶어진 경우 3차원상의 z축에 할당함으로써 손실되는 정보를 최소화한 방법에 관한 연구\cite{da2016comparison}가 진행되었다.\par
To overcome this disadvantage, \cite{da2016comparison} used a 3D vector.
A vector is assigned to each base, but a combination of two bases constitutes a random plot.
When the two bases are coupled together with the vector in the opposite direction, the representation is made three-dimensional with a z-axis to minimize the lost information.
\begin{table}[ht]
\caption{Vector allocation method for each 2-mer base in a genome sequence in three-dimensional geometric space}
\def\arraystretch{1.3}
\center
\begin{tabular}{cc|cc} \hline
2-mer    & Vector       & 2-mer    & Vector        \\  \hline
AA      & (  2,  0, 0) & AG(GA)  & (  1, 1,  0)  \\
AC(CA)  & (  1, -1, 0) & AT(TA)  & (  0, 0, -2)  \\
CC      & (  0, -2, 0) & CG(GC)  & (  0, 0, +2)  \\
CT(TC)  & ( -1, -1, 0) & GG      & (  0, 2,  0)  \\
GT(TG)  & ( -1,  1, 0) & TT      & ( -2, 0,  0)  \\
 \hline
\end{tabular}
%\caption{3차원 랜덤워크 시각화를 위한 벡터 설정.}-
\label{tab_2mervec}
\end{table}
%본 연구에서도 이와 같은 벡터 할당 방법을 사용하여 서열 데이터의 벡터를 계산하고, 서열 탐색 위치를 시각화 결과로 나타내고자 한다.
In this study, by using a 3D vector allocation model\cite{da2016comparison}, we calculate the vector character of the sequence data and obtain sequence search positions to visualize the results.


%%표\ref{tab_2mervec}은 각 2-mer에 대한 염기 할당 방법을 나타낸 것이다.
Table \ref{tab_2mervec} summarizes the vector allocation method for each 2-mer.
%AT, GC쌍이 나올 경우 앞선 장에서 언급한 바와 같이 Z축 상에서 표시하였으며,
In Table \ref{tab_2mervec}, the base pairs AT and GC are represented on the z axis.
%이를 제외한 다른 쌍의 염기는 WS-curve 상의 시각화 그래프에서 나타나는 해당 염기의 유닛 벡터들의 2개의 합으로 표현 한다.
The other base pairs are represented as the sum of two unit vectors for each base, as given by the WS-curve method.

%DNA 유전 데이터 정보에 대한 벡터 변환이 끝나면 이를 3차원 공간 상에서 시각화한다.
After the vector transition for DNA genome data information, those vectors are visualized in three-dimensional space.
%시각화 방법은 2차원 시각화 방법과 동일하게 읽어들인 순서에 따라 벡터 값들을 더하고 더해진 결과들을 선으로 이어 그 결과를 표시한다.
The method of visualization is the same as that of two-dimensional visualization, where the sum of vector values is computed according to the order of sequences and the results are connected with a line to provide the final visualization result.
%즉 랜덤워크플롯 $R$의 시작점을 $R(0) = (X_0,Y_0,Z_0)$ (단 $X_0=Y_0=Z_0=0)$,
For the random plot $R$, the starting point is $R(0) = (X_0,Y_0,Z_0)$ ($X_0=Y_0=Z_0=0)$.
%$i$번째 2-mer를 유닛벡터로 변환한 값을 $Unit^{3d}(i)$ 할 때
$Unit^{3d}(i)$ is the converted value of the $i$th 2-mer of the unit vector.
%랜덤 워크플롯 i 번째 점 $R(i)=(X_i,Y_i,Z_i)$는 다음과 같이 계산 가능하다.
The $i$th point $R(i)=(X_i,Y_i,Z_i)$ of the random plot is computed as follows:
\smallskip
\begin{equation}
\scriptsize
R(i) = R(i-1) + Unit^{3d}(i) = \sum_{k=1}^{i}Unit^{3d}(k)
\end{equation}
\smallskip
%그림 \ref{vector_exp}은 읽어들인 각 2-mer에 대한 random plot의 진행 방향을 나타낸 것이다.
Figure \ref{vector_exp} shows the direction of the random plot for each 2-mer read.
%처음 읽어들인 `AA'는 x축으로 (+2) 이므로, 그림(a)에서 원점$O$로부터 양의 x축으로 이동한 것을 확인할 수 있다.
Since the first 2-mer read `AA' is on the x-axis (+2), it can be confirmed from figure (a) that the positive x-axis moves from the origin $ O $.
%다음 중첩해서 읽어들인 2-mer는 `AT'이므로, z축으로 (-2)으로 이동한 것을 확인할 수 있다.
Since the next 2-mer read is `AT', a movement in the z-axis by (-2) can be confirmed. \par

%--------------camera begin--------------
This vector transformation rule are determined empirically in order to discriminate different sequences effectively.
As Figure \ref{prv_research}, similar sequences are likely to produce similar walk plots.
%--------------camera end--------------

%--------------camera begin--------------
%이와 같은 방법으로 변환된 random plot은 appropriately sized grid 3차원 공간에 시각화 된다.
In this way, the transformed random plot is visualized in an appropriate sized three-dimensional grid.
The default grid size $500 \times 500 \times 500$ is what we empirically figured out at which this trade off between speed and correctness of comparison is well balanced for the sequences used in the experiments.
%--------------camera end--------------


%비교적 짧은 길이의 유전 서열인 경우, 500x500x500 공간에 바로 나타낼 수 있지만,
In case of the short genome sequence, it can be represented in a $500 \times 500 \times 500$ grid easily.
%용량이 큰 서열인 경우, 시각화 크기에 맞춰 정규화 과정이 필요하다.
But the large size sequence needs space normalization to visualize the random plot in limited space.
%random plot의 벡터를 모두 계산했을 때, 원점 $O(0,0,0)$로 부터 X, Y, Z축으로 가장 거리가 먼 지점을 각 $max_x, max_y, max_z$ 라고 했을 때,
%정규화 된 i번째 픽셀은 다음과 같이 나타낼 수 있다.
When the vectors of the random plot are calculated, the points that are farthest from the origin $O(0,0,0)$ to the X, Y, and Z axes are $ max_x, max_y, max_z$, and the view size of visualization is $V$, the normalized $i$th point $R(i)=(X_i,Y_i,Z_i)$ can be expressed as:

\smallskip
\begin{equation}
Regular(R(i)) = ( X_i \cdot \frac{V}{max_x}, Y_i \cdot \frac{V}{max_y}, Z_i \cdot \frac{V}{max_z} )
\label{regular_exp}
\end{equation}
\smallskip


\begin{figure}
\center
\includegraphics[width=60mm]{./figures/walkplot_exp.eps}
\caption{
%읽어들인 각 2-mer에 대한 random plot의 진행방향을 나타낸 것이다.
%(a),(b),(c)는 각  X-Y, X-Z, Y-Z 평면 및 3차원 공간에서의 random plot 형태이다.
%$O(0,0,0)$에서 출발하여 2mer에 할당된 염기에 따라 random plot이 진행된다.
%X,Y축 상의 이동은 빨간색으로, Z축 상의 이동은 파란색으로 표시 되었다.
Movement of the random plot for each 2-mer read.
(a), (b), (c) and (d) show plots in the form of walks in the X-Y, X-Z, and Y-Z planes in three-dimensional space.
From $O(0, 0, 0)$, the random plot proceeds in accordance with the base assigned to 2-mer.
The red random plot represents movement on the X-Y plane, and the blue random plot represents movement on the Z axis.
} \label{vector_exp}
\end{figure}
This visualization model is so useful to compare the huge whole genome.
Figure \ref{prv_research} shows advantage of this works\cite{da2016comparison}.
We have constructed the 3D random plots from two whole genomes such as Human Chromosome 1 and Chimpanzee Chromosome 1.
In Figure \ref{prv_research}, red random plot represents the Human and green one represents the Chimpanzee.
Red random plots are up in the positive direction of the X and Y-axis than the green one.
This visualization method directly make us to confirm that two genomes are quite similar and the Human chromosome has more `G' and `A' base compared to Chimpanzee.

\begin{figure}
\center
\includegraphics[width=60mm]{./figures/prv_research2.png}
\caption{
Visualization result of Human and Chimpanzee chromosome 1.
Red plot is constructed from Human chromosome 1 and the green random plot is constructed from the whole genome of Chimpanzee (Pan troglodytes) chromosome 1.
} \label{prv_research}
\end{figure}
\subsection{ Vector Extraction from Random Plot }

For $G$, a genome sequence consisting of 4 DNA bases \{ a, g, t, c \}, $ranwalk(G)$ represents a three-dimensional geometric object constructed by our proposed algorithm.
Therefore, $ranwalk(G_i)$ consists of a list of linked pixels as follows:
\begin{definition}
\[ ranwalk(G) = < P_1 , P_2, \ldots , P_l > \]
\end{definition}
\medskip

The position of a $ranwalk$ pixel is denoted $P_i=(x_i , y_i, z_i )$ satisfying $|x_i - x_{i+1}| \leq 1$, $|y_i - y_{i+1}| \leq 1$ and $|z_i - z_{i+1}| \leq 1$, which means two pixels $P_i$ and $P_{i+1}$ are adjacent to each other, sharing a common face.
We say $P_i$ and $P_{i+1}$ are `adjacent' if they are within a distance of 1.
\smallskip

\begin{figure}[h]
\begin{center}
    \includegraphics[width=75mm]{./figures/geoplot_search2.eps}
    \caption{ A geometric random plot (blue dotted line) and corresponding vectors. }
    \label{Gpath}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
    \includegraphics[width=75mm]{./figures/geoplot04.eps}
    \caption{ Two comparison parameters \{$\theta_{AB},  L_{AB}$ \}. }
    \label{Rdist-how}
\end{center}
\end{figure}

Now, we explain how to compute the distance between two $ranplot$ pixels obtained from two genomes $G_a$ and $G_b$ to be compared.
Assume that we constructed two geometric objects, $R_a = ranplot(G_a)$ and $R_b = ranplot (G_b )$.
The proposed distance measure, \textit{random plot distance} ($Rdist$), is a vector with two components $\Delta Span$ and $\Delta Degree$.
The proposed $Rdist()$ measure has another parameter, depth $k$.
The distance between two random plot $R_a$ and $R_b$ at depth $k$ is defined recursively as follows.
In this definition, $R_a1$ is the first half of $R_a$, and $R_a2$ is the last half of $R_a$.
$R_{b1}$ and $R_{b2}$ are defined in a similar manner.
Thus, $R_a = R_{a1} \odot R_{a_2}$, where $\odot$ denotes the geometric concatenation operation.

\begin{definition}
\scriptsize
\[ Rdist( R_a , R_b, k ) \\ = Rdist( R_{a1} , R_{b1} , k+1 ) + \\
                                       Rdist ( R_{a2}, R_{b2} , k+1)  \]
\end{definition}

Now, we explain how to compute $Rdist( R_a , R_b, k=1 )$ at the basic depth = 1 level.
In Figure \ref{Gpath}, the thick blue dotted curve represents the random plot for a genome sequence.
Symbols $P_0(O)$ and $P_1$ denote the first and last pixel of a random plot, respectively.
$P_t$ denotes the first $t$-percentile pixel.
Thus, $P_{0.5}$ denotes the exact middle pixel in the list of pixels generated by our transformation algorithm.

For an interval in a random walk, we obtain a parameter, the length of the direction vector $(P_0, P_1)$.
If two random walks to be compared start with the origin $(0,0,0)$, then we can obtain the lengths of two direction vectors from $R_a$ and $R_b$ and compute the angle difference between two vectors $Pa_1$ and $Pb_1$.

%$R_a$의 시작과 끝점이 각 $P_{a0}, P_{a1}$이고, $R_b$의 시작과 끝점이 각 $P_{b0}, P_{b1}$이라고 가정하자.
Assume the start and end points of $R_a$ are $P_{a0}, P_{a1}$, and those of $R_b$ are $P_{b0}, P_{b1}$.
%$k=1$인 경우, 비교 대상은 $\overrightarrow{P_{a0}P_{a1}}$과 $\overrightarrow{P_{b0}P_{b1}}$이다.
If $k=1$ is, the comparison target is $\overrightarrow {P_{a0}P_{a1}}$ and $\overrightarrow{P_{b0} P_{b1}}$.
%$k=2$인 경우, 한 단계 더 내려가므로, 벡터를 둘로 나눠 앞, 뒤 벡터를 모두 비교한다.
If $k=2$, further down one step,divided into two vectors are compared both front and rear vector.
Therefore, the comparison target are $\overrightarrow{P_{a0}P_{a0.5}}$ and $\overrightarrow{P_{b0}P_{b0.5}}$,  $\overrightarrow{P_{a0.5}P_{a1.0}}$ and $\overrightarrow{P_{b0.5}P_{b1.0}}$.
%$k=3$인 경우, 마찬가지 방법을 적용하여  총 8번($2^k$) 번 비교를 수행한다. \par
If $k=3$, by applying the same method, it performs a comparison of eight times ($2^k$).

%-----------------------camera begin-----------------------
If the length of divided vector drops below the appropriate length D, the recursion is aborted.
In this paper, the threshold D value is set to 100 times the unit size, where unit size is the number of bp per pixel when visualized.
The D value was determined experimentally because at least the length of the vector was more than 100px, meaningful comparison was possible.
%-----------------------camera end-----------------------



\subsection{ Computing Similarity and Search on Random Plot }
%$Rdist$는 두 벡터간의 유사성 거리를 의미한다.
$Rdist$ refers to the similarity distance between the two vectors.
%그림\ref{Rdist-how}는 $Rdist$의 두 개 파라미터인 $\theta_{A,B}, L_{A,B}$을 보여준다.
Figure \ref{Rdist-how} shows that two parameters of $\theta_{A, B}, L_{A, B}$ for $Rdist$.
%$\theta_{A,B}$는 두 벡터의 사이각이고, $L_{A,B}$은 두 벡터의 길이의 차이와 그 중 더 긴 벡터 사이의 비율을 말한다.
$\theta_{A, B} $ refers to the angle between the two vectors, and $L_{A,B}$ refers to the ratio between the length of two vectors differ and from those of the longer vector.
%두 벡터가 방향이 같을 경우, $\theta_{A,B}=0$이 되고, 두 벡터가 길이가 같을 경우 $L_{A,B}=0$이 된다. $0<= \theta_{A,B} <=180, 0<= L_{A,B} <=1$.
If the two vectors have the same orientation, $ \theta_{A, B} = 0 $, two vectors, if the length is equal to $ L_ {A, B} = $ is 0($0 \leq \theta_{A,B} \leq 180, 0\leq L_{A,B} \leq1$).

To compare and visualize the random plot in a limited space, compression is necessary, as described earlier formula \ref{regular_exp}.
However, in the case of the reference sequence, to calculate the overall similarity of the two vectors, it maintains the two normalized values set.
One is a normalized value that is used to process the query sequence, and the other is a normalized value of the calculated original reference sequence.
When comparing the sequence to search when the use of normalized values of the query, and visualization uses the original normalized value.
This is because it can not be an accurate comparison due to the size difference between the reference and the query, the normalized values differ.

%레퍼런스 서열과 쿼리 서열 모두 쿼리 서열의 정규화 값에 따라 정규화 한 뒤, 일정 레벨 k까지 detph를 확장하여 전체 random plot을 분할하여 비교를 진행한다.
After the normalization of the reference sequence and query sequence the normalized according to the normalization value of the query sequence, extend the depth to a predetermined level $k$ to proceed comparison by dividing a random plot as unit size.
%두 random plot으로 부터 추출된 unit크기의 모든 벡터 조각을 Rdist()기반으로 비교한다.
Compare all the pieces of the vector unit size extracted from the two random plot by $Rdist()$.
When processing the results meet the pre-determined reference range, the higher the degree of similarity ($\theta_{A,B}\leq \theta_s$ and $L_{A,B} \leq L_s$).
%그리고 조건을 충족하는 유닛 벡터의 갯수와 전체 갯수 사이의 비율이 곧 유사도가 된다.
The ratio between the number of the unit vectors that meet the conditions and the total number of vector is similarity between two sequences.

\begin{algorithm}[t]
\caption{Comparison Algorithm} \label{alg:comp}
\begin{algorithmic}
\State \textbf{initialize} $beg \leftarrow 0$
\State \textbf{initialize} $end \leftarrow \mathbf{len}(R_a)$
\State \textbf{initialize} $O \leftarrow \{0,0,0\}$
\State \textbf{initialize} $D \leftarrow threshold \,lenth\, of\, vector$
\Procedure{Sim}{$beg$, $end$ : index of vector list, $R_a$, $R_b$ : random plot of $G_a, G_b$, threshold $\theta_s$, $L_s$}
\State $mid \leftarrow (end-beg)/2+beg $
\State $cnt \leftarrow 0 $
\If { $end - beg > D $ }
	\State $cnt += Sim(beg, mid, R_a, R_b )$
    \State $cnt += Sim(mid+1, end, R_a, R_b )$
\Else
    \State $ V_a \leftarrow R_a[end]-R_a[beg] $
    \State $ V_b \leftarrow R_b[end]-R_b[beg] $
    \State $ Len_a \leftarrow \mathbf{euclidean Dist}(O, V_a)$
    \State $ Len_b \leftarrow \mathbf{euclidean Dist}(O, V_b)$
    \State $ \theta_{a,b} \leftarrow \mathbf{acos}(\frac{\mathbf{dot Product}(V_a, V_b}{Len_a \times Len_b}) \times 180 $
    \State $ \L_{a,b} \leftarrow \frac{\mathbf{abs}(Len_a-Len_b)}{\mathbf{max}(Len_a, Len_b)}$
    \If { $\theta_{a,b} \le \theta_s$ and $\L_{a,b} \le L_s$ }
    	\State \textbf{return} $1$
    \Else
        \State \textbf{return} $0$
    \EndIf
\EndIf
\State \textbf{return} $cnt$
\EndProcedure
\end{algorithmic}
\end{algorithm}

% ---------- 새로 추가된 부분 ----------
\subsection{ Reference Sequence Slot }
%쿼리의 길이가 충분히 긴 경우, 제한된 공간에 시각화 하는 과정에서 서열 정보는 적절한 비율로 압축 된다.
If the length of the query is long enough, the sequence information is compressed at an appropriate rate during visualization in a limited space.
%따라서 레퍼런스 서열에서 탐색할 때 동일한 압축 비율을 적용하여 on-memory 상태에서 수행이 가능하다.
Therefore, it is possible to perform in the on-memory state by applying the same compression ratio when searching in the reference sequence.
%그러나 LTR 서열과 같이 길이가 짧은 서열은 불과 Killo byte 크기로서, 시각화 과정에서 압축이 되지 않고 원본 크기를 유지하게 된다.
However, sequences with short lengths, such as the LTR sequence, are only kilo-bytes in size and remain uncompressed in the visualization process.
%이 경우 벡터 정보가 커져서 on-memory 상태에서 쿼리 탐색이 불가능해진다.
In this case, vector information becomes large, and query search becomes impossible in on-memory state.
%이를 보완하기 위해 레퍼런스 서열과 쿼리 서열의 길이가 200배 이상 차이가 날 때, 레퍼런스 서열을 다수 개 slot으로 나누어 탐색을 수행한다.
In order to compensate for this, when the length of the reference sequence differs by more than 200 times, the reference sequence is divided into an appropriate number of slots to perform the search.
%슬롯은 일종의 윈도우와 같다.
A slot is like a window.
%특정 시점에 쿼리의 일정 배수만큼으로 탐색 범위를 축소시킴으로써, 대용량 서열에서 낮은 압축률로 탐색해야 하는 상황에서도 앞서 소개한 방법을 그대로 적용할 수 있도록 한다.
By reducing the search range by multiple of the query length at a certain point in time, the method described above can be applied even in a case where a search is required at a low compression ratio in a large size sequence.
\begin{equation}
\label{slot_numm}
%\frac {len($ranwalk(R)$) - $C$ \cdot len($ranwalk(Q)$)} { len($ranwalk(Q)$) \cdot ($C-1$)}
|Slot(Q, R)| = \frac{ |ranwalk(R)| - c_0 \cdot |ranwalk(Q)| }{ |ranwalk(Q)| \cdot (c_0-1) }
\end{equation}



%식 \ref{slot_num}은 쿼리와 레퍼런스 서열이 주어졌을 때 생성되는 슬롯의 갯수를 수식으로 나타낸 것이다.
Equation \ref{slot_numm} is the number of slots created when a query and reference sequence are given.
%$Q$와 $R$은 각각 Query, Reference Sequence이고 $len(ranwalk(X))$은 $X$를 random plot으로 나타냈을 때 전체 벡터 정보의 길이를 나타낸다.
$Q$ and $R$ are Query and Reference sequence respectively, and $len(ranwalk(X))$ represents the length of the whole vector information when $X$ sequence is expressed as a random plot.
%$C$는 일정 크기 벡터가 주어졌을 때, 그 벡터를 탐색하기에 용이한 공간의 크기로서 본 논문에서는 약 200에 가까운 값으로 설정했다. --> 수정
% C는 일종의 제어 상수로서, 일정 크기 쿼리 벡터가 주어졌을 때 그 벡터를 탐색해야 하는 공간의 크기이다.
$c_0$ is a control constant, which is the size of the space in which a vector should be searched when a certain size query vector is given.
In this paper, $c_0$ is set to around 200.0.
%슬롯이 분할되는 지점에 쿼리가 존재할 수 있으므로 각 슬롯의 경계는 쿼리 벡터의 길이만큼 중첩된다.
Since the query may exist at the point where the slot is divided, the boundaries of each slot are overlapped by the length of the query vector.
%그림 \ref{slotting}은 레퍼런스 서열의 벡터가 슬롯으로 분할된 것을 나타냈다.
Figure \ref{slotting} shows that the vector of the reference sequence is divided into slots.
\begin{figure}[h]
\begin{center}
    \includegraphics[width=.5\textwidth]{./figures/slotting.png}
    \caption{
    Slot division in reference sequence vector based on the vector length of the query sequence. }
   % 쿼리 서열의 시각화 벡터 길이를 기반으로 레퍼런스 서열의 시각화 벡터를 다수 개 slot으로 분할한 결과 }
    \label{slotting}
\end{center}
\end{figure}


%\begin{algorithm}[t]
%\caption{Restoring the Original Position on the Root} \label{alg:restore}
%\begin{algorithmic}
%\Procedure{Restore}{$v$: node, $i$: position}
%\While {$v$.Parent $\neq$ \texttt{null}}
%\State $p\leftarrow v$.Parent.
%\If {$v$ is a left child}
%\State $i\leftarrow p.\mathbf{select}_0(i)$
%\Else
%\State $i\leftarrow p.\mathbf{select}_1(i)$
%\EndIf
%\State $v\leftarrow p$.
%\EndWhile
%\State \textbf{return} $i$.
%\EndProcedure
%\end{algorithmic}
%\end{algorithm}
