Motivation: In molecular biology, sequence alignment is a crucial tool in s
tudying the structure and function of molecules, as well as the evolution o
f species, In the segment-to-segment variation of the multiple alignment pr
oblem, the input can be seen as a set of non-gapped segment pairs (diagonal
s). Given a weight function that assigns a weight score to every possible d
iagonal, the goal is to choose a consistent set of diagonals of maximum wei
ght. We show that the segment-to-segment multiple alignment problem is equi
valent to a novel formulation of the Maximum Trace problem: the Generalized
Maximum Trace (GMT) problem. Solving this problem to optimality, therefore
, may improve upon the previous greedy strategies that are used for solving
the segment-to-segment multiple sequence alignment problem. We show that t
he GMT can be stated in terms of an integer linear program and then solve t
he integer linear program using methods from polyhedral combinatorics. This
leads to a branch-and-cut algorithm for segment-to-segment multiple sequen
ce alignment.
Results: We report on our first computational experiences with this novel m
ethod and show that the program is able to find optimal solutions for real-
world test examples.