Shotgun Assembly of Labeled Graphs

被引：16
|
作者：
Mossel, Elchanan [1 ,2 ]
Ross, Nathan [3 ]
机构：
[1] Univ Calif Berkeley, Berkeley, CA 94720 USA
[2] Univ Penn, Philadelphia, PA 19104 USA
[3] Univ Melbourne, Sch Math & Stat, Parkville, Vic 3010, Australia
来源：
IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING | 2019年 / 6卷 / 02期
基金：
美国国家科学基金会;
关键词：
Random graphs; statistical identifiability; probabilistic algorithms; shotgun assembly; random jigsaw puzzles; DIAMETER;
D O I：
10.1109/TNSE.2017.2776913
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
We consider the problem of reconstructing graphs or labeled graphs from neighborhoods of a given radius r. Special instances of this problem include the well-known: DNA shotgun assembly; the lesser-known: neural network reconstruction; and a new problem: assembling random jigsaw puzzles. We provide some necessary and some sufficient conditions for correct recovery both in combinatorial terms and for some generative models including random labelings of lattices, Erdos-Renyi random graphs, and a random jigsaw puzzle model. Many open problems and conjectures are provided.
引用
收藏
页码：145 / 157
页数：13
相关论文
共 50 条
  • [1] Shotgun assembly of Erdos-Renyi random graphs
    Gaudio, Julia
    Mossel, Elchanan
    ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2022, 27
  • [2] Shotgun assembly threshold for lattice labeling model
    Jian Ding
    Haoyu Liu
    Probability Theory and Related Fields, 2023, 187 : 423 - 442
  • [3] Shotgun assembly threshold for lattice labeling model
    Ding, Jian
    Liu, Haoyu
    PROBABILITY THEORY AND RELATED FIELDS, 2023, 187 (1-2) : 423 - 442
  • [4] Shotgun Threshold for Sparse Erdos-Renyi Graphs
    Ding, Jian
    Jiang, Yiyang
    Ma, Heng
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2023, 69 (11) : 7373 - 7391
  • [5] Shotgun assembly of the mitochondrial genome from Fenneropenaeus penicillatus with phylogenetic consideration
    Zhang, Dianchang
    Gong, Fahui
    Liu, Tiantian
    Guo, Huayang
    Zhang, Nan
    Zhu, Kecheng
    Jiang, Shigui
    MARINE GENOMICS, 2015, 24 : 379 - 386
  • [6] Shotgun assembly of the first mitochondrial genome of Metapenaeus (Metapenaeus ensis) with phylogenetic consideration
    Zhang, Dianchang
    Liu, Tiantian
    Gong, Fahui
    Jiang, Shigui
    MITOCHONDRIAL DNA PART A, 2016, 27 (05) : 3689 - 3690
  • [7] TRAP: Tandem Repeat Assembly Program produces improved shotgun assemblies of repetitive sequences
    Tammi, MT
    Arner, E
    Andersson, B
    COMPUTER METHODS AND PROGRAMS IN BIOMEDICINE, 2003, 70 (01) : 47 - 59
  • [8] Self-assembly of geometric space from random graphs
    Kelly, Christy
    Trugenberger, Carlo A.
    Biancalana, Fabio
    CLASSICAL AND QUANTUM GRAVITY, 2019, 36 (12)
  • [9] On the hyperbolicity of random graphs
    Mitsche, Dieter
    Pralat, Pawel
    ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (02):
  • [10] On the diameter of Kronecker graphs
    Banaszak, Justyna
    Luczak, Tomasz
    DISCRETE MATHEMATICS, 2018, 341 (11) : 3165 - 3173
12345