<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>

CC BY-SA 4.0
2021-07-16T06:10:13.280Z
Can you please explain what do you mean by "if two adjacent k-mers are connected in any read"?
Alex
CC BY-SA 4.0
2021-07-16T08:26:10.457Z
@Alex The explanation in this paper is quite good (if I do say so myself). https://academic.oup.com/bioinformatics/article/27/4/479/198367?login=true
Pseudonym
CC BY-SA 4.0
2021-07-08T03:41:23.213Z
2021-07-08T03:41:23.213Z
Pseudonym
<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>

CC BY-SA 4.0
2021-07-06T04:30:20.530Z
Can a read be used multiple times?
Throckmorton
CC BY-SA 4.0
2021-07-06T21:08:01.823Z
@Throckmorton You mean like a repeat? I think it cannot be used because there is no unique solution.
Alex
CC BY-SA 4.0
2021-07-06T21:15:58.713Z
Is there supposed to be a unique solution?
Throckmorton
CC BY-SA 4.0
2021-07-06T21:18:13.737Z
@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
CC BY-SA 4.0
2021-07-06T23:24:19.767Z
I would venture to guess there isn’t a unique solution, as in genome assembly there usually isn’t
Throckmorton
<algorithms><homework>
How to reconstruct a target string from a large set of overlapping reads
# How to reconstruct a target string from a large set of overlapping reads

(Asked by: username_0 on 2021-07-05)

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.

**Tags:** algorithms, homework
> **Comments:**
> **username_1**: Can a read be used multiple times?  
> **username_0**: @Throckmorton You mean like a repeat? I think it cannot be used because there is no unique solution.  
> **username_1**: Is there supposed to be a unique solution?  
> **username_0**: @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.  
> **username_1**: I would venture to guess there isn’t a unique solution, as in genome assembly there usually isn’t  

---

## 1 answers

### Answer by username_2 on 2021-07-08. Score: 2 | Accepted answer

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](https://en.wikipedia.org/wiki/K-mer).
* Construct a subgraph of the [De Bruijn graph](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Eulerian_path) 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*](https://www.pnas.org/content/98/17/9748).
* Zerbino and Birney, [*Velvet: Algorithms for de novo short read assembly using de Bruijn graphs*](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2336801/).
* Sohn and Nam, [*The present and future of de novo whole-genome assembly*](https://academic.oup.com/bib/article/19/1/23/2339783).

> **Comments:**
> **username_0**: Can you please explain what do you mean by "if two adjacent k-mers are connected in any read"?  
> **username_2**: @Alex The explanation in this paper is quite good (if I do say so myself). https://academic.oup.com/bioinformatics/article/27/4/479/198367?login=true  

---

