Farnoud (Hassanzadeh), Farzad and Schwartz, Moshe and Bruck, Jehoshua (2016) The Capacity of String-Duplication Systems. IEEE Transactions on Information Theory, 62 (2). pp. 811-824. ISSN 0018-9448. doi:10.1109/TIT.2015.2505735. https://resolver.caltech.edu/CaltechAUTHORS:20160119-142638953
![]() |
PDF
- Submitted Version
See Usage Policy. 156kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160119-142638953
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.
Item Type: | Article | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||||||||
ORCID: |
| |||||||||||||||
Additional Information: | © 2016 IEEE. Manuscript received November 24, 2014; revised July 10, 2015; accepted October 26, 2015. Date of publication December 4, 2015; date of current version January 18, 2016. This work was supported by the National Science Foundation within the Expeditions in Computing Program through the Molecular Programming Project. This paper was presented in part at the 2014 IEEE International Symposium on Information Theory. | |||||||||||||||
Funders: |
| |||||||||||||||
Subject Keywords: | Capacity, DNA, string duplication, formal languages, constrained coding | |||||||||||||||
Issue or Number: | 2 | |||||||||||||||
DOI: | 10.1109/TIT.2015.2505735 | |||||||||||||||
Record Number: | CaltechAUTHORS:20160119-142638953 | |||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20160119-142638953 | |||||||||||||||
Official Citation: | Farnoud Hassanzadeh, F.; Schwartz, M.; Bruck, J., "The Capacity of String-Duplication Systems," in Information Theory, IEEE Transactions on , vol.62, no.2, pp.811-824, Feb. 2016 doi: 10.1109/TIT.2015.2505735 | |||||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||||||||
ID Code: | 63773 | |||||||||||||||
Collection: | CaltechAUTHORS | |||||||||||||||
Deposited By: | Ruth Sustaita | |||||||||||||||
Deposited On: | 19 Jan 2016 22:59 | |||||||||||||||
Last Modified: | 10 Nov 2021 23:21 |
Repository Staff Only: item control page