Question

Sequencing by hybridization. One experimental procedure for identifying a new DNA sequence repeatedly probes it to determine which $\mathit{k}\mathbf{-}\mathit{m}\mathit{e}\mathit{r}\mathit{s}$(substrings of length ) it contains. Based on these, the full sequence must then be reconstructed.Let’s now formulate this as a combinatorial problem. For any string x (the DNA sequence), let $\mathit{\Gamma }\mathbf{\left(}\mathit{x}\mathbf{\right)}$denote the multiset of all of its localid="1658905204605" $\mathit{k}\mathbf{-}\mathit{m}\mathit{e}\mathit{r}\mathit{s}$. In particular, localid="1658904556515" $\mathit{\Gamma }\mathbf{\left(}\mathit{x}\mathbf{\right)}$contains exactly $\mathbf{\left|}\mathit{x}\mathbf{\right|}\mathbf{-}\mathit{k}\mathbf{+}\mathbf{1}$elements.The reconstruction problem is now easy to state: given a multiset of strings, find a string x such that $\mathit{\Gamma }\mathbf{\left(}\mathit{x}\mathbf{\right)}$is exactly this multiset.

$\left(a\right)$Show that the reconstruction problem reduces to RUDRATA PATH. (Hint: Construct a directed graph with one node for each localid="1658904858295" $\mathit{k}\mathbf{-}\mathit{m}\mathit{e}\mathit{r}\mathit{s}$, and with an edge from a to b if the last $\mathit{k}\mathbf{-}\mathbf{1}$characters of match the first localid="1658905395287" $\mathit{k}\mathbf{-}\mathbf{1}$characters of b.)

$\left(b\right)$But in fact, there is much better news. Show that the same problem also reduces to EULER PATH. (Hint: This time, use one directed edge for each $\mathit{k}\mathbf{-}\mathit{m}\mathit{e}\mathit{r}$.)

Short answer

$$\begin{gathered} a)TheSequencingbyHybridizationproblemcanbereducedtoHamiltonianPath. \\ b)TheSequencingbyHybridizationproblemcanbereducedtoEulerPath. \end{gathered}$$

Step-by-step solution

Explain the given information

Consider the information:

The objective is to prove that the reconstruction problem can be reduced to Hamiltonian Path.

The Hamiltonian path or Hamilton path is a path between the any two vertices of the graph that contains all the other vertices exactly once.

Reconstructing problem to RUDRATA PATH

(a)

Proof:

This reconstruction problem is reduced to a Hamiltonian Path using a directed graph construction. In a directed graph, each substring of length k or $k-mers$is represented as the vertices of the graph. In a multiset, if any$k-mers$appears more than once then they are represented using multiple vertices.

The edges in the directed graph are constructed such that for each edge$\left(a,b\right)$, $k-1$suffix of should be similar to$k-1$ prefix of b .

Therefore, the Sequencing by Hybridization problem can be reduced to Hamiltonian Path.

Reconstructing problem to EULER PATH

(b)

Consider the information:

The objective is to prove that the reconstruction problem can be reduced to Euler Path.

The Euler path of a graph contains all the edges of the graph exactly once but the vertices can be visited multiple times.

Proof:

The reduction of the reconstruction problem to the Euler path gives a linear-time algorithm for the problem. The idea of the reduction is to make the edges of the graph the substrings of length k . Then the path containing every edge only once can be found.

The vertices in this graph are the set of $k-1\hspace{0.33em}mers.$.

The vertex is connected to a vertex with a directed edge if the multiset contains such that $\left(k-1\right)\hspace{0.33em}mers.$suffix is same as and$k-1$ prefix is same as b .The parallel edges are used to represent therole="math" localid="1658905546336" $k-mers.$appearing more than once.

Therefore, the Sequencing by Hybridization problem can be reduced to Euler Path.