Tuan Thanh Nguyen

Dr. Tuan Thanh Nguyen

orcid

Research Focus & Metrics

Academic Career Length

8Years (2019-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 January 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
KCKui Cai
Kui Cai
YCYeow Meng Chee
Yeow Meng Chee
RGRyan Gabrys
Ryan Gabrys
HKHan Mao Kiah
Han Mao Kiah
Tuan Thanh NguyenTuan Thanh Nguyen
Tuan Thanh Nguyen
An indel refers to a single insertion or deletion, while an edit refers to a single insertion, deletion or substitution. In this article, we investigate codes that correct either a single indel or a single edit and provide linear-time algorithms that encode binary messages into these codes of length n. Over the quaternary alphabet, we provide two linear-time encoders. One corrects a single edit with ⌈log n⌉+ O(loglog n) redundancy bits, while the other corrects a single indel with ⌈log n⌉+2 redundant bits. These two encoders are order-optimal. The former encoder is the first known order-optimal encoder that corrects a single edit, while the latter encoder (that corrects a single indel) reduces the redundancy of the best known encoder of Tenengolts (1984) by at least four bits. Over the DNA alphabet, we impose an additional constraint: the GC-balanced constraint and require that exactly half of the symbols of any DNA codeword to be either C or G. In particular, via a modification of Knuth's balancing technique, we provide a linear-time map that translates binary messages into GC-balanced codewords and the resulting codebook is able to correct a single indel or a single edit. These are the first known constructions of GC-balanced codes that correct a single indel or a single edit.

17 March 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Tuan Thanh NguyenTuan Thanh Nguyen
Tuan Thanh Nguyen
KCKui Cai
Kui Cai
KIKees Schouhamer Immink
Kees Schouhamer Immink
HKHan Mao Kiah
Han Mao Kiah
We propose coding techniques that simultaneously limit the length of homopolymers runs, ensure the GC-content constraint, and are capable of correcting a single edit error in strands of nucleotides in DNA-based data storage systems. In particular, for given l , ∈ > 0, we propose simple and efficient encoders/decoders that transform binary sequences into DNA base sequences (codewords), namely sequences of the symbols A, T, C and G, that satisfy all of the following properties: 1) runlength constraint: the maximum homopolymer run in each codeword is at most l ; 2) GC-content constraint: the GC-content of each codeword is within [0.5-∈,0.5+∈]; 3) error-correction: each codeword is capable of correcting a single deletion, or single insertion, or single substitution error. While various combinations of these properties have been considered in the literature, this work provides generalizations of codes constructions that satisfy all the properties with arbitrary parameters of l and ∈. Furthermore, for practical values of l and ∈, we show that our encoders achieve higher rates than existing results in the literature and approach capacity. Our methods have low encoding/decoding complexity and limited error propagation.

26 October 2021 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
KCKui Cai
Kui Cai
HKHan Mao Kiah
Han Mao Kiah
Tuan Thanh NguyenTuan Thanh Nguyen
Tuan Thanh Nguyen
EYEitan Yaakobi
Eitan Yaakobi
The sequence reconstruction problem, introduced by Levenshtein in 2001, considers a communication scenario where the sender transmits a codeword from some codebook and the receiver obtains multiple noisy reads of the codeword. The common setup assumes the codebook to be the entire space and the problem is to determine the minimum number of distinct reads that is required to reconstruct the transmitted codeword. Motivated by modern storage devices, we study a variant of the problem where the number of noisy reads $N$ is fixed. Specifically, we design reconstruction codes that reconstruct a codeword from $N$ distinct noisy reads. We focus on channels that introduce a single edit error (i.e. a single substitution, insertion, or deletion) and their variants, and design reconstruction codes for all values of $N$ . In particular, for the case of a single edit, we show that as the number of noisy reads increases, the number of redundant symbols required can be gracefully reduced from $\log _{q} n+O(1)$ to $\log _{q} \log _{q} n+O(1)$ , and then to $O(1)$ , where $n$ denotes the length of a codeword. We also show that these reconstruction codes are asymptotically optimal. Finally, via computer simulations, we demonstrate that in certain cases, reconstruction codes can achieve similar performance as classical error-correcting codes with less redundant symbols.

