Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 2017 | public
Journal Article Open

Capacity and Expressiveness of Genomic Tandem Duplication


The majority of the human genome consists of repeated sequences. An important type of repeated sequences common in the human genome are tandem repeats, where identical copies appear next to each other. For example, in the sequence AGTCGC, TGTG is a tandem repeat, that may be generated from AGTCTGC by a tandem duplication of length 2. In this work, we investigate the possibility of generating a large number of sequences from a seed, i.e. a small initial string, by tandem duplications of bounded length. We study the capacity of such a system, a notion that quantifies the system's generating power. Our results include exact capacity values for certain tandem duplication string systems. In addition, motivated by the role of DNA sequences in expressing proteins via RNA and the genetic code, we define the notion of the expressiveness of a tandem duplication system as the capability of expressing arbitrary substrings. We then completely characterize the expressiveness of tandem duplication systems for general alphabet sizes and duplication lengths. In particular, based on a celebrated result by Axel Thue from 1906, presenting a construction for ternary squarefree sequences, we show that for alphabets of size 4 or larger, bounded tandem duplication systems, regardless of the seed and the bound on duplication length, are not fully expressive, i.e. they cannot generate all strings even as substrings of other strings. Note that the alphabet of size 4 is of particular interest as it pertains to the genomic alphabet. Building on this result, we also show that these systems do not have full capacity. In general, our results illustrate that duplication lengths play a more significant role than the seed in generating a large number of sequences for these systems.

Additional Information

© 2017 IEEE. Manuscript received September 16, 2015; revised May 15, 2017; accepted July 7, 2017. Date of publication July 19, 2017; date of current version September 13, 2017. This work was supported by the NSF Expeditions in Computing Program–The Molecular Programming Project. This paper was presented at the 2015 IEEE International Symposium on Information Theory, Hong Kong. The authors would like to thank the anonymous reviewers for the thorough reviews and valuable comments. The reviews helped us make the finite automata and proofs presented in this paper simpler and more clear.

Attached Files

Submitted - 1509.06029.pdf


Files (424.5 kB)
Name Size Download all
424.5 kB Preview Download

Additional details

August 19, 2023
August 19, 2023