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
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.