Efficient reconstruction of sequences from their subsequences of supersequences
Let \(X\) be a sequence of length \(n\) of elements of a \(q\)-element set. The following two questions are considered: (1) Given \(N_1\) subsequences of \(X\) of length \(n-t\), is it possible to reconstruct \(X\)? (2) Given \(N_2\) supersequences of \(X\) of length \(n+t\), is it possible to reconstruct \(X\)? Clearly, positive answers to these questions are only possible if \(N_1\) and \(N_2\) are large enough. If \(n,q,t\) are fixed, what are the minimum possible numbers for \(N_1\) and \(N_2\), respectively, such that the reconstruction problem has a positive answer? These numbers are explicitly determined in this paper. Quite obviously, to find these numbers required a lot of imagination. For question (1) the answer is recursive, while for question (2) an explicit formula in terms of a binomial sum is given. Moreover, for both cases an algorithm is provided that solves the reconstruction problem. This is part of a theory developed in another paper of the author [IEEE Trans. Inform. Theory 47, 2-22 (2001)]. NEWLINENEWLINENEWLINEReviewer's remark: The author overlooks that it is also easy to provide an explicit formula for the desired number for question~(1). To be precise, if in Eq.~(16) the geometric series on the left-hand side are summed and subsequently the binomial theorem is applied to the powers of \((1-z^q)\) and \((1-z)\), respectively, then the formula NEWLINE\[NEWLINED_q(n,t)=\sum _{k=0} ^{\lfloor t/q\rfloor}(-1)^k\binom {n-t}k\binom {n-qk}{n-t}NEWLINE\]NEWLINE is obtained on comparing coefficients of powers of \(z\) on both sides. If this is substituted in Eq.~(28), the desired explicit formula results.
- Algorithms for the Longest Common Subsequence Problem
- Efficient reconstruction of sequences
- scientific article; zbMATH DE number 2185636 (Why is no real title available?)
- scientific article; zbMATH DE number 4211968 (Why is no real title available?)
- scientific article; zbMATH DE number 5242374 (Why is no real title available?)
- scientific article; zbMATH DE number 3240929 (Why is no real title available?)
- On a non-classical recognition problem
- On a reconstruction problem for sequences
- Reconstruction of objects from a minimum number of distorted patterns
- Reconstruction of sequences
- Some general results of coding theory with applications to the study of codes for the correction of synchronization errors
- Error graphs and the reconstruction of elements in groups
- Reconstruction of sequences
- On a reconstruction problem for sequences
- Reconstructing sequences
- 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
- Self-matched Patterns, Golomb Rulers, and Sequence Reconstruction
- Reconstructing numbers from pairwise function values
- scientific article; zbMATH DE number 1189007 (Why is no real title available?)
- On the Varshamov-Tenengolts construction on binary strings
- scientific article; zbMATH DE number 1156634 (Why is no real title available?)
- scientific article; zbMATH DE number 1498818 (Why is no real title available?)
- Efficient reconstruction of sequences
- DNA Codes Based on Stem Similarities Between DNA Sequences
- String reconstruction from substring compositions
- Covering codes for the fixed length Levenshtein metric
- Reconstruction of permutations distorted by single Kendall -errors
- Balanced reconstruction codes for single edits
- Reconstruction of hypermatrices from subhypermatrices
- The sequence reconstruction problem for permutations with the Hamming distance
- Sequence reconstruction problem for deletion channels: a complete asymptotic solution
- Improvements on permutation reconstruction from minors
- Trace reconstruction from local statistical queries
- Polynomial-time trace reconstruction in the smoothed complexity model
- Levenshtein's sequence reconstruction problem and results for larger alphabet sizes
- The sequence reconstruction of permutations with Hamming metric
- Global alignment of molecular sequences via ancestral state reconstruction
- Circular trace reconstruction
- Polynomial-time trace reconstruction in the low deletion rate regime
- Reconstructing graphs with subgraph compositions
- On the decoding error weight of one or two deletion channels
- Near-optimal trace reconstruction for mildly separated strings
- The sequence reconstruction of permutations under Hamming metric with small errors
- Reconstruction of a word from a multiset of its factors
- Reconstruction of a graph from 2-vicinities of its vertices
This page was built for publication: Efficient reconstruction of sequences from their subsequences of supersequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5930025)
