접미사 트리를 이용한 압축 기법에서 가장 긴 매치 찾기

나중채(Joong Chae Na),박근수(Kunsoo Park) 한국정보과학회 1999 한국정보과학회 학술발표논문집 Vol.26 No.2Ⅰ

Ziv-Lernpel 코딩 방식은 문자열이 반복해서 나올 때 뒤에 나오는 문자열을 앞에 나온 문자열에 대한 포인터로 대치시킴으로써 압축을 한다. 따라서 이 방식을 위해서는 앞서 나온 문자열을 유지하는 사전과 문자열 매칭이 필수적이다. 그래서 이 두 가지에 효율적인 자료구조인 접미사 트리를 Ziv-Lernpel 코딩 방식에 적용시키려는 연구가 많이 진행되어 왔다. Rodeh, Pratt와 Even은 접미사 트리를 LZ78 코딩에 이용하는 방법을 제안하였고, 그 이후에 Fiala, Green와 Larsson은 각각 McCreight와 Ukkonen의 접미사 트리 생성 알고리즘을 LZ77 코딩에 이용하였다. 접미사 트리를 이용한 Ziv-Lernpel 코딩에는 만들어진 사전, 즉 접미사 트리와 앞으로 압축될 문자열과의 가장 긴 매치를 찾는 과정이 있다. 이는 단순히 접미사 트리의 루트부터 차례로 검색해 나가도 되지만 이렇게 했을 때 걸리는 시간은 노드에서 자식을 찾는데 걸리는 분기 결정 시간에 의해 좌우된다. 즉 분기에 선형 시간 이상이 걸리면 가장 긴 매치를 찾는데도 역시 선형 시간 이상이 걸린다. 게다가 이 방법은 자기 중복 (self-overlapping)의 이점을 살릴 수가 없다. Rodeh, Pratt와 Even은 McCreight의 생성 알고리즘을 이용할 때 가장 긴 매치를 바로 찾을 수 있다는 것을 발견했다. 그러나 Ukkonen의 알고리즘에 대해서는 아직 이러한 방법이 알려지지 않았다. 본 논문에서는 Ukkonen의 알고리즘에 몇 가지 작업을 추가하여 전체적으로 선형시간 안에 가장 긴 매치를 찾는 방법을 소개한다.

거리반경기반 대표문자열 문제의 NP-완전

나중채(Joong Chae Na),심정섭(Jeong Seop Sim) 한국정보과학회 2009 정보과학회논문지 : 시스템 및 이론 Vol.36 No.3

여러 문자열들을 비교하여 유사성 또는 거리(오차)를 계산하는 문제는 패턴매칭, 웹검색, 바이오인포매틱스, 컴퓨터 보안 등 다양한 응용 분야와의 연관성으로 인해 활발히 연구되어 왔다. 주어진 문자열 집합 내의 여러 문자열들의 거리를 비교하기 위해 주어진 집합 내의 모든 문자열들을 대표하는 한 문자열(대표문자열)을 찾는 방법이 있다. 대표문자열 방법은 주어진 문자열 집합과 가장 유사한 한 문자열을 찾는 방법으로 주로 이용되는 목적함수는 거리반경과 거리합이 있다. 거리반경은 집합 내의 문자열들과 특정 문자열과의 거리들의 최대값으로 정의되며, 모든 문자열들 중에서 최소의 거리반경을 만드는 문자열을 주어진 문자열 집합에 대한 거리반경기반 대표문자열이라 한다. 거리합은 집합 내의 문자열들과 특정 문자열과의 거리들의 합으로 정의되며, 모든 문자열들 중에서 최소의 거리합을 만드는 문자열을 주어진 문자열 집합에 대한 거리합기반 대표문자열이라 한다. 본 논문에서는 메트릭 거리함수에 대해 거리반경기반 대표 문자열 문제가 NP-완전임을 증명한다. The problems to compute the distances or similarities of multiple strings have been vigorously studied in such diverse fields as pattern matching, web searching, bioinformatics, computer security, etc. One well-known method to compare multiple strings in the given set is finding a consensus string which is a representative of the given set. There are two objective functions that are frequently used to find a consensus string, one is the radius and the other is the consensus error. The radius of a string x with respect to a set S of strings is the smallest number r such that the distance between the string x and each string in S is at most r. A consensus string based on radius is a string that minimizes the radius with respect to a given set. The consensus error of a string with respect to a given set S is the sum of the distances between x and all the strings in S. A consensus string of S based on consensus error is a string that minimizes the consensus error with respect to S. In this paper, we show that the problem of finding a consensus string based on radius is NP-complete when the distance function is a metric.

절단 접미사 트리를 생성하는 새로운 알고리즘

나중채 ( Joong Chae Na ) 한국정보처리학회 2009 한국정보처리학회 학술대회논문집 Vol.16 No.1

