초록 ▼

본 연구의 목표는 문자열 포함 및 불포함 문제에 관한 연구를 수행하여 침입탐지와 같은 컴퓨터보안 분야와, DNA 서열분석과 같은 바이오인포매틱스 분야에 응용할 수 있는 기술을 개발하는 것이다. 본 연구에서 수행한 연구 주제 및 이의 결과들을 요약하면 다음과 같다.
(1) 최장공통비상위문자열 문제를 해결하는 효율적인 알고리즘 개발: 문자열 집합 N = {x₁, ... ,x_t}이 주어졌을 때, 어떤 x_i(1 ≤ i ≤ t)의 상위문자열도 아닌 문자열을 N에 대한 공통비상위

본 연구의 목표는 문자열 포함 및 불포함 문제에 관한 연구를 수행하여 침입탐지와 같은 컴퓨터보안 분야와, DNA 서열분석과 같은 바이오인포매틱스 분야에 응용할 수 있는 기술을 개발하는 것이다. 본 연구에서 수행한 연구 주제 및 이의 결과들을 요약하면 다음과 같다.
(1) 최장공통비상위문자열 문제를 해결하는 효율적인 알고리즘 개발: 문자열 집합 N = {x₁, ... ,x_t}이 주어졌을 때, 어떤 x_i(1 ≤ i ≤ t)의 상위문자열도 아닌 문자열을 N에 대한 공통비상위문자열이라 한다. 이 때, 공통비상위문자열 문제는 N이 주어졌을 때, 어떤 조건을 만족하는 공통비상위 문자열이 있는지 밝히고, 그 문자열을 찾아내는 것이다. Rubinov와 Timkovsky는 불포함문자열 집합의 접미사들에 대한 유향그래프를 이용해 이 문제를 모델링하고, 다항시간 안에 최장공통 비상위문자열을 찾는 방법을 제시하였다. 본 연구에서는 일반화접미사트리를 이용하여 Rubinov와 Timkovsky가 제시한 그래프를 선형시간, 즉 O(n)시간에 생성하는 알고리즘을 개발하였고, 이를 이용하여 선형시간에 최장공통비상위문자열을 찾는 알고리즘을 개발하였다. 본 연구에서 는 이 문제에 대한 기존 알고리즘을 개선한 효율적인 알고리즘 개발을 수행하였다. 또한 동적으로 최장공통비상위문자열을 찾는 문제에 대해 연구하고 이 결과들을 정보과학회 논문지 등에 게재하였으며 관련 연구 결과들을 국내특허로 출원하여 총 5건을 등록하였다.
(2) 비모순상위문자열 문제 해결을 위한 모델 연구: 두 문자열 집합 N = {x₁, ... ,x_t}과 P = {y₁, ... ,y_r}가 주어졌을 때, 각 x_i(1 ≤ i ≤ t)의 공통비상위문자열이며 동시에 각 y_i(1 ≤ j ≤ r)의 공통상위문자열을 N과 P에 대한 비모순상위문자열이라 한다. 본 연구에서는 Aho-Corasick 오토마타를 이용하여 비모순상위문자열 문제를 표현하는 방법에 대해 연구하였다. 접두사를 이용하여 직관적인 그래프 모델링 방법을 개발하고 이를 활용하여 비모순상위문자열 문제를 효율적으로 해결하는 구체적인 알고리즘을 개발하였다. 접두사를 이용하여 직관적인 그래프 모델링 방법을 개발하였다. 또한 이 그래프 모델링을 활용하여 비모순상위문자열 문제를 효율적으로 해결하는 구체적인 알고리즘을 개발하였다. 이 결과는 국제학회인 ISAAC에 발표하였고 현재 SCI급 논문지 게재를 준비중이다. 또한 관련 기술을 국내특허로 1건 출원하였다.
(3) 서열분석에 응용 가능한 문자열 알고리즘 연구: 바이오인포매틱스 분야의 서열 분석에 응용가능한 다중서열배치에 대한 연구를 수행하였다. 다중서열배치는 여러 서열들에서 공통적으로 나타나는 부분을 찾는 문제이다. 다양한 목적함수를 이용하여 연구되어 왔는데 본 연구에서는 두 목적함수를 동시에 고려한 다중서열배치 문제에 대한 연구 결과를 SCI 논문지에 게재하였으며, 바이러스와 같은 환형으로 이루어진 서열들에 대한 다중서열배치를 연구하여 이 결과를 정보과 학회 논문지에 게재하였다.

목차 Contents

• 일반연구자지원사업 최종(결과)보고서 ... 1
• 목차 ... 3
• I. 연구결과 요약문 ... 4
• II. 연구내용 및 결과 ... 5
• 1. 연구과제의 개요 ... 5
• 2. 국내·외 기술개발 현황 ... 5
• 3. 연구수행 내용 및 결과 ... 6
• 4. 목표달성도 및 관련분야에의 기여도 ... 7
• 5. 연구결과의 활용계획 ... 7
• 6. 연구과정에서 수집한 해외 과학기술 정보 ... 7
• III. 연구성과 ... 8