91影视

The DNA sequence or genome is written as$x\left[1Kn\right]$

Each partial matching given represents the starting and the weight of the match.

From these given sets of intervals, the maximum chain of intervals in required.

The greedy solution to this problem repeats the process of taking the chain with the highest scores first and then the largest left in the range until no more chains can be taken. Then sum the taken chains to get the maximum score.

But by constructing a graph, this problem can be solved in $O\left(n\right)$time complexity.

Algorithm is as follows,

With a graph $G\left(V,E\right)$, the algorithm is given as follows:

(G, n)

for i= 1 to 2n

$re{s}_i=0$

for i = 1 to 2n

if $v_i$in G corresponds to right end l

$j_i$left end index of vertex for l

$w_i$-weight

$re{s}_j=max\left\{\left(re{s}_j+w_i\right),\left(re{s}_{j-1}\right)\right\}$

else

$re{s}_i=re{s}_{i-1}$

return $re{s}_{2n}$

Explanation:

The Exon chaining problem can be solved using dynamic programming in a graph.

And that same approach is provided above.

The problem for n interval can be solved using 2nvertices in graph.

Assume that the set of left and right interval ends is sorted into ascending order.

And all positions are definite. This forms an ordered array of vertices.

There are 3n-1edges in the graph. In the algorithm, $re{s}_i$denotes the length of the longest path ending at vertex $v_i$ in the graph.

Therefore the final solution is $re{s}_{2n}$

Thus, dynamic programming solves the problem in O (n)