26 June 2024 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
Tuan Thanh NguyenTuan Thanh Nguyen
Tuan Thanh Nguyen
KCKui Cai
Kui Cai
PSPaul H. Siegel
Paul H. Siegel
The problem of correcting deletions and insertions has recently received significantly increased attention due to the DNA-based data storage technology, which suffers from deletions and insertions with extremely high probability. In this work, we study the problem of constructing non-binary burst-deletion/insertion correcting codes. Particularly, for the quaternary alphabet, our designed codes are suited for correcting a burst of deletions/insertions in DNA storage. Non-binary codes correcting a single deletion or insertion were introduced by Tenengolts [1984], and the results were extended to correct a fixed-length burst of deletions or insertions by Schoeny et al . [2017]. Recently, Wang et al . [2021] proposed constructions of non-binary codes of length n , correcting a burst of length at most two for q -ary alphabets with redundancy log n + O (log q log log n ) bits, for arbitrary even q . The common idea in those constructions is to convert non-binary sequences into binary sequences, and the error decoding algorithms for the q -ary sequences are mainly based on the success of recovering the corresponding binary sequences, respectively. In this work, we look at a natural solution that the error detection and correction algorithms are performed directly over q -ary sequences, and for certain cases, our codes provide a more efficient encoder with lower redundancy than the best-known encoder in the literature. Particularly, • (Single-error correction codes) We first present a new version of non-binary VT codes that are capable of correcting a single deletion or single insertion, providing an alternative simpler and more efficient encoder of the construction by Tenengolts [1984]. Our construction is based on the differential vector , and the codes are referred to as the differential VT codes . In addition, we provide linear-time algorithms that encode user messages into these codes of length n over the q -ary alphabet for q ⩾ 2 with at most ⌈log q n ⌉+1 redundant symbols, while the optimal redundancy required is at least log q n +log q ( q −1) symbols. Our designed encoder reduces the redundancy of the best-known encoder of Tenengolts [1984] by at least 2 redundant symbols or equivalently 2 log 2 q bits. • (Burst-error correction codes) We use the idea of the binary shifted VT codes to define the q-ary differential shifted VT codes , and propose non-binary codes correcting a burst of up to two deletions (or two insertions) with redundancy log n + 3 log log n + O (log q ) bits, which improves a recent result of Wang et al. [2021] with redundancy log n + O (log q log log n ) bits for all q ⩾ 8. We then extend the construction to design non-binary codes correcting a burst of either exactly or at most t deletions (or insertions) for arbitrary t ⩾ 2.

7 August 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
YCYeow Meng Chee
Yeow Meng Chee
SLSan Ling
San Ling
Tuan Thanh NguyenTuan Thanh Nguyen
Tuan Thanh Nguyen
VVVan Khu Vu
Van Khu Vu
HWHengjia Wei
Hengjia Wei
XZXiande Zhang
Xiande Zhang
Permutation codes and multipermutation codes are widely studied due to various applications in information theory. Designing codes correcting deletion errors has been the main subject of works in the literature and to the best of our knowledge, there exist only optimal codes capable of correcting a single deletion in a permutation. In this paper, we construct several classes of permutation and multipermutation codes that are capable of correcting a burst deletion of length s ≥ 2, for both stable and unstable models. Efficient error decoders are provided to show the correctness of our constructions.

16 July 2019 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
YCYeow Meng Chee
Yeow Meng Chee
JCJohan Chrisnata
Johan Chrisnata
HKHan Mao Kiah
Han Mao Kiah
Tuan Thanh NguyenTuan Thanh Nguyen
Tuan Thanh Nguyen
Tandem duplication in DNA is the process of inserting a copy of a segment of DNA adjacent to the original position. Motivated by applications that store data in living organisms, Jain et al. (2016) proposed the study of codes that correct tandem duplications to improve the reliability of data storage. We investigate algorithms associated with the study of these codes. Two words are said to be ⩽-confusable if there exists a sequence of tandem duplications for each word, where each duplication is of length at most k , such that the resulting two words after duplications are equal. For k =3, we demonstrate that the problem of deciding whether two words is ⩽3-confusable is linear-time solvable through a characterisation that can be checked efficiently. Combining with previous results, the decision problem is linear-time solvable for k ⩽ 3. We conjecture that this problem is undecidable for k > 3. Using insights gained from the algorithm, we study the size of tandem-duplication codes. We improve the previous known upper bound and then construct codes with larger sizes as compared to the previous constructions. We determine the sizes of optimal tandem-duplication codes for lengths up to 20, develop recursive methods to construct tandem-duplication codes for all word lengths, and compute explicit lower bounds for the size of optimal tandem-duplication codes for lengths from 21 to 30.