##### Algorithms in Computational Biology

What is the wagner-fischer edit distance

Initialize 0 rows and columns with it's index

What is the recursive algorithm for longest common subsequence

Initialize 0s

What is the difference between the smith waterman and the needleman wunsch alignment algorithm?

Needleman is a global aliner, that is there are negative scores, and the best alignment starts in the lower right corner. Smith waterman is a local aligner, and the best alignment can start anywhere. Negative scores are zeroed out.

What is the recurrence relation for SmithWaterman

What is the recurrence relation for Needleman Wunsch

What is the time complexity for optimal multiple sequence alignment?

O(2^k k^2 n^k )

What is sequence complexity?

It defines how different a sequence is. Typically calculated by

1/4 * log4(N!/nA!nT!nC!nG!)

What is relative entropy

Relates two distributions to eachother

1sumk pk log2 pk/qk

What is liklihood in the context of motif finding

p(x|B) = mult(i) Pbi

p(x|M) = mult(i) Fmi

That is, probability of x given background is the product of each entry in the matrix, and the same for the Motif matrix

What is posterior probability

P(M|x) = P(x|M)P(M)/P(x|M)P(M) + P(x|B)P(B)

What is entropy

- SUM i Pi log2 Pi

How do you setup a suffix array

Start with the whole word, first letter at the top, to the suffix ($). Build a new edge for every subword in the sequence. if the subword is contained by a branch that already exists begin there.

What does the viterbi algorithm do?

The viterbi attempts to maximize the probability of the final state with a chosen set of hidden states pi*. It is greedy and faster than the other algorithms.

What does the forward algorithm do?

Sums over the probability of all states ending at K. Exhaustive and time prohibitive.