Shotgun identification on groups

DOI10.2140/INVOLVE.2021.14.631MaRDI QIDQ2238478zbMATH OpenOpenAlexFDO

Authors Jacob Raymond, Kevin McGoff, Robert G. Bland

Publication date 1 November 2021

Published in Involve (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.02255

zbMATH Keywords

identifiabilityshotgun identification

Mathematics Subject Classification ID

Combinatorial probability (60C05) Information theory (general) (94A15)

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 $CsubsetG$ and $KsubsetG$ and a finite alphabet $mathcalA$. In such problems, there is a ``global" pattern $winmathcal{A}^{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 one, and our second general result establishes sufficient conditions under which the random pattern $w$ is non-identifiable with probability tending to one. Additionally, we illustrate our main results by applying them to several families of examples.

Recommendations

• Shotgun assembly of Erdős-Rényi random graphs
• scientific article; zbMATH DE number 956614
• scientific article; zbMATH DE number 826053
• Identification of Distinguishing Motifs
• scientific article; zbMATH DE number 702949

Cites work

• Group synchronization on grids
• Information Theory of DNA Shotgun Sequencing
• Jigsaw percolation: what social networks can collaboratively solve a puzzle?
• Message-passing algorithms for synchronization problems over compact groups
• Shotgun assembly of random jigsaw puzzles
• The geometry of synchronization problems and learning group actions
• Three-dimensional structure determination from common lines in cryo-EM by eigenvectors and semidefinite programming

Cited in

(2)

• Shotgun assembly of Erdős-Rényi random graphs
• Shotgun assembly threshold for lattice labeling model

This page was built for publication: Shotgun identification on groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2238478)