... probabilities¹

To use any available TSP algorithm, we simply subtract the scores from a large number and then compute the shortest tour.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... already²

The gaps are scored according to the formula $a + l \times b$, where a is a fixed gap cost that depends on the PAM distance, l is the length of the gap and b is the incremental cost that also depends on the PAM distance [Benner et al., 1993]

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... equally³

The score will not be exactly equal to the probability, as in our scoring function, the probabilities of the pairwise alignments are independent, whereas in the exact case, the probabilities are dependent. We would have to know the internal nodes, which are generally not available.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.