Flashcards
Hamming Distance
Cards in this deck (11)
- 1What is the Hamming Distance Problem?For every alignment i, output Ham(i), the hamming distance between P and
T[i ... i+m-1] - 2By computing cross correlations to solve the hamming distance problem, what time and space complexity can we expect?O(n|sigma|logm) total time
O(n) space - 3Briefly explain how to solve the hamming distance problem using cross correlations
- 4Name a situation where the cross correlation method to solve the hamming distance problem is worse than the naive methodWhen the alphabet is longer than m
- 5For the O(n(rootm)logm) method, how many times must a symbol occur for it to be classed as frequent?root m
- 6How many frequent symbols can there be?root m at most
- 7Stage 1 involves counting the number of matches involving frequent symbols. What is the time complexity of this step?O(n(rootm)logm)
- 8Stage 1 involves counting the matches involving frequent symbols using cross correlations. How does this differ from stage 2, which involves counting the matches involving infrequent symbols?An array of length (n - m + 1) is constructed initially containing zeros. During a single pass of T, if T[k] is infrequent, for all j such that T[k] = P[j], increase A[k - j] by one, as long as k - j > 0. A[i] is the number of matches at alignment i involving an infrequent symbol.
- 9How quick is stage 2 of the O(n(rootm)logm) algorithm?O(n root m)
- 10How quickly can we classify each symbol as frequent or infrequent?O(mlogm)
- 11How can we improve the O(n(rootm)logm) algorithm to O(n (rootmlogm))?By changing the definition of frequent to be at least root(mlogm) occurrences.