|
|||||
 |
|
|
|
|
|
|
|
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 is specified by two finite subsets and a finite alphabet . In such problems, there is a “global” pattern , and one would like to be able to identify this pattern (up to translation) based only on observation of the “local” -shaped subpatterns of , called reads, centered at the elements of . We consider an asymptotic regime in which the size of tends to infinity and the symbols of are drawn in an i.i.d. fashion. Our first general result establishes sufficient conditions under which the random pattern is identifiable from its reads with probability tending to 1, and our second general result establishes sufficient conditions under which the random pattern 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 |
|
