Motivation: The performance and time complexity of an improved version of t
he segment-to-segment approach to multiple sequence alignment is discussed.
In this approach, alignments are composed from gap-free segment pairs, and
the score of an alignment is defined as the sum of so-called weights of th
ese segment pairs.
Results: A modification of the weight function used in the original version
of the alignment program DIALIGN has two important advantages: it can be a
pplied to both globally and locally related sequence sets, and the running
time of the program is considerably improved The time complexity of the alg
orithm is discussed theoretically, and the program running time is reported
for various test examples.