Multiple sequence alignment (MSA) is one of the most fundamental problems in
computational molecular biology. The running time of the best known scheme for finding an
optimal alignment, based on dynamic programming, increases exponentially with the
number of input sequences. Hence, many heuristics were suggested for the problem. We
consider a version of the MSA problem where the goal is to find an optimal alignment in
which matches are restricted to positions in predefined matching segments. We present …

Abstract Multiple Sequence Alignment (MSA) is one of the most fundamental problems in
computational molecular biology. The running time of the best known scheme for finding an
optimal alignment, based on dynamic programming, increases exponentially with the
number of input sequences. Hence, many heuristics were suggested for the problem. We
consider the following version of the MSA problem: In a preprocessing stage pairwise
alignments are found for every pair of sequences. The goal is to find an optimal alignment in …