Author name cluster

Chin Lung Lu

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.

8 papers

1 author row

TCS Journal 2026 Journal Article

A sparse dynamic programming algorithm for solving the coding sequence design problem

Long-Shang Cho
Kai-Wei Chang
Chin Lung Lu

In this work, we study the coding sequence design problem, which involves designing a coding sequence to encode a given amino acid sequence by optimizing both its secondary structure stability and codon usage. The structural stability and codon usage are quantified by minimum free energy and codon adaptation index, respectively. The coding sequence design problem is important since it has significant potential for the development of mRNA-based vaccines. Previously, we proposed an O ( L 3 ) time and O ( L 2 ) space dynamic programming algorithm to solve the coding sequence design problem, where L is the length of the coding sequence to be designed. In this study, we utilize the sparsification technique to further reduce the time complexity of this dynamic programming algorithm from O ( L 3 ) to O ( L 2 + Z P ) for the problem under the base pair-based energy model, where Z and P are two sparsity parameters satisfying Z ≤ L ( 6 + P ) and P ≤ 36 L. Experimental results on a biological dataset show that our sparse dynamic programming algorithm achieves a 35-fold to 49-fold speedup over its non-sparse counterpart.

Details DOI

TCS Journal 2021 Journal Article

Computing a longest common almost-increasing subsequence of two sequences

Toan Thang Ta
Yi-Kung Shieh
Chin Lung Lu

Given a positive constant c, a sequence S = 〈 s 1, s 2, …, s k 〉 of k numbers is said to be almost increasing if and only if s i > max 1 ≤ j < i ⁡ s j − c for all 1 < i ≤ k. A longest common almost-increasing subsequence (LCaIS) between two input sequences is a longest common subsequence that is also an almost increasing sequence. We found out that the existing algorithm proposed by Moosa et al. [1] to find an LCaIS of two sequences without repeated elements gives an incorrect result for some instances. In this work, we present a dynamic programming algorithm that can correctly compute an LCaIS between any two sequences with repeated elements in O ( n m l ) time and O ( n m ) space, where n and m are the lengths of two input sequences and l is the length of the output LCaIS.

Details DOI

TCS Journal 2021 Journal Article

The exact multiple pattern matching problem solved by a reference tree approach

Yi-Kung Shieh
Shyong Jian Shyu
Chin Lung Lu
Richard Chia-Tung Lee

Given a text T and a set of r patterns P 1, P 2, …, P r, the exact multiple pattern matching problem reports the ending positions of all occurrences of P i in T for 1 ≤ i ≤ r. By transforming all substrings with a fixed length of T into a reference tree such that each internal node stores a reference string, the exact multiple pattern matching problem can be efficiently solved by searching patterns in the tree via the guidance of the reference strings. We design elegant algorithms to construct the reference tree (the preprocessing phase) and to search patterns in the tree (the searching phase) using bitwise operations. The experiments involving problem instances from the DNA sequence and the English language are conducted to compare the performance of our approach against those of the suffix tree and suffix array algorithms. The computational results demonstrate the advantage of our approach over these algorithms. In spite of the simplicity, our approach is quite efficient, flexible and robust.

Details DOI

TCS Journal 2016 Journal Article

An efficient algorithm for one-sided block ordering problem under block-interchange distance

Kun-Tze Chen
Chi-Long Li
Hsien-Tai Chiu
Chin Lung Lu

In this work, we study the one-sided block ordering problem under block-interchange distance. Given two signed permutations π and σ of size n, where π represents a partially assembled genome consisting of several blocks (i. e. , contigs) and σ represents a completely assembled genome, the one-sided block ordering problem under block-interchange distance is to order (i. e. , assemble) the blocks of π such that the block-interchange distance between the assembly of π and σ is minimized. The one-sided block ordering problem is useful in genome resequencing, because its algorithms can be used to assemble the contigs of partially assembled resequencing genomes based on their completely assembled genomes. By using permutation groups in algebra, we design an efficient algorithm to solve the one-sided block ordering problem under block-interchange distance in O ( n log ⁡ n ) time. Moreover, we show that the assembly of π can be done in O ( n ) time and its block-interchange distance from σ can also be calculated in advance in O ( n ) time.

Details DOI

TCS Journal 2013 Journal Article

A new filtration method and a hybrid strategy for approximate string matching

Chia Wei Lu
Chin Lung Lu
R.C.T. Lee

In this paper, we propose a new filtration algorithm, as well as a hybrid filtration strategy, to efficiently solve the approximate string matching problem (also called the k -difference problem), which aims to find all the positions i ’s in a given text such that there exists a substring of the text ending at position i whose edit distance from a given pattern is less than or equal to a given error bound k. Our experimental results on simulated datasets of DNA sequences show that when compared with other filtration algorithms, our filtration algorithm has better performance on the efficiency to filter out those positions of the text at which the pattern does not occur approximately. Moreover, our hybrid filtration strategy further improves the effectiveness of our filtration algorithm.

Details DOI

TCS Journal 2005 Journal Article

The approximability of the weighted Hamiltonian path completion problem on a tree

Quincy Wu
Chin Lung Lu
Richard Chia-Tung Lee

Given a graph, the Hamiltonian path completion problem is to find an augmenting edge set such that the augmented graph has a Hamiltonian path. In this paper, we show that the Hamiltonian path completion problem will unlikely have any constant ratio approximation algorithm unless NP = P. This problem remains hard to approximate even when the given subgraph is a tree. Moreover, if the edge weights are restricted to be either 1 or 2, the Hamiltonian path completion problem on a tree is still NP-hard. Then it is observed that this problem is strongly NP-hard, so it does not have any fully polynomial-time approximation scheme (FPTAS) unless NP=P. When the given tree is a k-tree, we give an approximation algorithm with performance ratio 1. 5.

Details DOI

TCS Journal 2003 Journal Article

Efficient minus and signed domination in graphs

Chin Lung Lu
Sheng-Lung Peng
Chuan Yi Tang

An efficient minus (respectively, signed) dominating function of a graph G=(V, E) is a function f: V→{−1, 0, 1} (respectively, {−1, 1}) such that ∑u∈N[v] f(u)=1 for all v∈V, where N[v]={v}∪{u|(u, v)∈E}. The efficient minus (respectively, signed) domination problem is to find an efficient minus (respectively, signed) dominating function of G. In this paper, we show that the efficient minus (respectively, signed) domination problem is NP-complete on chordal graphs, chordal bipartite graphs, planar bipartite graphs and planar graphs of maximum degree 4 (respectively, on chordal graphs). Based on the forcing property on blocks of vertices and automata theory, we provide a uniform approach to show that in a special class of interval graphs, every graph (respectively, every graph with no vertex of odd degree) has an efficient minus (respectively, signed) dominating function. We also give linear-time algorithms to find these functions. Besides, we show that the efficient minus domination problem is equivalent to the efficient domination problem on trees.

Details DOI

TCS Journal 2003 Journal Article

The full Steiner tree problem

Chin Lung Lu
Chuan Yi Tang
Richard Chia-Tung Lee

Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G=(V, E) with a length function on E and a proper subset R⊂V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either 1 or 2. For the instances with lengths either 1 or 2, we give a 8 5 -approximation algorithm to find an approximate solution for the problem.

Details DOI