절단 접미사 트리(truncated suffix tree)는 접미사 트리의 절단 버전으로, 주어진 문자열의 부분 문자열중 일정 길이 이하인 것들만을 표현하는 자료구조이다. 절단 접미사 트리는 일정 길이 이하의 문자열들만을 고려하는 응용에 유용한데, 특히 LZ77 압축과 같이 온라인 생성 알고리즘이 필요한 응용들도 있다. 본 논문에서는 절단 접미사 트리를 온라인으로 생성하는 새로운 알고리즘을 제시한다.

일반화된 접미사 트리의 온라인 동반 생성 알고리즘

나중채 ( Joong Chae Na ) 한국정보처리학회 2009 한국정보처리학회 학술대회논문집 Vol.16 No.1

접미사 트리는 주어진 하나의 문자열의 모든 접미사를 표현하는 트리로, 문자열 처리, 압축 등 다양한 분야에서 활용된다. 접미사 트리는 문자열 집합에 대한 자료구조로 확장될 수 있는데, 이를 일반화된 접미사 트리라 부른다. 본 논문에서는 일반화된 접미사 트리를 동반적이면서 온라인으로 생성하는 문제를 다룬다. 기존의 생성 알고리즘은 정방향의 문자열이 아닌 역방향의 문자열들에 대한 일반화된 접미사 트리를 생성하여, 부자연스럽다. 본 논문에서는 정방향 문자열들의 일반화된 접미사 트리를 동반적이면서 온라인으로 생성하는 알고리즘을 제시한다.

품질 정보를 이용한 서열 배치 알고리즘 (pp.578-587)

나중채(Joong Chae Na),노강호(Kangho Roh),박근수(Kunsoo Park) 한국정보과학회 2005 정보과학회논문지 : 시스템 및 이론 Vol.32 No.11·12

본 논문에서 다루는 문제는 품질 정보를 가지는 서열을 배치(alignment)하는 알고리즘이다. 시퀀싱(sequencing) 작업의 일부인 염기 결정 프로그램(base-calling program)에 의해서 생성되는 DNA 서열은 각 염기가 어느 정도 신뢰할 수 있는 가를 나타내는 품질 정보를 가진다. 그러나 지금까지 개발된 서열 배치 알고리즘들은 이러한 품질 정보를 고려하지 않았다. 본 논문에서는 품질 정보를 가지는 두 서열의 배치를 평가하는 기준을 제시한다. 이 평가 기준에 의한 최적의 서열 배치는 동적 프로그래밍(dynamic programming) 기법에 의해서 찾을 수 있다. In this paper we consider the problem of sequence alignment with quality scores. DNA sequences produced by a base-calling program (as part of sequencing) have quality scores which represent the confidence level for individual bases. However, previous sequence alignment algorithms do not consider such quality scores. To solve sequence alignment with quality scores, we propose a measure of an alignment of two sequences with quality scores. We show that an optimal alignment in this measure can be found by dynamic programming.

문자열 집합에 대한 일반화접미사트리의 병행적 생성 알고리즘

나중채(Joong Chae Na) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.1

접미사트리 는 주어진 한 문자열의 모든 접미사를 표현하는 트리로, 문자열 처리, 압축 등 다양한 분야에서 활용된다. 접미사트리는 문자열 집합에 대한 자료구조로 확장될 수 있는데, 이를 일반화접미사트리 라 부른다. 본 논문에서는 일반화접미사트리를 병행적 으로 생성하는 문제를 다룬다. 기존의 알고리즘은 문자열들을 역방향으로 처리하면서 일반화접미사트리를 생성하는데, 접미사트리가 활용되는 대부분의 응용에서는 문자열을 정방향으로 처리하고 있어, 기존의 알고리즘은 활용 범위가 매우 제한된다. 본 논문에서는 문자열들을 정방향으로 처리하면서 일반화접미사트리를 병행적으로 생성하는 알고리즘을 제시함으로써 기존 알고리즘의 문제점을 극복한다. The suffix tree, a compacted trie representing all suffixes of a given string, is utilized in various applications such as string processing and data compression. The suffix tree can be extended to a data structure of a set of strings, called the generalized suffix tree. In this paper we consider the problem of constructing concurrently the generalized suffix tree. The previous algorithm constructs the generalized suffix tree by processing strings in backward direction. In most applications, strings are handled in forward direction, and thus the previous algorithm has some limits. We propose an algorithm for constructing concurrently the generalized suffix tree by processing strings in forward direction.

극대 증가 부분서열을 찾는 선형 알고리즘

나중채(Joong Chae Na) 한국스마트미디어학회 2023 스마트미디어저널 Vol.12 No.6

