A few words about the proof
Theorems 1 and 2 were proved by reducing the MAX-CUT
problem for graphs to the multiple sequence alignment
problem. That is, given a simple graph G, a multiple
sequence alignment problem is constructed in such a way
that from a (nearly) optimal solution of the sequence
alignment problem a cut in the graph G of (nearly)
maximal size can be reconstructed in polynomial time.