# Reconstruction of a sequence generated by a Markov chain - reference request

Let S be a finite sequence of symbols from a finite alphabet, with gaps - that is on some known locations an unknown number of symbols are missing. Assuming that the sequence , including the symbols in the "gaps", is generated by a Markov chain on the alphabet's symbols with an unknown transition matrix, the problem is to design an efficient algorithm that will fill (almost) correctly the gaps , with high probability . More formally , the output sequence must be close (in edit distance , for example) to one of the most probable sequences, given S and the model. The algorithm receive only the sequence S and must output a new sequence S' generated by filling the gaps in S .

Was this problem or a close variation of it solved ?

This seems to be an important and solvable problem, but I was not able to find any reference . I have some ideas on how to proceed , but I don't want to waste my time on some known result.

I'm imagining the problem can have occurred in bioinformatics or communication theory.

## 1 Answer

If the number of gaps is small, you can do the following brute force approach. Try every possible way of filling those gaps (there will be exponentially many possibilities, in the number of the gaps). For every "guess", fill in the gaps accordingly and train a maximum-likelihood Markov chain on the full sequence. You can even guarantee something about the convergence of the MLE estimator for MC's: http://proceedings.mlr.press/v98/wolfer19a.html

Having computed the maximum likelihood model -- together with its likelihood score -- pick the highest-scoring possibility of filling the gaps.

I don't know if there's an efficient (say, dynamic-programming-based) algorithm for doing this when the number of gaps is large.

• Thank you ! My idea was to learn the Markov chain using the sequence with gaps (whit the same algorithm from your paper , but ignoring the symbols near the gaps- this don't works in general , but if the total number of symbols in the gaps is sub-linear we can control the bias and it will vanish in the limit). For the sample bound I sketched only some naive analysis to bound the transition matrix error entry-wise using Chernoff , union bound and mixing time . This is worst than that from your paper - gives only a bound quadratic in d . – Popescu Claudiu Sep 20 at 7:40
• Finally , the reconstruction proceeds using MLE+DP and observing that the optimal fillings can not be larger than d . This seems to be efficient in m (if d is constant). – Popescu Claudiu Sep 20 at 7:40