Lemma 2.4 (Upper Bound)
Let
be the set of all possible MSAs that can be
generated for a given set of sequences
.
The maximal score
CS_{max}(
S) serves as an upper bound for the
score of any MSA
that can be built from S:
Proof 2.4
OPA scores are optimal. Therefore,
CS_{max}(
S), which is the sum
of OPA scores in circular order obtained by a TSP algorithm, is
also maximal.
Assume this last statement is wrong there exists
another score
that is higher than
CS_{max}(
S).
Since that score
is a sum of MPA scores, it would
follow that at least one of the MPA scores is higher than the
corresponding OPA score, which is a contradiction.