Shotgun identification on groups

Raymond, Jacob; Bland, Robert; McGoff, Kevin

doi:10.2140/involve.2021.14.631

Download this article
	For screen
	For printing

Recent Issues

The Journal

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

This article is available for purchase or by subscription. See below.

Shotgun identification on groups

Jacob Raymond, Robert Bland and Kevin McGoff

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

DOI: 10.2140/involve.2021.14.631

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 \subset G$ and a finite alphabet $𝒜$ . In such problems, there is a “global” pattern $w \in 𝒜^{C K}$ , 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.

PDF Access Denied

We have not been able to recognize your IP address 18.221.239.148 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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

Vol. 14, No. 4, 2021