The shared piece
The genomes of lambdoid phages are mosaics: a piece of one phage occurs in another almost unchanged, while next to it they have nothing in common. To find such a piece, one aligns not the whole genomes but their parts: locally.
You are given two pieces of DNA, s and t. Choose in each a stretch of consecutive letters and align them so that the score is the largest. A match of letters scores A points, a mismatch subtracts B, a gap of length k (a run of consecutive dashes in one row) subtracts O + E·k. Two runs of dashes back to back in different rows are two gaps. Empty stretches give a score of 0.
The tests hold pieces of the genomes of phages λ, HK97 and HK022: the genes of integrases, repressors, head, tail and cell-exit proteins.
Input
The first line holds the integers A, B, O, E (1 ≤ A ≤ 10, 0 ≤ B ≤ 20, 0 ≤ O ≤ 50, 1 ≤ E ≤ 20). The second and third hold s and t: strings of the letters A, C, G, T from 1 to 1000 long.
Output
The first line holds the largest score. If it equals 0, print nothing more. Otherwise the second line holds four numbers: the start and end of the stretch of s, the start and end of the stretch of t (positions from one, ends inclusive). The third and fourth hold the alignment of these stretches: two strings of equal length with dashes in place of gaps, without columns of two dashes. If there are several best answers, print any.
Examples
Example 1
3 3 0 2 TGTTACGG GGTTGACTA
13 2 6 2 7 GTT-AC GTTGAC
Example 2
2 3 5 2 ATGGAACAACGCATAACCCTGAAAGATTATGCAATGCGCT CCGTTATGGAACAACGCATAACCAAAGATTATGCAATGCGCTGACC
63 1 40 6 42 ATGGAACAACGCATAACCCTGAAAGATTATGCAATGCGCT ATGGAACAACGCATAACC---AAAGATTATGCAATGCGCT
Limits
- Time · Python
- 7000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 16 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 the stretches were known, this would be an end-to-end alignment, as in the problem “Gaps in one piece”. Trying all starts and ends is (n·m)2 pairs of stretches. What if the alignment were allowed to start at any cell of the table?
2Hint 2
In the formula for a column of two letters add the option “start here”: the pair’s score is added not only to the best of the three tables on the diagonal, but also to zero, the score of an empty alignment. If everything before the cell adds up to less than zero, it pays to discard it.
3Hint 3
The answer lies not in the corner but in the cell of table M with the largest value, wherever it is. The traceback runs from that cell and stops where the alignment started from zero.
4The idea
The best non-empty piece starts and ends with a pair of letters: a gap at an edge only subtracts points, since E ≥ 1, and without it the score is higher. So the tables suffice:
M(i, j) = w(si, tj) + max(0, M, X, Y at (i − 1, j − 1)),
where w is A or −B, and X and Y are the same as in end-to-end alignment, without the zero. M(i, j) is the best score of aligning some stretch of s ending in the letter si with some stretch of t ending in the letter tj, if the last column is this pair. The proof is the same as for whole strings: remove the last column; the rest is either empty (that is the zero) or ends at cell (i − 1, j − 1) in one of three kinds and must be the best of its kind. The answer is max(0, the largest M(i, j)).
5Walkthrough
Fill the three tables and remember the cell with the largest M. The traceback is as in end-to-end alignment, but in table M check: if zero remains without the pair’s score, the piece started here. The cell where we stopped, plus one, gives the starts of the stretches; the cell with the maximum gives their ends.
The first example is a classic: with a match of 3, a mismatch of −3 and a gap of 2 per letter, the best piece is GTT-AC over GTTGAC: five matches of 3 minus one gap. In the second there is the start of phage λ’s cro gene and the same piece without one codon among foreign letters: 37 matches of 2 minus a three-letter gap of 5 + 3·2 = 11, 63 in all.
The real tests show the mosaic from the article. The integrase and excisionase genes of λ and HK97 give a piece 994 letters long scoring 942, almost without differences. The repressor genes of λ and HK022 give 12, while two random strings of a thousand letters at the same prices give 8 to 11: these genes are not in each other. The genes of tail protein J are related at the protein level, 31% identical amino acids, but in DNA the best piece is 39 letters scoring 38 against 19–25 for random strings. Distant kinship shows in proteins and hardly shows in genes: one amino acid is encoded by different codons, and over a long time DNA letters diverge further.
5+Solution
6Complexity
Time and memory are O(n·m): three tables of a million cells in the worst test. If only the score and the end of the piece are needed, two rows of each table are enough; the start of the piece can be found by a second pass, the same computation on the reversed strings starting from the end found.
7Common mistakes
- The answer in the corner or on the edge. If you look for the maximum only in the last row and last column, you find pieces that reach the end of a string, while an island in the middle of both is lost. The first example already fails this way.
- A traceback to the edge of the table. If you do not stop at zero, a start with a negative score sticks to the piece: the piece named scores less than the score printed.
- Zero without a penalty in X and Y. Starting a piece with a gap does not pay, and no zero is needed there. And if you write max(…, 0) right in the gap formula, gaps become free.
- An empty answer. If there are no common letters, the best score is 0, and only it is printed.
- Positions from zero. The boundaries of the stretches in the answer count from one, ends inclusive.