An exact solution for the segment-to-segment multiple sequence alignment problem

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.