91影视

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.

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

(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鈥�mers.$.

The vertex is connected to a vertex with a directed edge if the multiset contains such that $\left(k-1\right)鈥�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.