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 may have occurred in bioinformatics or communication theory.


1 Answer 1


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.

  • $\begingroup$ 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). $\endgroup$ Sep 20, 2019 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.