The Capacity of String-Duplication Systems
From MaRDI portal
Publication:2977005
DOI10.1109/TIT.2015.2505735zbMATH Open1359.94317arXiv1401.4634WikidataQ59902755 ScholiaQ59902755MaRDI QIDQ2977005FDOQ2977005
Farzad Farnoud (Hassanzadeh), Jehoshua Bruck, Moshe Schwartz
Publication date: 28 April 2017
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
Abstract: It is known that the majority of the human genome consists of repeated sequences. Furthermore, it is believed that a significant part of the rest of the genome also originated from repeated sequences and has mutated to its current form. In this paper, we investigate the possibility of constructing an exponentially large number of sequences from a short initial sequence and simple replication rules, including those resembling genomic replication processes. In other words, our goal is to find out the capacity, or the expressive power, of these string-replication systems. Our results include exact capacities, and bounds on the capacities, of four fundamental string-replication systems.
Full work available at URL: https://arxiv.org/abs/1401.4634
Cited In (7)
- Bound-decreasing duplication system
- The tandem duplication distance problem is hard over bounded alphabets
- On the maximum number of non-confusable strings evolving under short tandem duplications
- On duplication-free codes for disjoint or equal-length errors
- Tandem Duplications, Segmental Duplications and Deletions, and Their Applications
- Deciding the Confusability of Words under Tandem Repeats in Linear Time
- Computing the Tandem Duplication Distance is NP-Hard
This page was built for publication: The Capacity of String-Duplication Systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977005)
