The Capacity of String-Duplication Systems
Open Access
- 4 December 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 62 (2) , 811-824
Abstract
It is known that the majority of the human genome consists of duplicated sequences. Furthermore, it is believed that a significant part of the rest of the genome also originated from duplicated 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 using simple duplication rules, including those resembling genomic-duplication processes. In other words, our goal is to find the capacity, or the expressive power, of these string-duplication systems. Our results include exact capacities, and bounds on the capacities, of four fundamental string-duplication systems. The study of these fundamental biologically inspired systems is an important step toward modeling and analyzing more complex biological processes.Keywords
Funding Information
- National Science Foundation within the Expeditions in Computing Program through the Molecular Programming Project
This publication has 13 references indexed in Scilit:
- A stochastic model for genomic interspersed duplication2015
- Capacity and expressiveness of genomic tandem duplication2015
- The biological effects of simple tandem repeats: Lessons from the repeat expansion diseases: Table 1.Genome Research, 2008
- Constrained Coding for Context-Free Languages with Applications to Genetic Sequence Modelling2007
- Uniformly bounded duplication languagesDiscrete Applied Mathematics, 2005
- Molecular origins of rapid and continuous morphological evolutionProceedings of the National Academy of Sciences, 2004
- Origin and Evolution of Tandem Repeats in the Mitochondrial DNA Control Region of Shrikes (Lanius spp.)Journal of Molecular Evolution, 2004
- Operations and language generating devices suggested by the genome evolutionTheoretical Computer Science, 2001
- The inverted repeat as a recognizable structural feature in supercoiled DNA molecules.Proceedings of the National Academy of Sciences, 1980
- A Mathematical Theory of CommunicationBell System Technical Journal, 1948