Ryan Gabrys

Ryan Gabrys

Auto-generated profile, based on publicly available information

Ryan Gabrys

Department of Electrical and Computer Engineering, University of California, La Jolla, San Diego, CA, USA

Research Focus & Metrics

Academic Career Length

19Years (2008-Present)

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

Representative Publications

View All Publications
16 October 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
RGRyan Gabrys
Ryan Gabrys
FSFrederic Sala
Frederic Sala
In this paper, we investigate the problem of constructing codes capable of correcting two deletions. In particular, we construct a code that requires redundancy approximately 8 log 2 n + O(log 2 log 2 n) bits of redundancy, where n denotes the length of the code. To the best of the authors' knowledge, this represents the best known construction in that it requires the lowest number of redundant bits for a code correcting two deletions.

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.

12 January 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
SYS. M. Hossein Tabatabaei Yazdi
S. M. Hossein Tabatabaei Yazdi
HKHan Mao Kiah
Han Mao Kiah
RGRyan Gabrys
Ryan Gabrys
OMOlgica Milenkovic
Olgica Milenkovic
We introduce the notion of weakly mutually uncorrelated (WMU) sequences, motivated by applications in DNAbased data storage systems and synchronization between communication devices. WMU sequences are characterized by the property that no sufficiently long suffix of one sequence is the prefix of the same or another sequence. WMU sequences used for primer design in DNA-based data storage systems are also required to be at large mutual Hamming distance from each other, have balanced compositions of symbols, and avoid primer-dimer byproducts. We derive bounds on the size of WMU and various constrained WMU codes and present a number of constructions for balanced, error-correcting, primer-dimer free WMU codes using Dyck paths, prefix-synchronized and cyclic codes.

28 November 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
RGRyan Gabrys
Ryan Gabrys
EYEitan Yaakobi
Eitan Yaakobi
OMOlgica Milenkovic
Olgica Milenkovic
Motivated by applications in DNA-based storage, we introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which, in addition to deletions, insertions and substitution errors also accounts for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. We conclude with constructions for joint block deletion and adjacent block transposition error-correcting codes.

21 May 2020 in IEEE Transactions on Information Theory
Verified
Journal Article
Open access
MCMahdi Cheraghchi
Mahdi Cheraghchi
RGRyan Gabrys
Ryan Gabrys
Olgica MilenkovićOlgica Milenković
Olgica Milenković
JRJoao Ribeiro
Joao Ribeiro
Motivated by average-case trace reconstruction and coding for portable DNA-based storage systems, we initiate the study of coded trace reconstruction , the design and analysis of high-rate efficiently encodable codes that can be efficiently decoded with high probability from few reads (also called traces ) corrupted by edit errors. Codes used in current portable DNA-based storage systems with nanopore sequencers are largely based on heuristics, and have no provable robustness or performance guarantees even for an error model with i.i.d. deletions and constant deletion probability. Our work is the first step towards the design of efficient codes with provable guarantees for such systems. We consider a constant rate of i.i.d. deletions, and perform an analysis of marker-based code-constructions. This gives rise to codes with redundancy $O(n/\log n)$ (resp. $O(n/\log \log n)$ ) that can be efficiently reconstructed from $\exp (O(\log ^{2/3}n))$ (resp. $\exp (O(\log \log n)^{2/3})$ ) traces, where $n$ is the message length. Then, we give a construction of a code with $O(\log n)$ bits of redundancy that can be efficiently reconstructed from $\text {poly}(n)$ traces if the deletion probability is small enough. Finally, we show how to combine both approaches, giving rise to an efficient code with $O(n/\log n)$ bits of redundancy which can be reconstructed from $\text {poly}(\log n)$ traces for a small constant deletion probability.

31 January 2018 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
RGRyan Gabrys
Ryan Gabrys
EYEitan Yaakobi
Eitan Yaakobi
The sequence reconstruction problem, first proposed by Levenshtein, models the setup in which a sequence from some set is transmitted over several channels, and the decoder receives the outputs from every channel. The channels are almost independent as it is only required that all outputs are different from each other. The main problem of interest is to determine the minimum number of channels required to reconstruct the transmitted sequence. In the combinatorial context, the problem is equivalent to finding the maximum intersection between two balls of radius t, where the distance between their centers is at least d. The setup of this problem was studied before for several error metrics such as the Hamming metric, the Kendalltau metric, and the Johnson metric. In this paper, we extend the study initiated by Levenshtein for reconstructing sequences over the deletion channel. While he solved the case where the transmitted sequence can be arbitrary, we study the setup, where the transmitted sequence belongs to a single-deletion-correcting code and there are t deletions in every channel. Under this paradigm, we study the minimum number of different channel outputs in order to construct a successful decoder.