Table 2 Two evaluation algebras for the Sankoff problem
SIGNATURE | PROB | SIM | ||
|---|---|---|---|---|
nil | \(=\) | 0 | 0 | |
NoStr (x, y) | \(=\) | x + y | x + y | |
Split (x, y) | \(=\) | x + y | x + y | |
Pair \((\langle a, b\rangle , x, \langle c, d\rangle )\) | \(=\) | x + \(\Psi (a, c)\) + \(\Psi (b, d)\) | x + \(\sigma (a,b)\) + \(\sigma (c,d)\) | (*) |
Ins \((\langle \epsilon , b\rangle )\) | \(=\) | 0 | \(\gamma (b)\) | |
Del \((\langle a, \epsilon \rangle )\) | \(=\) | 0 | \(\gamma (a)\) | |
Match \((\langle a, b \rangle )\) | \(=\) | 0 | \(\sigma (a,b)\) | |
\(\varphi\) | \(=\) | Max | Mx | |