The Capacity of String-Duplication Systems

DOI10.1109/TIT.2015.2505735MaRDI QIDQ2977005zbMATH OpenWikidataFDO

Authors Moshe Schwartz, Jehoshua Bruck, Farzad Farnoud (Hassanzadeh)

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.4634

Mathematics Subject Classification ID

Measures of information, entropy (94A17)

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.

Cited in

(7)

• Bound-decreasing duplication system
• Deciding the confusability of words under tandem repeats in linear time
• The tandem duplication distance problem is hard over bounded alphabets
• On the maximum number of non-confusable strings evolving under short tandem duplications
• Computing the tandem duplication distance is NP-hard
• On duplication-free codes for disjoint or equal-length errors
• Tandem Duplications, Segmental Duplications and Deletions, and Their Applications

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)