Sequencer errors

dynamic programming similarity bioinformatics matrix

A sequencer has read a piece of a genome, but with errors: sometimes it confuses a letter, sometimes it inserts an extra one, sometimes it skips a real one. Each machine has its own character. One hardly ever loses letters but often confuses them; a nanopore sequencer, on the contrary, rarely confuses but easily skips. So the errors have different costs: a substitution costs S, inserting an extra letter I, skipping a letter of the reference D.

Given a reference, a piece of a known genome, and a read. Find the cheapest way to get the read from the reference by substitutions, insertions and skips, and write it as an alignment: the reference and the read one under the other, with hyphens in place of gaps. A column where a letter of the reference stands over a hyphen is a skip; a hyphen over a letter of the read is an insertion; two different letters are a substitution. There are no columns of two hyphens.

The references in the tests are pieces of the genomes of phages lambda and φX174 and of human mitochondria.

Input

The first line holds three integers S, I, D (1 ≤ S, I, D ≤ 100). The second holds the reference, the third the read: strings of the letters A, C, G, T of length 1 to 600.

Output

The first line holds the smallest cost. The second and third hold the alignment: the reference and the read of equal length with hyphens. If there are several cheapest alignments, print any.

Examples

Example 1

Input

1 1 1
GATTACA
GCATGCG

Output

4
GATTACA
GCATGCG

Example 2

Input

3 1 1
GATTACA
GCATGCG

Output

6
G-AT-TAC-A
GCATG--CG-

Limits

Time · Python: 4000 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 all errors cost 1, this would be the ordinary edit distance. What changes in the table when the costs differ?

2Hint 2

The subproblem is the same: the cheapest way to get the first j letters of the read from the first i letters of the reference. The last column of the alignment is a skip, an insertion or a pair of letters, and each variant has its own cost.

3Hint 3

Do not first look for the alignment with the fewest edits and then add up their costs. In the second sample a substitution costs 3, while a skip and an insertion together cost 2.

4The idea

D[i][j] = min(D[i − 1][j] + D, D[i][j − 1] + I, D[i − 1][j − 1] + (0 if the letters are equal, otherwise S)), with edges i · D and j · I. The proof is the same as in the article: in any alignment the last column is of one of three kinds, and the rest of the alignment must be the cheapest for its beginnings.

5Walkthrough

Fill the (n + 1) × (m + 1) table row by row, then go back from the bottom right corner: at each step find the neighbour from which the cell got its value, and write out a column of the alignment. Reverse what was written.

Look at the second sample. With costs 1, 1, 1 the cheapest alignment of GATTACA and GCATGCG costs 4 and consists of four substitutions. If a substitution costs 3, the same four substitutions would cost 12, while an alignment of three skips and three insertions costs 6: G-AT-TAC-A over GCATG--CG-, where G, A, T and C match. The shortest by number of edits and the cheapest are different alignments.

5+Solution

6Complexity

Time and memory O(n · m), 360,000 cells in the worst test. If only the cost is needed, two rows of the table are enough. For the alignment itself in linear memory there is Hirschberg's technique: the table is computed from both ends to the middle, the place where the path crosses the middle row is found, and the two halves are solved separately.

7Common mistakes

Edits first, costs afterwards. The alignment with the fewest edits may cost more than another: with an expensive substitution a skip and an insertion are better, with cheap insertions extra insertions instead of substitutions.
Insertion and skip mixed up. A step down the table (along the reference) is skipping a letter of the reference, a step right (along the read) is an insertion. On tests with I ≠ D this changes the answer.
Table edges with ones. The first row is j insertions, the first column i skips, each at its own cost, not i and j.

Algorithms behind it

STR Algorithm Edit distance The fewest insertions, deletions and substitutions between two strings: an m × n table and the alignment read from it. O(m · n) 2 problems