선택한 단어 수는 입니다.
최소 단어 이상 선택하여야 합니다.
최소 단어 이상 선택하여야 합니다.
선택한 단어 수는 30입니다.
최대 10 단어까지만 선택 가능합니다.
최대 10 단어까지만 선택 가능합니다.
문제 정의
- 본 논문에서는 DNA 스트링의 써픽스 배열을 구축하는 빠른 알고리즘을 제안하였다. KJP는 고정길이 문자 집합에 대해 써픽스 배열을 빠르게 구축하지만, DNA 스트링에 대한 써픽스 배열을 빠르게 구축하는 최적의 알고리즘은 아니었다.
- 본 논문에서는 DNA 스트링의 특성을 고려하여써픽스 배열을 더욱 빠르게 구축하는 방법을 제안한다. 기존 알고리즘들 중에서 고정길이 문자집합에 적합한 Kim, Jo 및 Park의 알고리즘(이하 논문에서 KJP라 칭함)에서의 인코딩 과정과 합병 과정을 DNA 스트링의 특성에 맞게 효율적으로 처리하여 전체 구축 시간을 단축시켰다.
제안 방법
- KJP를 이용하여 써픽스 배열을 구축하는 시간과 본 논문에서 제안한 방법을 사용해서 써픽스 배열을 구축하는 시간을 측정했다. 문자집합의 크기가 4이고 길이가 IM, 5M, 1OM, 30M, 50M 인 랜덤 스트링과 길이가 3.
- O(nlogn) 알고리즘인 Manber와 Myers[기의 알고리즘(MM), Larsson과 Sadakane[9]의 알고리즘CLS), 대표적인 선형시간 알고리즘인 Karkk五inen과 Sanders [1 이의 알고리즘 (KS), C»(nloglogn) 시간 알고리즘인 KJP와 본 논문에서 제안한 알고리즘(Proposed)의 써 픽스 배열 구축 속도를 비교했다. 실험에 사용된 텍스트는 문자 집합의 크기가 4이고 길이가 IM, 5M, 10M, 30M, 50M 인 랜덤 스트링과 길이가 3.
- 본 논문에서는 DNA 스트링의 특성을 고려하여써픽스 배열을 더욱 빠르게 구축하는 방법을 제안한다. 기존 알고리즘들 중에서 고정길이 문자집합에 적합한 Kim, Jo 및 Park의 알고리즘(이하 논문에서 KJP라 칭함)에서의 인코딩 과정과 합병 과정을 DNA 스트링의 특성에 맞게 효율적으로 처리하여 전체 구축 시간을 단축시켰다. 실험 결과 L35배에서 1.
- 합병 과정에서 이진 검색을 위해서는 추가로 자료구조를 구축해야 하며, 시간 복잡도에 숨은 상수가 크기 때문에 문자집합의 크기가 작은 경우 속도가 빠르지 않다. 다음 장에서는 이 알고리즘의 인코딩 및 합병 과정을 개선하여 DNA 스트링에 대한 써픽스 배열을 더욱 빠르게 구축하는 방법을 제안한다.
- 시간을 측정했다. 문자집합의 크기가 4이고 길이가 IM, 5M, 1OM, 30M, 50M 인 랜덤 스트링과 길이가 3.2M, 3.6M, 4.7M, 12.2M, 16.9M, 31.0M, 35.6M인 DNA 스트링을 이용해서 실험하여 그 결과를 표 3에 나타내었다. 실험을 통해 비교한 결과 랜덤 스트링과 DNA 스트링 모두 본 논문에서 제안한 방법을 사용했을 경우 인코딩 시간과 합병 시간이 단축되어 KJP보다 L3배에서 L6배 정도 더 빠르게 써픽스 배열을 구축하였다.
- 그 이 유는 3개의 문자를 인코딩하기 때문에 시간 복잡도 OS)에 숨은 상수가 크고, loglogne 실제로 매우 작은 값이므로 OS)에 숨은 상수와 비교할 수 있기 때문이다. 본 논문에서 제안한 알고리즘은 KJP보다 빠르게 써 픽스배열을 구축하였으며, 텍스트의 크기가 작은 일부 경우를 제외하면 가장 빠르게 써픽스 배열을 구축하였다.
- 6배에서 10배 정도 더 빠르게 인코딩을 수행하는 것을 볼 수 있다. 첫 번째 재귀 단계의 합병 시간을 실험을 통해 비교해 보았다. 인코딩과 마찬가지로 문자집합의 크기가 4이고 길이가 IM, 5M, 10M, 30M, 50M 인 랜덤 스트링과 길이가 3.
- 첫 번째, 두 번째, 세 번째 재귀 단계에서의 인코딩 시간을 실험을 통해서 비교해 보았다. 실험에 사용된 텍스트는 문자집합의 크기가 4이고 길이가 IM, 5M, 10M, 30M, 50M인 랜덤 스트링과 길이가 3.
- 첫 번째, 두 번째, 세 번째 재귀 단계의 인코딩 과정에서 기존의 기수 정렬 대신 카운트 정렬 방식을 이용하여 빠르게 수행하였으며, 첫 번째 재귀 단계에서 이진 검색을 하지 않고 단순히 배열을 읽는 방법을 사용하여 자료구조 구축 시간과 검색 시간을 줄여 합병을 빠르게 수행하였다. 본 논문에서 제안한 방법을 이용해서 써 픽스 배열을 구축한 결과 KJP보다 랜덤 스트링에서 65.
- 텍스트 의 Z 번째 써픽스를 S, = Rhn]라고 하자. 흘수 인덱스를 가지는 써픽스들의처음 2개의 문자를 인코딩해서 尸을 재귀적으로 생성한다. 尸을 이용해서 흘수 써픽스 배열 血를 직접 구축한다.
대상 데이터
- 6M 인 DNA 스트링이다. DNA 스트링은 NCBI사의 홈페이지에서 있는 것을 사용하였다. Proposed는 논문의 내용을 적용한 알고리즘을 의미한다.
- 실험을 통해서 비교해 보았다. 실험에 사용된 텍스트는 문자집합의 크기가 4이고 길이가 IM, 5M, 10M, 30M, 50M인 랜덤 스트링과 길이가 3.2M, 3.6M, 4.7M, 12.2M, 16.9M, 31.0M, 35.6M 인 DNA 스트링이다. DNA 스트링은 NCBI사의 홈페이지에서 있는 것을 사용하였다.
- 실험을 통해서 비교해 보았다. 실험에 사용된 텍스트는 문자집합의 크기가 4이고 길이가 IM, 5M, 10M, 30M, 50M인 랜덤 스트링과 길이가 3.2M, 3.6M, 4.7M, 12.2M, 16.9M, 31.0M, 35.6M 인 DNA 스트링이다. DNA 스트링은 NCBI사의 홈페이지에서 있는 것을 사용하였다.
- 첫 번째 재귀 단계의 합병 시간을 실험을 통해 비교해 보았다. 인코딩과 마찬가지로 문자집합의 크기가 4이고 길이가 IM, 5M, 10M, 30M, 50M 인 랜덤 스트링과 길이가 3.2M, 3.6M, 4.7M, 12.2M, 16.9M, 31.0M,35.6M인 DNA 스트링을 이용해서 실험하였다. 표 2는 랜덤 스트링을 이용해서 첫 번째 재귀 단계의 합병 시간을 실험을 통해서 비교한 결과와 DNA 스트링을 이용해서 첫 번째 재귀 단계의 합병 시간을 비교한 결과이다.
이론/모형
- 引社=9이면 써픽스 2의 순위는 g임을 의미한다. Lar- sson과 Sadakane 알고리즘 역시 더블링 기법을 사용하며 정렬 방법은 다음과 같다.
- 3와 耳가 정렬된 순서를 이용해서 와 를 정렬하면 모든 써픽스들은 次개의 문자들로 정렬되며, 이 방식을 더블링(doubling) 기법이라고 한다. Manber와 Myers[71의 알고리즘은 더블링 기법을 사용하며, 정렬 방법은 다음과 같다.
- 이 문제를 해결하기 위해서 Kim, Jo 및 Parke 문자 집합의 크기에 상관없이 OS) 공간을 사용하면서 비교적 빠른 0(login) 시간에 occQZc, #)를 계산할 수 있는 Sim, Kim, Park, 및 Park[13] 알고리즘의 자료구조를 사용하였다. 이 자료구조는 배열 U를 因의 길이를 가진블럭으로 나누고 매 블럭까지 누적된 c의 개수를 배열 *에 저장한다.
성능/효과
- 4.1에서 KJP의 인코딩 및 합병 시간과 본 논문에서 제안하는 인코딩 및 합병 시간을 실험을 통해 비교하여본 논문에서 제안하는 방법을 사용하는 경우 성능향상이 있음을 보인다. 42에서 본 논문의 방법을 사용하여써픽스 배열을 구축했을 경우 KJP에 비해 성능이 향상되었음을 보인다.
- Larsson과 Sadakane 알고리즘은 Manber와 Myers 알고리즘보다는 빠르지만 역시 시간 복잡도의 영향이 나타나 텍스트가 커질수록 구축 속도가 느려진다. Kark- kainen과 Sanders 알고리즘은 선형시간 알고리즘이지만 (9(nloglogn) 시간 알고리즘인 KJP보다 느렸다. 그 이 유는 3개의 문자를 인코딩하기 때문에 시간 복잡도 OS)에 숨은 상수가 크고, loglogne 실제로 매우 작은 값이므로 OS)에 숨은 상수와 비교할 수 있기 때문이다.
- 본 논문에서 제안한 알고리즘을 사용한 경우 최쟝 공통 접두사의 평균값이 크고, 텍스트의 크기가 커질수록 써픽스 배열을 빠르게 구축한다. 랜덤 스트링과 DNA 스트링을 이용한 실험을 통해 본 논문에서 제안한 방법은 KJP보다 빠르며, 다른 알고리즘들에 비해 전체적으로 가장 좋은 성능을 보임을 알 수 있다.
- 42에서 본 논문의 방법을 사용하여써픽스 배열을 구축했을 경우 KJP에 비해 성능이 향상되었음을 보인다. 마지막으로 4.3에서 본 논문에서 제안한 알고리즘과 다른 알고리즘들의 써픽스 배열 구축 속도를 비교한 결과 대부분의 경우 본 논문에서 제안한 알고리즘이 가장 빠름을 보인다.
- 문자집합의 크기가 4인 랜덤 스트링과 DNA 스트링을 이용해서 첫 번째, 두 번째, 세 번째 재귀 단계의 인코딩 시간을 비교한 결과 KJP에서 사용하는 기수 정렬 방법을 사용하는 방법보다 본 논문에서 제안한 카운트 정렬 방법을 이용하는 방법을 사용할 경우 약 5.6배에서 10배 정도 더 빠르게 인코딩을 수행하는 것을 볼 수 있다. 첫 번째 재귀 단계의 합병 시간을 실험을 통해 비교해 보았다.
- 본 논문에서 제안한 방법을 이용해서 써 픽스 배열을 구축한 결과 KJP보다 랜덤 스트링에서 65.0%-74.9%, DNA 스트링에서 68.5%-73.9% 정도로 구축 시간이 단축되었고, 다른 알고리즘들과 DNA 스트링에 대한 써픽스 배열의 구축 시간을 비교한 결과 대부분의 경우 가장 빠르게 써픽스 배열을 구축하였다.
- 본 논문에서 제안한 방법인 배열 KZ를 구축하지 않고 이진 검색 대신 배열을 읽는 방법을 사용한 첫 번째 재귀 단계의 합병 시간은 KJP의 합병 시간에 비해 1.2 배에서 1.6배 정도의 성능 향상이 있음을 알 수 있다. DNA 스트링의 경우에도 L4배에서 1.
- 르게 구축하고 있지만 Larsson과 Sadakane 알고리즘보다는 느리다. 본 논문에서 제안한 알고리즘을 사용한 경우 최쟝 공통 접두사의 평균값이 크고, 텍스트의 크기가 커질수록 써픽스 배열을 빠르게 구축한다. 랜덤 스트링과 DNA 스트링을 이용한 실험을 통해 본 논문에서 제안한 방법은 KJP보다 빠르며, 다른 알고리즘들에 비해 전체적으로 가장 좋은 성능을 보임을 알 수 있다.
- KJP는 고정길이 문자 집합에 대해 써픽스 배열을 빠르게 구축하지만, DNA 스트링에 대한 써픽스 배열을 빠르게 구축하는 최적의 알고리즘은 아니었다. 본 논문에서는 DNA 스트링의 문자 집합의 크기가 4로 고정되어 있는 사실을 이용해서 KJP의 인코딩 과정과 합병 과정의 성능을 크게 향상시킬 수 있었다.
- 기존 알고리즘들 중에서 고정길이 문자집합에 적합한 Kim, Jo 및 Park의 알고리즘(이하 논문에서 KJP라 칭함)에서의 인코딩 과정과 합병 과정을 DNA 스트링의 특성에 맞게 효율적으로 처리하여 전체 구축 시간을 단축시켰다. 실험 결과 L35배에서 1.46배 정도 더 빠르게 써 픽스 배열을 구축하였다.
- 6M인 DNA 스트링을 이용해서 실험하여 그 결과를 표 3에 나타내었다. 실험을 통해 비교한 결과 랜덤 스트링과 DNA 스트링 모두 본 논문에서 제안한 방법을 사용했을 경우 인코딩 시간과 합병 시간이 단축되어 KJP보다 L3배에서 L6배 정도 더 빠르게 써픽스 배열을 구축하였다.
- 첫 번째 재귀 단계에서는 이진 검색을 하는 것보다 배열을 읽으면서 값을 계산하는 것이 빨랐다. 그 이유는 이진 검색의 시간 복잡도 <9(logW)5] 숨은 상수가 직접 배열을 읽는 시간 복잡도。(因)의 숨은 상수보다 크고, 문자집합의 크기가 16으로 작아서 직접 배열을 읽는 시간이 이진 검색 시간에 비해 크게 느리지 않기 때문이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.