Algorithms in Computational Biology

Helpfulness: 0
Set Details Share
created 8 years ago by yetipirate
41 views
updated 8 years ago by yetipirate
Grade levels:
Graduate school
show moreless
Page to share:
Embed this setcancel
COPY
code changes based on your size selection
Size:
X
Show:
1

What is the wagner-fischer edit distance

card image

Initialize 0 rows and columns with it's index

2

What is the recursive algorithm for longest common subsequence

card image

Initialize 0s

3

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.

4

What is the recurrence relation for SmithWaterman

card image
5

What is the recurrence relation for Needleman Wunsch

card image
6

What is the time complexity for optimal multiple sequence alignment?

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

7

What is sequence complexity?

It defines how different a sequence is. Typically calculated by

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

8

What is relative entropy

Relates two distributions to eachother

1sumk pk log2 pk/qk

9

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

10

What is posterior probability

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

11

What is entropy

- SUM i Pi log2 Pi

12

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.

13

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.

14

What does the forward algorithm do?

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