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.

  • $\begingroup$ Can a read be used multiple times? $\endgroup$ Commented Jul 6, 2021 at 4:30
  • $\begingroup$ @Throckmorton You mean like a repeat? I think it cannot be used because there is no unique solution. $\endgroup$
    – Alex
    Commented Jul 6, 2021 at 21:08
  • $\begingroup$ Is there supposed to be a unique solution? $\endgroup$ Commented Jul 6, 2021 at 21:15
  • $\begingroup$ @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. $\endgroup$
    – Alex
    Commented Jul 6, 2021 at 21:18
  • $\begingroup$ I would venture to guess there isn’t a unique solution, as in genome assembly there usually isn’t $\endgroup$ Commented Jul 6, 2021 at 23:24

1 Answer 1


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.

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

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.