Stretches of G and C
A genome is read as a string of the letters A, C, G and T, and its letter composition changes in stretches: here more G and C, there more A and T. A model with two hidden states annotates each letter: state 0 is “rich in G and C here”, state 1 “rich in A and T here”. Each letter in each state brings its own score, the logarithm of how likely the letter is in such a stretch, and a change of state between neighbouring letters costs a penalty P.
Find the annotation with the highest score: the sum of the scores of all letters in their states minus P for each change. You may start in either state.
Most tests are the genomes of phages λ, HK97, HK022 and φX174 and of human mitochondria, with scores as in the article: a stretch with 58% G and C against one with 40%.
Input
The first line holds P (0 ≤ P ≤ 106). The second holds the scores of the letters A, C, G, T in state 0, the third in state 1 (integers, at most 1000 in absolute value). The fourth holds a string of the letters A, C, G, T from 1 to 2·105 long.
Output
On the first line, the highest score. On the second, the annotation: a string of zeros and ones, one character per letter. If there are several best annotations, output any.
Examples
Example 1
100 -25 21 21 -25 26 -32 -32 26 ATATTATAAGCGCGGCGCCGGATATAATTA
520 111111111000000000000111111111
Example 2
1000 -25 21 21 -25 26 -32 -32 26 ATATTATAAGCGCGGCGCCGGATATAATTA
84 111111111111111111111111111111
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
If changing state cost nothing, each letter could be given its best state separately. What does the penalty change? Try the second example: the same string, but a change costs 1000.
2Hint 2
Suppose you know the best score of an annotation of the first i letters that ends in state 0, and the same for state 1. How do you get the two numbers for i + 1 letters from these two?
3The idea
Denote by Vi(s) the best score of an annotation of the first i letters where letter i is in state s. The last step of such an annotation either stays in s or moves into it from the other state, paying P:
Vi(s) = score(s, letter i) + max(Vi−1(s), Vi−1(other) − P), V0 = 0.
The rest of the best annotation must be the best among annotations of the same beginning ending in the same state: otherwise it could be replaced and the whole improved. This is the Viterbi algorithm for two states. To recover the annotation itself, remember for each letter and each state where you came from, and walk back from the better of the two numbers at the end.
4Walkthrough
Two numbers per letter and two “where from” bits. In the first example the middle of the string has twelve G and C letters in a row: each brings 21 points in state 0 instead of −32, 636 points of difference for the stretch, while two switches cost 200, so switching pays. In the second example two switches cost 2000, and it is better to leave the whole string in state 1. On the genome of phage λ the best score is 38,498 with six stretches, as in the article’s listing.
4+Solution
5Complexity
O(n) time: two comparisons per letter. Memory is O(n) bits for the backtrack: two bits per letter suffice, 50 KB for 200 thousand letters. If only the score is needed, two numbers are enough.
6Common mistakes
- The best state for each letter separately. That is what you get when the penalty is ignored: an annotation with countless switches and a poor score. The second example catches this at once.
- Multiplying the scores. The scores are already logarithms: they are added. There is nothing to multiply.
- Recursion over letters. Python will not survive 2·105 nested calls; a loop will.
- A penalty at the start. The first letter may be in either state for free. If you insist on starting in state 0 or charge for “entering” state 1, the second example gives −198 instead of 84: the whole string in state 0.