Efficient reconstruction of sequences from their subsequences of supersequences

DOI10.1006/jcta.2000.3081zbMath0992.68155OpenAlexW1969151232MaRDI QIDQ5930025

Vladimir I. Levenshtein

Publication date: 2 September 2002

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcta.2000.3081

zbMATH Keywords

reconstruction of words

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Graph theory (including graph drawing) in computer science (68R10)

Related Items (23)

Metric intersection problems in Cayley graphs and the Stirling recursion ⋮ Algorithms for subsequence combinatorics ⋮ On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length ⋮ On the Varshamov-Tenengolts construction on binary strings ⋮ Covering codes for the fixed length Levenshtein metric ⋮ Reconstruction of permutations distorted by single Kendall \(\tau\)-errors ⋮ Levenshtein graphs: resolvability, automorphisms \& determining sets ⋮ On DNA codes ⋮ Reconstruction of a word from a multiset of its factors ⋮ Optimal mean-based algorithms for trace reconstruction ⋮ Reconstruction of a graph from 2-vicinities of its vertices ⋮ On reconstruction of signed permutations distorted by reversal errors ⋮ Spectral concepts in genome informational analysis ⋮ DNA codes for nonadditive stem similarity ⋮ Global alignment of molecular sequences via ancestral state reconstruction ⋮ Efficient reconstruction of partitions ⋮ Subpolynomial trace reconstruction for random strings and arbitrary deletion probability ⋮ DNA Codes Based on Stem Similarities Between DNA Sequences ⋮ A universal bound for a covering in regular posets and its application to pool testing ⋮ Error graphs and the reconstruction of elements in groups ⋮ Reconstructing trees from traces ⋮ String Reconstruction from Substring Compositions ⋮ Reconstruction of a graph from 2–vicinities of its vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstruction of sequences
• On a reconstruction problem for sequences
• Reconstruction of objects from a minimum number of distorted patterns
• On a non-classical recognition problem
• Algorithms for the Longest Common Subsequence Problem
• Efficient reconstruction of sequences
• Some general results of coding theory with applications to the study of codes for the correction of synchronization errors

This page was built for publication: Efficient reconstruction of sequences from their subsequences of supersequences