Author name cluster

Heejin Park

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

TCS Journal 2018 Journal Article

FM-index of alignment with gaps

Joong Chae Na
Hyunjoon Kim
Seunghwan Min
Heejin Park
Thierry Lecroq
Martine Léonard
Laurent Mouchard
Kunsoo Park

Recently a compressed index for similar strings, called the FM-index of alignment (FMA), has been proposed with the functionalities of pattern search and random access. The FMA is quite efficient in space requirement and pattern search time, but it is applicable only for an alignment of strings without gaps. In this paper we propose the FM-index of alignment with gaps, a realistic index for similar strings, which allows gaps in their alignment. For this, we design a new version of the suffix array of alignment by using an alignment transformation and a new definition of the alignment-suffix. The new suffix array of alignment enables us to support the LF-mapping and backward search, the key functionalities of the FM-index, regardless of gap existence in the alignment. We experimentally compared our index with RLCSA due to Mäkinen et al. and related indexes GCSA due to Sirén et al. and GCSA2 due to Sirén on genome sequences from the 1000 Genomes Project. The index size of our index is smaller than those of other indexes.

Details DOI

TCS Journal 2016 Journal Article

A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm

Youngho Kim
Joong Chae Na
Heejin Park
Jeong Seop Sim

Given two strings X ( | X | = m ) and Y ( | Y | = n ) over an alphabet Σ, the edit distance between X and Y can be computed in O ( m n / t ) time with the help of the Four-Russians' lookup table whose block size is t. The Four-Russians' lookup table can be constructed in O ( ( 3 | Σ | ) 2 t t 2 ) time using O ( ( 3 | Σ | ) 2 t t ) space. However, the construction time and space requirement of the lookup table grow very fast as the alphabet size increases and thus it has been used only when | Σ | is very small. For example, when a string is a protein sequence, | Σ | = 20 and thus it is almost impossible to use the Four-Russians' lookup table on typical workstations. In this paper, we present an efficient alphabet-independent Four-Russians' lookup table. It requires O ( 3 2 t ( 2 t )! t ) space and can be constructed in O ( 3 2 t ( 2 t )! t 2 ) time. Thus, the Four-Russians' lookup table can be constructed and used irrespective of the alphabet size. The time and space complexity were achieved by compacting the lookup table using a clever encoding of the preprocessed strings. Experimental results show that the space requirement of the lookup table is reduced to about 1/5, 172, 030 of its original size when | Σ | = 26 and t = 4. Furthermore, we present efficient multithreaded parallel algorithms for edit distance computation using the Four-Russians' lookup table. The parallel algorithm for lookup table construction runs in O ( t ) time and the parallel algorithm for edit distance computation between X and Y runs in O ( m + n ) time. Experiments performed on CUDA-supported GPU show that our algorithm runs about 942 times faster than the sequential version of the original Four-Russians' algorithm for 100 pairs of random strings of length approximately 1, 000 when | Σ | = 4 and t = 4.

Details DOI

TCS Journal 2016 Journal Article

FM-index of alignment: A compressed index for similar strings

Joong Chae Na
Hyunjoon Kim
Heejin Park
Thierry Lecroq
Martine Léonard
Laurent Mouchard
Kunsoo Park

In this paper we propose the FM-index of alignment, a compressed index for similar strings with the functionalities of pattern search and random access. For this, we first design a new and improved version of the suffix array of alignment. The FM-index of alignment is an FM-index of this suffix array of alignment. The FM-index of alignment supports the LF-mapping and backward search, the key functionalities of the FM-index, but the LF-mapping and backward search of our index is significantly more involved than the original FM-index. We implemented the FM-index of alignment and did experiments on 100 genome sequences from the 1000 Genomes Project. The index size of the FM-index of alignment is about a half of that of RLCSA due to Mäkinen et al.

Details DOI

TCS Journal 2013 Journal Article

Finding consensus and optimal alignment of circular strings

Taehyung Lee
Joong Chae Na
Heejin Park
Kunsoo Park
Jeong Seop Sim

Circular strings are different from linear strings in that the last symbol is considered to precede the first symbol. Even though circular strings are biologically important, only a few efforts have been made to solve computational problems on circular strings. In this paper, we introduce consensus problems for circular strings of length n and present the first non-trivial algorithms to find a consensus and an optimal alignment for circular strings by the Hamming distance. They are O ( n 2 log n ) -time algorithms for three circular strings and an O ( n 3 log n ) -time algorithm for four circular strings. Our algorithms are O ( n / log n ) times faster than the naïve algorithms directly using the solutions for the linear consensus problems, which take O ( n 3 ) time for three circular strings and O ( n 4 ) time for four circular strings. This speedup was achieved by reducing the problems into correlations and by formulating and solving systems of linear equations. Moreover, our algorithms use only O ( n ) space.

Details DOI

TCS Journal 2011 Journal Article

Efficient algorithms for consensus string problems minimizing both distance sum and radius

Amihood Amir
Gad M. Landau
Joong Chae Na
Heejin Park
Kunsoo Park
Jeong Seop Sim

The consensus (string) problem is finding a representative string, called a consensus, of a given set S of strings. In this paper we deal with consensus problems considering both distance sum and radius, where the distance sum is the sum of (Hamming) distances from the strings in S to the consensus and the radius is the longest (Hamming) distance from the strings in S to the consensus. Although there have been results considering either distance sum or radius, there have been no results considering both, to the best of our knowledge. We present the first algorithms for two consensus problems considering both distance sum and radius for three strings: one problem is to find an optimal consensus minimizing both distance sum and radius. The other problem is to find a bounded consensus such that the distance sum is at most s and the radius is at most r for given constants s and r. Our algorithms are based on characterization of the lower bounds of distance sum and radius, and thus they solve the problems efficiently. Both algorithms run in linear time.

Details DOI

TCS Journal 2001 Journal Article

Parallel algorithms for red–black trees

Heejin Park
Kunsoo Park

We present parallel algorithms for the following four operations on red–black trees: construction, search, insertion, and deletion. Our parallel algorithm for constructing a red–black tree from a sorted list of n items runs in O(1) time with n processors on the CRCW PRAM and runs in O(loglog n) time with n/loglog n processors on the EREW PRAM. Our construction algorithm does not require the assumptions that previous construction algorithms used. Each of our parallel algorithms for search, insertion, and deletion in red–black trees runs in O(log n+log k) time with k processors on the EREW PRAM, where k is the number of unsorted items to search for, insert, or delete and n is the number of nodes in a red–black tree.

Details DOI