Elishco, Ohad and Farnoud (Hassanzadeh), Farzad and Schwartz, Moshe and Bruck, Jehoshua (2018) The Capacity of Some Pólya String Models. Parallel and Distributed Systems Group Technical Reports, 142. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20180820-100255874
![]() |
PDF
- Submitted Version
See Usage Policy. 357kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20180820-100255874
Abstract
We study random string-duplication systems, which we call Pólya string models. These are motivated by DNA storage in living organisms, and certain random mutation processes that affect their genome. Unlike previous works that study the combinatorial capacity of string-duplication systems, or various string statistics, this work provides exact capacity or bounds on it, for several probabilistic models. In particular, we study the capacity of noisy string-duplication systems, including the tandem-duplication, end-duplication, and interspersed-duplication systems. Interesting connections are drawn between some systems and the signature of random permutations, as well as to the beta distribution common in population genetics.
Item Type: | Report or Paper (Technical Report) | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||
ORCID: |
| ||||||||||
Additional Information: | The material in this paper was presented in part at the 2016 IEEE International Symposium on Information Theory. | ||||||||||
Group: | Parallel and Distributed Systems Group | ||||||||||
Subject Keywords: | DNA storage, string-duplication systems, capacity, Pólya string models | ||||||||||
Other Numbering System: |
| ||||||||||
Series Name: | Parallel and Distributed Systems Group Technical Reports | ||||||||||
Issue or Number: | 142 | ||||||||||
Record Number: | CaltechAUTHORS:20180820-100255874 | ||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20180820-100255874 | ||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||
ID Code: | 88948 | ||||||||||
Collection: | CaltechPARADISE | ||||||||||
Deposited By: | George Porter | ||||||||||
Deposited On: | 20 Aug 2018 17:16 | ||||||||||
Last Modified: | 18 Aug 2021 01:17 |
Repository Staff Only: item control page