# How to reconstruct a target string from a large set of overlapping reads

I got this question as a homework. Does anyone know how the it can be solved?

Consider a short string $$r$$ as a read from a string $$S$$ if $$r$$ is converted from a substring of $$S$$ by at most $$k$$ swaps at random locations, where a swap is an operation that switch two adjacent characters, i.e., string $$s_1s_2...s_i s_{i+1}...s_n$$ is one swap away from the string $$s_1s_2...s_{i+1} s_{i}...s_n$$. Two reads are called overlapping if the substrings to which they are converted are overlapping. Given the input of $$k << |r|$$, devise an algorithm to reconstruct a target string $$S$$ from a large set of overlapping reads of $$S$$.

The question doesn't explicitly mention which of the possible superstrings of reads should be returned, so I think it's asking for any superstring.

• Can a read be used multiple times? Jul 6 at 4:30
• @Throckmorton You mean like a repeat? I think it cannot be used because there is no unique solution.
– Alex
Jul 6 at 21:08
• Is there supposed to be a unique solution? Jul 6 at 21:15
• @Throckmorton Hmm.. I think there can be multiple solutions as well. I mean given the fact that the number of reads are large it may conclude that there might be a unique solution.
– Alex
Jul 6 at 21:18
• I would venture to guess there isn’t a unique solution, as in genome assembly there usually isn’t Jul 6 at 23:24

Unless it's not obvious, the problem has no unique solution. An obvious example is a string which uses entirely one character; the problem is then to determine its length, which you can only do statistically.

As you've correctly surmised, this is more or less the short-read de novo assembly problem, with one modification: the "read errors" are all swaps.

The usual way that we solve this problem is:

• Pick a length (which is customarily called $$k$$ in bioinformatics, but the problem confusingly already used that, so we'll use $$\kappa$$ instead), and extract all $$\kappa$$-length substrings of the reads. These substrings will, from here on, be referred to as $$\kappa$$-mers.
• Construct a subgraph of the De Bruijn graph, where the $$\kappa$$-mers are the nodes, and there is an edge between two nodes if two adjacent $$\kappa$$-mers are connected in any read. Label the edges with the number of times this happens in all reads.
• Prune the graph of any edges that have low frequency. In your example, the kinds of errors are known, so you could in fact "correct" the pruned edges, or even correct the reads, based on the higher-consensus path.
• An Eulerian superpath through the graph corresponds to the desired string.

I'm not saying that this is the best approach for your homework question, but this is how we do it in practice.

To understand the method in depth, here are some suitable references. Some of these are tool papers, and others explain the data structures and algorithms well.

• Can you please explain what do you mean by "if two adjacent k-mers are connected in any read"?
– Alex
Jul 16 at 6:10
• @Alex The explanation in this paper is quite good (if I do say so myself). academic.oup.com/bioinformatics/article/27/4/479/… Jul 16 at 8:26