MSA 2.0 (Multiple Sequence Alignment)

Alex Schaffer schaffer at
Sun Mar 19 00:51:45 EST 1995

I am pleased to announce the availability of MSA version 2.0, which is
an improved version of the MSA program to do multisequence alignment
under the sum-of-pairs cost criterion.  Version 2.0 is distributed by
Alejandro Schaffer (schaffer at Please contact him if you
have any problems with MSA 2.0.

MSA version 1.0 was written by J. Kececioglu, S. Altschul, D. Lipman,
and R. Miner and distributed in 1989, and it was briefly described in:

    1. D. Lipman, S. Altschul and J. Kececioglu, "A Tool for Multiple
Sequence Alignment", Proc. Natl. Acad. Sci. USA 86 (1989) 4412-4415.

MSA 2.0 is an improved version that uses substantially less space and
time. It was developed by S. K. Gupta and A. A. Schaffer,
with help from some notes by J. Kececioglu. It is described in:

    2. S. K. Gupta, J. Kececioglu, and A. A. Schaffer, "Making the
Shortest-Paths Approach to Sum-of-Pairs Multiple Sequence Alignment
More Space Efficient in Practice", (extended abstract) to appear in
Proc. 6th Annual Combinatorial Pattern Matching conference (CPM '95);
(full paper) submitted for publication.

Paper 2 describes the improvements and also includes a more detailed
explanation of the most important algorithm in MSA 1.0. A copy of
paper 2 is included as with the MSA 2.0 distribution.

Some other papers that helped develop the theory behind MSA are:

    3. Carrillo & Lipman, "The Multiple Sequence Alignment Problem in Biology",
		SIAM J. Appl. Math. 48 (1988) 1073-1082;
    4. Altschul & Lipman, "Trees, Stars, and Multiple Biological Sequence
		Alignment", SIAM J. Appl. Math. 49 (1989) 197-209;
    5. Altschul, "Gap Costs for Multiple Sequence Alignment",
		J. Theor. Biol. 138 (1989) 297-309;
    6. Altschul, Carroll & Lipman, "Weights for Data Related by a Tree",
		J. Molec. Biol. 207 (1989) 647-653;
    7. Altschul, "Leaf Pairs and Tree Dissections",
		SIAM J. Discrete Math. 2 (1989) 293-299;

MSA is designed to run under the UNIX operating
system, and generally requires several megabytes of memory.
The form that input to the program is required to take is
described in the accompanying manual page.

MSA is available by anonymous ftp from as follows:


login as anonymous
leave *full* e-mail address as password

     cd pub/msa

Retrieve either msa.tar.Z or all the other files in the directory.


If you retrived the files all together as msa.tar.Z, then run:

    uncompress msa.tar.Z
    tar xvf msa.tar

and this will pull the files apart and leave them in a subdirectory called

To make a compiled version of msa, run
     make msa

To try the program, run:

  msa SampleData.txt

If you wish to be kept apprised of all bug fixes and other updates,
please send e-mail to Alejandro Schaffer (schaffer at

More information about the Bio-soft mailing list