Efficient reconstruction of sequences from their subsequences of supersequences

DOI10.1006/jcta.2000.3081zbMath0992.68155MaRDI 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

05A15: Exact enumeration problems, generating functions

68R10: Graph theory (including graph drawing) in computer science

Related Items

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