## Coursera Week 1

###
Why is it called “dynamic programming”?

###
If dynamic programming is so powerful, then why don’t we transform all recursive algorithms into dynamic programming algorithms?

###
Is it possible to develop an iterative rather than recursive algorithm for OutputLCS?

IterativeOutputLCS(Backtrack, v, w)

###
Why do we favor vertical backtracking edges (over horizontal and diagonal) in OutputLCS?

###
If there are many topological orders, which one should I use for computing alignments?

## Coursera Week 2

###
Can you explain how to select penalties for insertions and deletions?

###
How do we know where the conserved region in a local alignment starts and ends?

###
How do biologists decide when to use global alignment and when to use local alignment?

###
Are there advantages of using global alignment instead of local alignment?

###
How do we backtrack when computing a local alignment?

We already know that (i’, j’) can be computed as a node such that the score si’, j’ is maximized over all nodes of the entire alignment graph. The question, then, is how to backtrack from this node and to find (i, j).

Recall the three backtracking choices from the OutputLCS pseudocode corresponding to the backtracking references ("↓", "→", and "↘"). To these, we will simply add one additional option, "FREE", which is used when we have used a free taxi ride from the source and will allow us to jump back to (0, 0) when backtracking. Thus, to find (i, j), one has to backtrack from (i’, j’) until we either reach a coordinate (i, j) with Backtracki, j = "FREE" or until we reach the source (0,0).

For simplicity, the following LocalAlignment pseudocode assumes that si, j = -∞ if i < 0 or j < 0.

###
Can you help me understand how to set up different alignment problems as an instance of the Longest Path in a DAG Problem?

###
If we have two newly sequenced proteins and don't know how different they are to begin with, how do we know which scoring matrix to use?

## Coursera Week 3

###
When building a Manhattan graph in three levels to perform affine sequence alignment, can’t we avoid building the three-level graph by using a two-level graph and keeping track of gap penalties each time we open a gap?

###
When building a Manhattan graph in three levels to perform affine sequence alignment, would it be more natural to connect (i, j)middle to the nodes (i, j)lower and (i, j)upper (instead of connecting them with (i+1, j)lower and (i, j+1)upper?

###
When building a Manhattan graph in three levels to perform affine sequence alignment, would it be more natural to connect (i, j)middle to the nodes (i, j)lower and (i, j)upper (instead of connecting them with (i+1, j)lower and (i, j+1)upper?

###
Why are there no edges connecting nodes in the upper level directly to the nodes in lower level in the three-level affine gap penalty alignment graph?

###
What topological order should we use to move in the three-level Manhattan graph for affine sequence alignment?

###
How can we backtrack in the three-level Manhattan for alignment with affine gap penalties?

###
How should we perform initialization for the Alignment with Affine Gap Penalties Problem?

###
In space-efficient sequence alignment, what should we do if there are multiple middle nodes?

###
Why did we switch from finding a middle node to finding a middle edge in space-efficient alignment?

###
Can I see an illustration of LinearSpaceAlignment?

###
Is it possible to develop a linear-space algorithm for alignment with affine gap penalties?

###
How would we align a nucleotide string of length n against a profile of length k, i.e., against a 4 x m matrix?

Every alignment of a string v against a profile Profile = (PX, j) (for X ∈ {A, C, G, T}, and 1 ≤ j ≤ m) can be represented as a path from (0,0) to (n, m) in the alignment graph. We can define scores of vertical and horizontal edges in this graph as before, i.e., by assigning penalties sigma to indels. There are various ways to assign scores to diagonal edges, e.g, a diagonal edge into a node (i, j) can be assigned a score Pvi, j. After the scores of all edges are specified, an optimal alignment between a string and a profile is computed as a longest path in the alignment graph.