text: user12692: 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.
  
  user9536: 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.
  
  Pevzner et al, An Eulerian path approach to DNA fragment assembly.
  Zerbino and Birney, Velvet: Algorithms for de novo short read assembly using de Bruijn graphs.
  Sohn and Nam, The present and future of de novo whole-genome assembly.
  
  
original_text: 12692: <p>I got this question as a homework. Does anyone know how the it can be solved?</p>
  <blockquote>
  <p>Consider a short string <span class="math-container">$r$</span> as a read from a string <span class="math-container">$S$</span> if <span class="math-container">$r$</span> is converted from a substring of <span class="math-container">$S$</span> by at most <span class="math-container">$k$</span> swaps at random locations, where a swap is an operation that switch two adjacent characters, i.e., string <span class="math-container">$s_1s_2...s_i s_{i+1}...s_n$</span> is one swap away from the string <span class="math-container">$s_1s_2...s_{i+1} s_{i}...s_n$</span>. Two reads are called overlapping if the substrings to which they are converted are overlapping. Given the input of <span class="math-container">$k &lt;&lt; |r|$</span>, devise an algorithm to reconstruct a target string <span class="math-container">$S$</span> from a large set of overlapping reads of <span class="math-container">$S$</span>.</p>
  </blockquote>
  <p>The question doesn't explicitly mention which of the possible superstrings of reads should be returned, so I think it's asking for <em>any</em> superstring.</p>
   9536: <p>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 <em>length</em>, which you can only do statistically.</p>
  <p>As you've correctly surmised, this is more or less the short-read <em>de novo</em> assembly problem, with one modification: the &quot;read errors&quot; are all swaps.</p>
  <p>The usual way that we solve this problem is:</p>
  <ul>
  <li>Pick a length (which is customarily called <span class="math-container">$k$</span> in bioinformatics, but the problem confusingly already used that, so we'll use <span class="math-container">$\kappa$</span> instead), and extract all <span class="math-container">$\kappa$</span>-length substrings of the reads. These substrings will, from here on, be referred to as <a href="https://en.wikipedia.org/wiki/K-mer" rel="nofollow noreferrer"><span class="math-container">$\kappa$</span>-mers</a>.</li>
  <li>Construct a subgraph of the <a href="https://en.wikipedia.org/wiki/De_Bruijn_graph" rel="nofollow noreferrer">De Bruijn graph</a>, where the <span class="math-container">$\kappa$</span>-mers are the nodes, and there is an edge between two nodes if two adjacent <span class="math-container">$\kappa$</span>-mers are connected in any read. Label the edges with the number of times this happens in all reads.</li>
  <li>Prune the graph of any edges that have low frequency. In your example, the kinds of errors are known, so you could in fact &quot;correct&quot; the pruned edges, or even correct the reads, based on the higher-consensus path.</li>
  <li>An <a href="https://en.wikipedia.org/wiki/Eulerian_path" rel="nofollow noreferrer">Eulerian superpath</a> through the graph corresponds to the desired string.</li>
  </ul>
  <p>I'm not saying that this is the best approach for your homework question, but this is how we do it in practice.</p>
  <p>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.</p>
  <ul>
  <li>Pevzner et al, <a href="https://www.pnas.org/content/98/17/9748" rel="nofollow noreferrer"><em>An Eulerian path approach to DNA fragment assembly</em></a>.</li>
  <li>Zerbino and Birney, <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2336801/" rel="nofollow noreferrer"><em>Velvet: Algorithms for de novo short read assembly using de Bruijn graphs</em></a>.</li>
  <li>Sohn and Nam, <a href="https://academic.oup.com/bib/article/19/1/23/2339783" rel="nofollow noreferrer"><em>The present and future of de novo whole-genome assembly</em></a>.</li>
  </ul>
  