Consider a voice recording split into it's phonemes as our sample $S=(s_1,...,s_k) \in \Omega = P^k$. The number of phonemes is $|P| = 40$. Then I have a word $w = (w_1,...,w_n) \in P^n$. I want to analyze with what chance I can reconstruct $w$ by just cutting out parts of the sample and chaining them together in the right order. I assume that $p(s_i=p) = x_p$ for $i=1,..,n$ and $p \in P$, i.e. that each sample symbol $s_i$ is chosen independently from the others and the distribution of the phonemes is given by $x_j$.

First, I wanted to know what the probability is that one can reconstruct a word "in principle" by taking single phonemes from the sample and chaining them in the right order. One can easily calculate this by naively iterating through all possible samples. This is obviously not feasable for larger k. Instead, I take the set $X = \{w_i : 1 \leq i \leq n\}$ of all required phonemes. Let $R_A^k$ be all the samples of length k where all phonemes in $A \subseteq X$ are contained in the sample (i.e. $A$ is reconstructable). Note that $p(S \in R_X^k)$ is my answer. The states $Q=\{R_A : A \subseteq X\}$ form a Bayesian Network where the transitions represent going from $k$ to $k+1$. For instance, if one is in state $R_A$ one ends up in $R_{A \cup \{p\}}$ with probability $x_p$ for $p \in X \setminus A$. Now I can iteratively calculate the probability of $w$ being reconstructable in $O(k \cdot 2^{|X|})$ and this suffices for my data (in one dataset, the biggest $n$ is $10$).

Now, I want to know the probability for reconstructing the word using $c$ substrings in $S$. For instance, if I want to reconstruct the word $w=$ACEG and I have the sample $S=$CEGBAF then I can reconstruct $w$ as A+CEG using 2 substrings. I try to group all samples into relevant states so that I can iteratively compute over k like before. My idea is to save the longest available substring in each position of w, as well as the start position and length of the longest streak in S (the largest substring at the end of $S$ that is in $w$), so $q=((q_1,...,q_n),a,l)$.

For example: $w=$ABCDE and the state $q=((2,1,2,1,0),3,1)$. This means we gathered two substrings "AB" and "CD", the last streak in S was "C".

Naively there are $n! \cdot \frac{n \cdot (n+1)}{2}$ such states. One can cut down this number by observing constraints in $q$: $(a=0 \wedge l=0) \vee (0 \lt l \leq q_a \lt n-a)$)

I implemented this in python (Note that string indexing starts at zero here):

import itertools

def enum_states(n):
    states = [(i,) for i in xrange(0,n+1)]
    for i in xrange(n-1):
        states = [q + (x,) for q in states for x in xrange(max(0, q[-1]-1), n - i)]
    states = [(q, a, l) for q in states for a in xrange(0, n) for l in xrange(0, n-a+1) if (a==0 and l==0) or (l > 0 and l <= q[a] and q[a] < n-a)]
    return states
def print_states(states):
    i = 0
    for q in states:
        tup = q[0]
        a = q[1]
        l = q[2]
        tup = [str(e) for e in tup]
        if l == 0:
            print ''.join(tup) + "  ",
            print ''.join(tup[:a]) + "<" + ''.join(tup[a:a+l]) + ">" + ''.join(tup[a+l:]),
        i += 1
        if i%8 == 0:

states = enum_states(10)
print len(states)

For $n=10$ there are $|Q|=978926$ states! My original goal was to compute the transition matrix from the bayesian network. There are at most $(n+1)$ transitions from each state (one for each phoneme in $w$ and one for all phonemes not in $w$). The transition matrix $M$ would therefore be very sparse and could be stored efficiently in a CSR Matrix. However iterating over k going one step at a time would be too slow for large k. Instead one can calculate $M^k$ using fast exponentiation. But the resulting matrix would not be sparse any more and just be too big to work with.

I hope I could articulate my problem clearly. To sum up: How can I compute the probability of a word being reconstructable using $c$ substrings from a sample of length $k$ efficiently? Am I missing something? Maybe there's a smarter way of doing this.

  • $\begingroup$ Hi, I try to understand your question. You said that X={w_i:1≤i≤n} is set of all phonemes, but w_i - is word. Everything is ok here ? $\endgroup$ – vadikrobot Aug 16 '17 at 7:22

I don't know the answer to your question, but there is almost certainly a large amount of literature on it in the computational biology community. This is because your problem is in essence how genomes are reconstructed: genome sequencers break the many copies of the same DNA (which is a string consisting of 4 letters) into small pieces at essentially random locations (i.e., you get many many substrings that will partially overlap), and can then read these substrings. The goal of "sequence assembly" is then to recover the long string from the many substrings that, hopefully, cover the long string many times over.

So this is the community (and associated literature) I would start to look into to get your question answered.

  • $\begingroup$ Thank you for your suggestion. To be honest I couldn't find anything related to my problem (maybe I overlooked something?). The sequencing algorithms that I found don't deal with probability and were not applicable. The exact problem definition is crucial as "recovering the original string" and "estimated number of substrings needed to recover a different string" are two separate problems. $\endgroup$ – user1841833 Apr 23 '16 at 21:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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