Union Bound for Generalized Duplication Channels with DTW Decoding
Adrian Vidal, V. B. Wijekoon, Emanuele Viterbo · 2023
In this paper, we calculate a union bound for dynamic time warping (DTW)-based decoding of piecewise constant signals corrupted by additive noise and time stretching due to sample duplications, as observed in raw measurement signals obtained from nanopore sequencers. We consider both finitely- and infinitely-supported duplications with geometric-like characteristic, which include discrete uniform distributions as a special case. First, we provide explicit algorithms that calculate the union bound in O(αk2) time for the infinite-support case and in O(β2k2) for the finite-support case, where k is the codeword length, α is the minimum duplication, and β is the maximum duplication. Next, we show that a multi-read union bound exhibits a thresholding effect, where the error probability can be made arbitrarily close to zero by aggregating DTW distances from sufficiently many independent reads. Finally, we validate the calculated bounds relative to simulation results.