Abstract
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 language | English |
---|---|
Title of host publication | 2023 IEEE International Symposium on Information Theory (ISIT) |
Editors | Albert Guillén i Fàbregas, Hsiao-Feng (Francis) Lu, Stefan M. Moser, Anelia Somekh-Baruch |
Place of Publication | Piscataway NJ USA |
Publisher | IEEE, Institute of Electrical and Electronics Engineers |
Pages | 358-363 |
Number of pages | 6 |
ISBN (Electronic) | 9781665475549 |
ISBN (Print) | 9781665475556 |
DOIs | |
Publication status | Published - 2023 |
Event | IEEE International Symposium on Information Theory 2023 - Taipei, Taiwan Duration: 25 Jun 2023 → 30 Jun 2023 https://ieeexplore.ieee.org/xpl/conhome/10206429/proceeding (Proceedings) https://isit2023.org/ (Website) |
Conference
Conference | IEEE International Symposium on Information Theory 2023 |
---|---|
Abbreviated title | ISIT 2023 |
Country/Territory | Taiwan |
City | Taipei |
Period | 25/06/23 → 30/06/23 |
Internet address |
|