<p>If the number of gaps is small, you can do the following brute force approach. Try <em>every possible</em> 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:
<a href="http://proceedings.mlr.press/v98/wolfer19a.html" rel="nofollow noreferrer">http://proceedings.mlr.press/v98/wolfer19a.html</a></p>

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

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

CC BY-SA 4.0
2019-09-20T07:40:51.163Z
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
CC BY-SA 4.0
2019-09-19T14:09:23.177Z
2019-09-19T14:09:23.177Z
Aryeh
<p>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 &quot;gaps&quot;, 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 .</p>
<p>Was this problem or a close variation of it solved ?</p>
<p>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.</p>
<p>I'm imagining the problem may have occurred in bioinformatics or communication theory.</p>

<ds.algorithms><pr.probability><lg.learning><markov-chains><bioinformatics>
Reconstruction of a sequence generated by a Markov chain - reference request
Popescu Claudiu
# Reconstruction of a sequence generated by a Markov chain - reference request

(Asked by: username_0 on 2019-09-17)

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.

**Tags:** ds.algorithms, pr.probability, lg.learning, markov-chains, bioinformatics

---

## 1 answers

### Answer by username_1 on 2019-09-19. Score: 2 | Accepted 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.

> **Comments:**
> **username_0**: 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).  

---

