This document contains two exercises related to bioinformatics algorithms. The first exercise asks the reader to apply the Hirschberg algorithm to compute the optimal global alignment of two sequences in linear space. It provides the sequences, scoring scheme, and asks the reader to trace back the alignment and describe the algorithm. The second exercise uses the Dinkelbach algorithm to find the subsequence of a vector with the best normalized local similarity. It provides definitions and asks the reader to analyze the effect of a parameter L on the optimal subsequence.
This document contains two exercises related to bioinformatics algorithms. The first exercise asks the reader to apply the Hirschberg algorithm to compute the optimal global alignment of two sequences in linear space. It provides the sequences, scoring scheme, and asks the reader to trace back the alignment and describe the algorithm. The second exercise uses the Dinkelbach algorithm to find the subsequence of a vector with the best normalized local similarity. It provides definitions and asks the reader to analyze the effect of a parameter L on the optimal subsequence.
This document contains two exercises related to bioinformatics algorithms. The first exercise asks the reader to apply the Hirschberg algorithm to compute the optimal global alignment of two sequences in linear space. It provides the sequences, scoring scheme, and asks the reader to trace back the alignment and describe the algorithm. The second exercise uses the Dinkelbach algorithm to find the subsequence of a vector with the best normalized local similarity. It provides definitions and asks the reader to analyze the effect of a parameter L on the optimal subsequence.
This document contains two exercises related to bioinformatics algorithms. The first exercise asks the reader to apply the Hirschberg algorithm to compute the optimal global alignment of two sequences in linear space. It provides the sequences, scoring scheme, and asks the reader to trace back the alignment and describe the algorithm. The second exercise uses the Dinkelbach algorithm to find the subsequence of a vector with the best normalized local similarity. It provides definitions and asks the reader to analyze the effect of a parameter L on the optimal subsequence.
at Freiburg Lehrstuhl f ur Bioinformatik Institut f ur Informatik
Prof. Dr. Rolf Backofen
Dr. Martin Mann Dr. Fabrizio Costa Omer Alkhnbashi Christina Schmiedl
http://www.bioinf.uni-freiburg.de
Bioinformatik 1 SS 2013
Exercise Sheet 4
Exercise 1 - Hirschberg Algorithm
The Hirschberg algorithm solves the global sequence alignment problem in linear space by employing a divide and conquer approach. The two sequences S1 and S2 and the cost function are given in Eq. 1. S1 = TCCGA S2 = TACGCGC
+1 if x = - y = - w(x, y) = 1 if x = y
0 else
(1)
a) Compute in linear space in which cell the traceback intersects row 3 of the dynamic programming matrix. b) Which parts of the dynamic programming matrix are considered in the next step of the Hirschberg algorithm? c) Show the pseudocode for computing the minimum cost of an alignment when we are only allowed to store one row and one variable.
Exercise 2 - Dinkelbach Algorithm
In this exercise we use the Dinkelbach Algorithm to find the subsequence of a vector x = x1 . . . xn of integers with the best normalized local similarity. The local similarity s(A) for a subsequence A = xi . . . xj of the vector x and the normalized similarity ns(A) are defined in Eq. 2 and 3, respectively. s(A) =
j X
xk
(2)
k=i
ns(A) =
s(A) with [[A]] = |xi . . . xj | [[A]] + L
(3)
a) Find a naive algorithm, i.e., without optimized runtime, to compute the subsequence of x with the best local normalized similarity by considering all subsequences.
b) The vector x=9 8 -1 -1 -1 7 8 10 is given. We study the effect of the parameter L on the result of the Dinkelbach Algorithm. Compute for L = 0, L = 5 and L = 10 the normalized local similarity for the subsequences x1 x2 , x1 . . . x8 and x6 . . . x8 . Which subsequences give the best normalized similarity for the different values of L? c) Can shadowing and the mosaic effect also occur in this setting?
