Alon, Noga and Bruck, Jehoshua and Farnoud, Farzad and Jain, Siddharth
(2016)
*On the duplication distance of binary strings.*
In:
2016 IEEE International Symposium on Information Theory (ISIT).
IEEE
, Piscataway, NJ, pp. 260-264.
ISBN 978-1-5090-1807-9.
http://resolver.caltech.edu/CaltechAUTHORS:20160824-101618060

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20160824-101618060

## Abstract

We study the tandem duplication distance between binary sequences and their roots. This distance is motivated by genomic tandem duplication mutations and counts the smallest number of tandem duplication events that are required to take one sequence to another. We consider both exact and approximate tandem duplications, the latter leading to a combined duplication/Hamming distance. The paper focuses on the maximum value of the duplication distance to the root. For exact duplication, denoting the maximum distance to the root of a sequence of length n by f(n), we prove that f(n) = Θ(n). For the case of approximate duplication, where a β-fraction of symbols may be duplicated incorrectly, we show using the Plotkin bound that the maximum distance has a sharp transition from linear to logarithmic in n at β = 1/2.

Item Type: | Book Section | |||||||||
---|---|---|---|---|---|---|---|---|---|---|

Related URLs: |
| |||||||||

ORCID: |
| |||||||||

Additional Information: | © 2016 IEEE. The authors would like to thank anonymous reviewers whose comments improved the presentation of this paper. This work was supported in part by the NSF Expeditions in Computing Program (The Molecular Programming Project), by a USA-Israeli BSF grant 2012/107, by an ISF grant 620/13, and by the Israeli I-Core program. | |||||||||

Funders: |
| |||||||||

Record Number: | CaltechAUTHORS:20160824-101618060 | |||||||||

Persistent URL: | http://resolver.caltech.edu/CaltechAUTHORS:20160824-101618060 | |||||||||

Official Citation: | N. Alon, J. Bruck, F. Farnoud and S. Jain, "On the duplication distance of binary strings," 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016, pp. 260-264. doi: 10.1109/ISIT.2016.7541301 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7541301&isnumber=7541040 | |||||||||

Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||

ID Code: | 69895 | |||||||||

Collection: | CaltechAUTHORS | |||||||||

Deposited By: | Tony Diaz | |||||||||

Deposited On: | 24 Aug 2016 21:42 | |||||||||

Last Modified: | 21 Sep 2017 23:53 |

Repository Staff Only: item control page