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 cs.rice.edu). 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 paper.ps 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 softlib.cs.rice.edu as follows:
login as anonymous
leave *full* e-mail address as password
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:
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
To try the program, run:
If you wish to be kept apprised of all bug fixes and other updates,
please send e-mail to Alejandro Schaffer (schaffer at cs.rice.edu).