Union bound for generalized duplication channels with DTW decoding

Adrian Vidal, V. B. Wijekoon, Emanuele Viterbo

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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(ak2) time for the infinite-support case and in O(ß2k2) for the finite-support case, where k is the codeword length, a 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.

Original languageEnglish
Title of host publication2023 IEEE International Symposium on Information Theory (ISIT)
EditorsAlbert Guillén i Fàbregas, Hsiao-Feng (Francis) Lu, Stefan M. Moser, Anelia Somekh-Baruch
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages6
ISBN (Electronic)9781665475549
ISBN (Print)9781665475556
Publication statusPublished - 2023
EventIEEE International Symposium on Information Theory 2023 - Taipei, Taiwan
Duration: 25 Jun 202330 Jun 2023
https://ieeexplore.ieee.org/xpl/conhome/10206429/proceeding (Proceedings)
https://isit2023.org/ (Website)


ConferenceIEEE International Symposium on Information Theory 2023
Abbreviated titleISIT 2023
Internet address

Cite this