Articles in dynamic programing series

Sequence Alignment Revisited

2019/2/9
| algorithm
Problem1 Sequence Alignment We can reduce the space by using only two column instead. Space-Efficient-Alignment(X ,Y) Array B[0…m,0…1] Initialize B[i,0]=iδ for each i (just as in column 0 of A) For j=1,…,n B[0,1]=j$\delta$ (since this corresponds to entry A[0,j]) For i=1,…,m B[i, 1]= min[$\alpha x_iy_j$ + B[i − 1, 0], $\delta$ + B[i−1,1], $\delta$ + B[i,0]] Endfor Move column 1 of B to column 0 to make room for next iteration: Update B[i, 0]= B[i, 1] for each i Endfor However, this doesn’t left enough information to get back the information about alignment.……

Read More

Sequence Alignment

2019/2/9
| algorithm
Problem1 When you type “ocurrance”, the brower will will prompt “Perhaps you mean occurrence?” How does the search engine knows? How does it know the most similar word? How do we determine the similarity between words? The definition of similarity will be based on the optimal alignment between X and Y where X = $x_1x_2 … x_m$, Y = $y_1y_2 … y_n$. when there is gap (character not matched), we pay $\delta$ when we match character p and q, we pay $\alpha_{pq}$, where $\alpha_{pq}$ = 0 goal is to minimize the sum of cost.……

Read More

RNA Secondary Structure

2019/2/9
| algorithm
Problem1 We have bases of {A,C,G,T} in DNA sequence, where A-T and C-G form a pair. A sinlge strand of RNA will loop back, resulting shape called secondary structure. Let $B = b_1b_2 … b_n$, where $b_i$ = {A,C,G,U} also A-U, C-G form pair Then the Secondary structure, S ={(i, j)} no sharp turn, i < j - 4 pair is either {A,U}, {C,G} (either order) no base appear in more than 1 matching no crossing condition, (i,j) and (k, l) $\in$ S, we can’t have i < k < j < l Algorithm Following the same analysis……

Read More

Knapsack

2019/2/9
| algorithm
Problem1 Each request has value $v_i$ and weight $w_i$, and we have constraint that the total of request weight $\leq$ W. Greedy doesn’t work because sorting the W either in decreasing or increasing manner don’t produce the optimal solution. {W/2 + 1, W/2, W/2} {1, W/2, W/2} Using dynamic programing, we can use reduce this problem to whether or not each request belongs to the optimal solution O again.……

Read More

Segmented Least Square

2019/2/9
| algorithm
Problem1 Data $P = (x_1,y_1), (x_2, y_2)…(x_n, y_n)$ for $x_1 < x_2 < … < x_n$. Given a line y=ax+b, and error $$Error(L, P) = \sum_{i=1}^n(y_i - ax_i -b)^2$$ And it has closed form solution of $$a = \frac{n\sum_i x_iy_i - (\sum_i x_i)(\sum_i y_i)}{n\sum_i x_i^2 - (\sum_i x_i)^2}$$ and $$b = \frac {\sum_i y_i - a \sum_i x_i}{n}$$ However, if the data is show as below (maybe fitted with two lines), we can’t just use the above formula.……

Read More

Weighted Interval Scheduling

2019/2/8
| algorithm
Problem1 Instead of just fitting as many tasks like regular interval scheduling problem, we have weight associates with the interval. Now we want to maximize the value. So basically, $f_i$ finish time sorted in non-decreasing order, $v_i$ is the value, and $s_i$ is the start time. We want $S \subseteq {1… n}$. We also define $p(j)$ which is the largest i < j which is disjoint(compatible) with j. Algorithm Idea:……

Read More