Jain, Siddharth and Farnoud (Hassanzadeh), Farzad and Bruck, Jehoshua (2017) Capacity and Expressiveness of Genomic Tandem Duplication. IEEE Transactions on Information Theory, 63 (10). pp. 6129-6138. ISSN 0018-9448. doi:10.1109/TIT.2017.2728079. https://resolver.caltech.edu/CaltechAUTHORS:20170719-165632439
![]() |
PDF
- Submitted Version
See Usage Policy. 424kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170719-165632439
Abstract
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.
Item Type: | Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||||||||
ORCID: |
| |||||||||||||||
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. | |||||||||||||||
Funders: |
| |||||||||||||||
Subject Keywords: | Capacity, expressiveness, tandem repeats, tandem duplication, finite automaton, irreducible string | |||||||||||||||
Issue or Number: | 10 | |||||||||||||||
DOI: | 10.1109/TIT.2017.2728079 | |||||||||||||||
Record Number: | CaltechAUTHORS:20170719-165632439 | |||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20170719-165632439 | |||||||||||||||
Official Citation: | S. Jain, F. Farnoud Hassanzadeh and J. Bruck, "Capacity and Expressiveness of Genomic Tandem Duplication," in IEEE Transactions on Information Theory, vol. 63, no. 10, pp. 6129-6138, Oct. 2017. doi: 10.1109/TIT.2017.2728079 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7984889&isnumber=8036324 | |||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||||||||
ID Code: | 79216 | |||||||||||||||
Collection: | CaltechAUTHORS | |||||||||||||||
Deposited By: | Kristin Buxton | |||||||||||||||
Deposited On: | 20 Jul 2017 19:09 | |||||||||||||||
Last Modified: | 15 Nov 2021 17:46 |
Repository Staff Only: item control page