최장 증가 부분서열(longest increasing subsequence)은 컴퓨터 과학 분야에서 오랫동안 연구되어온 주요 문제이다. 본 논문에서는 최장 조건을 극대로 완화한 극대 증가 부분서열(maximal increasing subsequence) 문제를 고려한다. 본 논문에서는 두 가지 버전의 증가 개념(단조증가, 순증가)에 대해, 알파벳 에 대한 서열의 극대 증가 부분서열을 구하는 선형시간 알고리즘을 제안한다. 극대 단조증가 부분서열을 구하는 알고리즘은 공간을 사용하고, 극대 순증가 부분서열을 구하는 알고리즘은 공간을 사용한다. The longest increasing subsequence is a fundamental problem which has been studied for a long time in computer science. In this paper, we consider the maximal increasing subsequence problem where the constraint is released from the longest to the maximal. For two kinds of increasing (monotone increasing and strictly increasing), we propose linear-time algorithms computing a maximal increasing subsequence of an input sequence from an alphabet . Our algorithm for computing a maximal monotone increasing subsequence requires space and our algorithm for computing a maximal strictly increasing subsequence requires space.

환형문자열에 대한 쌍합 기반의 다중서열배치

이태형(Taehyung Lee),나중채(Joong Chae Na),박근수(Kunsoo Park),심정섭(Jeong Seop Sim) 한국정보과학회 2011 정보과학회논문지 : 시스템 및 이론 Vol.38 No.3

환형문자열은 문자열의 첫 글자와 마지막 글자가 연결되어 고리 모양을 이루는 문자열로서 자연계에서 박테리아나 미토콘드리아의 DNA 등에서 흔히 발견된다. 다중서열배치 문제는 주어진 문자열 집합에서 유사한 부분을 중심으로 모든 문자열을 배치하는 문제로 분자 생물학 및 생물 정보학에서 여러 가지 연구에 응용되는 중요한 문제이다. 본 논문에서는 환형문자열에 대하여 해밍거리 기반의 쌍합 목적함수를 최소화하는 다중서열배치 문제를 정의한다. 또한 이를 해결하는 두 가지 알고리즘을 제안한다. Circular strings are different from linear strings in that the first (leftmost) symbol of a circular string is wrapped around next to the last (rightmost) symbol. In nature, for example, bacterial and mitochondrial DNAs typically form circular strings. In this paper, we consider the problem of multiple sequence alignment on circular strings, which is defined by using Hamming distance and Sum-of-Pairs score. We also propose two algorithms to solve this problem.

최장 공통 부분 서열과 극대 공통 부분 서열의 길이 비교 및 분석

이동엽 ( Dongyeop Lee ),나중채 ( Joong Chae Na ) 한국정보처리학회 2021 한국정보처리학회 학술대회논문집 Vol.28 No.2

최장 공통 부분 서열(Longest Common Subsequence, LCS)은 서열 유사도(Similarity)를 측정하기 위한 주요 지표 중 하나로 특별한 가정이 없는 한 두 문자열의 LCS 를 계산하기 위해서는 두 문자열의 길이의 곱에 비례하는 시간이 필요하다. 최근 최장(longest)이라는 조건을 극대(maximal)로 완화한 극대 공통 부분 서열(Maximal Common Subsequence, MCS)이 제시되었고, 두 문자열의 MCS 를 선형에 가까운 시간에 찾는 알고리즘이 개발되었다. 극대는 최장을 보장하지 않기 때문에 두 문자열의 MCS 길이는 LCS 길이와 달리 유일하지 않을 수 있고, LCS 길이가 매우 길어도 길이가 1 인 MCS 가 존재할 수도 있다. 본 논문에서는 기존 알고리즘에 의해 계산되는 MCS 의 효용성을 알아보기 위해, DNA 등 여러 종류의 실제 데이터와 랜덤 생성된 데이터에 대해 LCS 와 MCS 의 길이를 비교했다. MCS 길이는 LCS 길이 대비 실제 데이터에서 32.1 ~ 60.2%, 랜덤 데이터에서는 27.5 ~ 62.9%로 나타났다. 이 비율은 문자열을 이루고 있는 알파벳 수가 많을수록, 문자열의 길이가 길어질수록 감소했다.

품질정보의 사용유무에 따른 하플로타입 페이징의 결과 차이

이종찬 ( Jong-chan Lee ),나중채 ( Joong Chae Na ) 한국정보처리학회 2017 한국정보처리학회 학술대회논문집 Vol.24 No.1

인간 유전자의 SNP 서열 정보를 통해 하플로타입을 추정하는 하플로타입 페이징은 생명공학분야에서 중요한 연구분야이다. 최근에는 SNP 데이터가 많아짐에 따라 많은 하플로타입 페이징 알고리즘들이 제시되었다. 본 논문에서는 SNP 데이터의 오류로 인한 하플로타입 페이징의 한계점과 이를 해결하기 위한 품질정보의 사용에 관한 문제점을 언급한 후 이와 관련된 실험을 통해 품질정보가 하플로타입 페이징의 결과에 미치는 영향을 알아본다. 실험은 기존의 하플로타입 페이징 알고리즘을 사용하여 품질정보의 사용 유무에 따라 하플로타입 페이징 결과를 비교하는 과정으로 진행되었다. 실험 결과 하플로타입 페이징에 과정에서 품질정보를 사용하는 것은 품질정보를 사용하지 않았을 때 보다 좋은 결과를 보여주었다.