Question

Exon chaining.Each gene corresponds to a subregion of the overall genome (the DNA sequence); however, part of this region might be “junk DNA.” Frequently, a gene consists of several pieces called exons, which are separated by junk fragments called introns. This complicates the process of identifying genes in a newly sequenced genome.

Suppose we have a new DNA sequence and we want to check whether a certain gene (a string) is present in it. Because we cannot hope that the gene will be a contiguous subsequence, we look for partial matches—fragments of the DNA that are also present in the gene (actually, even these partial matches will be approximate, not perfect). We then attempt to assemble these fragments.

Let x $\left[1Kn\right]$denote the DNA sequence. Each partial match can be represented by a triple $\left(l_i,r_i,w_i\right)$, where $x\left[l_{i}K{r}_i\right]$is the fragment and is a weight

representing the strength of the match (it might be a local alignment score or some other statistical quantity). Many of these potential matches could be false, so the goal is to find a subset of the triples that are consistent (nonoverlapping) and have a maximum total weight.

Show how to do this efficiently.

Short answer

Dynamic programming solves the problem in $O\left(n\right)$

Step-by-step solution

Step 1:Explain Exon Chaining

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.

Step 2:Give Algorithm

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

Explain the algorithm

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)