Vol. 14, No. 4, 2021

Download this article
Download this article For screen
For printing
Recent Issues

Volume 14
Issue 4, 541–721
Issue 3, 361–540
Issue 2, 181–360
Issue 1, 1–179

Volume 13, 5 issues

Volume 12, 8 issues

Volume 11, 5 issues

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Editorial Board
Editors’ Interests
Subscriptions
 
Submission Guidelines
Submission Form
Policies for Authors
Ethics Statement
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Author Index
Coming Soon
 
Other MSP Journals
Shotgun identification on groups

Jacob Raymond, Robert Bland and Kevin McGoff

Vol. 14 (2021), No. 4, 631–682
Abstract

We consider the problem of shotgun identification of patterns on groups, which extends previous work on shotgun identification of DNA sequences and labeled graphs. A shotgun identification problem on a group G is specified by two finite subsets C,K G and a finite alphabet 𝒜. In such problems, there is a “global” pattern w 𝒜CK , and one would like to be able to identify this pattern (up to translation) based only on observation of the “local” K-shaped subpatterns of w, called reads, centered at the elements of C. We consider an asymptotic regime in which the size of w tends to infinity and the symbols of w are drawn in an i.i.d. fashion. Our first general result establishes sufficient conditions under which the random pattern w is identifiable from its reads with probability tending to 1, and our second general result establishes sufficient conditions under which the random pattern w is nonidentifiable with probability tending to 1. Additionally, we illustrate our main results by applying them to several families of examples.

Keywords
identifiability, shotgun identification
Mathematical Subject Classification
Primary: 60C05
Secondary: 94A15
Milestones
Received: 4 September 2020
Revised: 25 March 2021
Accepted: 29 March 2021
Published: 23 October 2021

Communicated by John C. Wierman
Authors
Jacob Raymond
Department of Mathematics and Statistics
University of North Carolina at Charlotte
Charlotte, NC
United States
Robert Bland
Department of Mathematics and Statistics
University of North Carolina at Charlotte
Charlotte, NC
United States
Kevin McGoff
Department of Mathematics and Statistics
University of North Carolina at Charlotte
Charlotte, NC
United States