Subsequence problem

Scoring subsequences or lengths of similar matches or runs is common to a variety of problems from matches in genetic codes to similar runs in bits.

Consider the following question about two sequences of letters. Set both sequences to have length \(k\). At each location of the sequences the probability of a match in letters is \(.7\) and the probability of a mismatch is \(.3\). At each location a match is assigned a score of \(4\) and a mismatch is assigned a score of \(-1\). The total score of the sequence is the sum of the scores at each location, there are \(k\) locations.

Answer the following:

  1. What is the PMF of the total score if \(k=5\).
  2. What is the PMF of the total score for a general \(k\) ?


Leave a Reply

Your email address will not be published. Required fields are marked *