Multalin documentation
                                     ======================
                                        ( version 5.0, 5.1, 5.2 )



 Introduction
 ------------

        Welcome to Multalin! This is a software that will allow you to align
simultaneously several biological sequences on computer which use UNIX system.

        What is a Multiple sequence alignment? It is the arrangement of several
protein or nucleic acid sequences with postulated gaps so that similar
residues are juxtaposed. A score is attached to identities, conservative or
non-conservative substitutions (the score measuring the similarity) and a
penalty to gaps; an ideal program would maximize the total score, taking
account of all possible alignments and allowing for any length gap at any
position.

        Unfortunately the computing requirements, both of time and memory, grow
as the nth power, where n is the sequence number, so this ideal alignment can
be found only for two sequences or three short sequences. In the general case,
to be practicable programs must restrict the conditions of the optimization.
Nevertheless it is undeniably useful to have an automatic system available for
multiple sequence alignment to provide a starting point for a more human
analysis.

        Multalin creates a multiple sequence alignment from a group of related
sequences using progressive pairwise alignments. The method used is described
in "Multiple sequence alignment with hierarchical clustering", F.Corpet, 
1988, Nucl. Acids Res. 16 10881-10890.

  NEW in version 5.0
  ------------------
	Comparison tables can include negative entries. GCG tables can be used.
	Gap penalty can be length dependent. Gap at sequence extremities can be
scored or not.

  NEW in version 5.1
  ------------------
	There is a maximal number of iterations set to 10 (see F. Iteration).
	A bug has been fixed that prohibited the comparison of two sequences only.
	SCO and sco, CLU and clu are now valid extensions for score files and 
clustering files.
	Portability has been tested for more platforms.

  NEW in version 5.2
  ------------------
	The similarity coefficient at a position is still the mean of all pairwise 
coefficients at this position, BUT only the sequences for which the position is 
internal are counted. Example:
              CCPC50  QDG DAAKGEKEFN .KCKACHMI QAPDGTDII. KGGKTGPNLY
              CCRF2C  ..G DAAKGEKEFN .KCKTCHSI IAPDGTEIV. KGAKTGPNLY
              CCRF2S  QEG DPEAGAKAFN .QCQTCHVI VDDSGTTIAG RNAKTGPNLY
              CCQF2R  .EG DAAAGEKVSK .KCLACHTF DQGGAN.... ...KVGPNLF
              CCQF2P  .AG DAAVGEKIAK AKCTACHDL NKGGPI.... ...KVGPPLF
                      |
Multalin sequence #   245 5555555555 555555555 5555555555 5555555555
Clustalv sequence #   245 5555555555 155555555 5555553331 3335555555

	I think that it is important to take the mean over all sequences for new 
gaps to be preferentially inserted at the same position as old gaps. But this is 
a problem when sequence lengths are inhomogenous, so I have made this modification.

 Cautions
 --------      
        Before aligning large sequences, you may test Multalin with shorter
sequences, and look at the system occupation ( see 'ps' UNIX command ) during
alignment. When the swap partition of the hard disk is full, Multalin can use
an internal swap mode on user partition.



 Portability
 -----------           
        The file "portab.h" contains preprocessor commands which allow to
compile and run program on different computers and operating systems.



 Compilation
 ----------- 
        Source files:
        afichseq.c            aligne.c              basproc1.c            cluster.c
        coefdisk.c            commande.c            copright.c            disk.c
        drivers.c             fast.c                gcgdisk.c             lstfseq.c
        ma.c                  maglob.c              mbgbdisk.c            msfdisk.c
        msgerr.c              muldisk.c             parametr.c            portab.c
	swapd.c               util.c

 To create 'ma' program in UNIX environment:

        1/ Compile these files to obtain object files:
                cc -<ansi_option> -c <filename.c>

        2/ Build the executable file 'ma' by linking all objects files:
cc -<ansi_option> afichseq.o aligne.o basproc1.o cluster.o coefdisk.c
commande.o copright.o disk.o drivers.o fast.o gcgdisk.o lstfseq.o ma.o
maglob.o mbgbdisk.o msfdisk.o msgerr.o muldisk.o parametr.o portab.o swapd.o
util.o -o ma 

where <ansi_option> is the option which allows compilation according to the
ANSI C directives (1988).

 Installation
 ------------
 Two possibilities:
 1       Copy 'ma', 'ma.MSG' and symbol comparison tables (files '.tab') into the
same directory. If you run ma from another directory, use its full name (do not
use the PATH).

 2	Copy 'ma.MSG' and the *.tab files into the same directory and set the
environment variable MULTALIN to its name, e.g.:
DOS: set MULTALIN=C:\MULTALIN.DIR\
Unix : setenv MULTALIN /usr/Multalin/
	Copy 'ma' into a directory that is included in the PATH.



                        ________________________________
                       |                                |
                       |        Running Multalin        |
                       |________________________________|



You can run Multalin in two modes:

* command line mode.

* interactive mode which helps you to select program parameters and options.





Help: type 'ma -h' or 'ma -?' to obtain help screen.



1/ Command line mode
=====================

Syntax:                ma [[<Option> ...] <SequencesFile> [<ClusterFile.xxx>]]

<SequencesFile> contains several sequences, or several sequences filenames
(depending of sequence input format,see Appendix B).

<ClusterFile.clu> contains cluster obtained by previous FAST alignment (or by
any other method) of the same sequences. The file format used is the same that 
MultAlin MS-DOS version.

<ClusterFile.sco> contains a triangular table of alignment scores for any pair
of sequences included in SequencesFile. These scores are used by Multalin to
compute a first clustering (instead of using Fast).

if no ClusterFile is given, the first clustering is done with Fast (Lipman &
al algorithm).



Options are:

        -r                     Recover last configuration.

        -i:<Input format>       with Format:  gcg, embl, genbank,
                                             mul (MultAlin),
                                             auto (determined automatically).

        -p                     select Parts of sequences.

        -o:<Output format>      with Format:  msf (GCG) or mul (MultAlin).

        -c:<symbol Comparison table>
        -g:<Gap value>
        -l:<Gap length value>
        -x:<Gap at ext>       0 no penalties, 1 penalty at the end
                              2 penalty at the beginning, 3 at both extremities

        -1                     One iteration only

        -q                     quiet : no message during alignment

 Default options are:    -i:gcg -o:msf -c:dayhoff.tab -g:5 -l:0 -x:0



 Recover option (-r)
 -------------------- 
        Multalin always saves configuration parameters, used for the last
alignment: 
        - input format ( gcg, mul, embl, genbank or undefined ).
        - output format ( msf, mul ).
        - clustering output format (list, drawing).
        - name of the symbol comparison table file. 
        - penalty for gap opening and extension.
        - penalty for end gaps.
        - consensus levels.
        - one iteration only ( true, false ).

        This information is saved in a text file 'ma.cfg'. If you want to edit
yourself this file, you have to use the same key-words.

 Sequence input format (-i)
 --------------------------- 
        Multalin automatically recognizes four formats (GCG, Multalin, GenBank,
EMBL). However, if error message appears, you have to specify input formats
or correct sequence syntax ( see Files formats in this manual ).

 Select parts of sequences option (-p)
 -------------------------------------- 
        If you use this option, the program will pause when reading sequences
file(s), and ask you the sequence range to use for alignment.

 Sequence output format(-o)
 --------------------------- 
        You can save alignment result in two formats: MSF(default) or Multalin.
In both formats, sequences are saved in only one file. If Multalin format is
chosen, a consensus sequence is saved in an other file with extension .con

 Comparison symbol table file (-c)
 ---------------------------------- 
        You can use Multalin tables (.tab), or GCG package tables (.cmp).
Multalin tests the file name for the .cmp extension to know the file format.
If the file is not present in the current file, it is looked for in MULTALIN
directory (see Installation 2).
Both kinds of tables contains semi-matrix of coefficients, but Multalin  
tables may also contain: 
        gap value ( first number after coefficients )
        homology symbols used in the consensus sequence. ( See "dayhoff.tab"
file for example ).

        ATTENTION : GCG tables give non-integer values : Multalin multiplies GCG
values by 10 to use integer values. Gap penalties must also be multiplied by
10. For example, if you use "nwsgappep.cmp" with a gap value of 5 and a gap
length weight of 0.1 in GCG programs, you must use it with a gap value of 50
and a gap length weight of 1 in Multalin.

 Gap value (-g) 
 --------------- 
 Gap length weight (-l)
 ----------------------
        The score of an alignment is equal to the sum of the values of the
matches, each one scored with the comparison table, less the gap value times
the number of internal gaps and less the gap length weight times the total
length of the internal gaps. There is no penalty for end gaps unless the
option -x is set to a non-0 value.
        Default values are -g:5 -l:0

 Gap at extremities (-x)
 -----------------------
        With this option, it is possible to weigh end gaps as all other gaps : 
-x:1 a gap at the end is weighted
-x:2 a gap at the beginning is weighted
-x:3 both end gaps are weighted
-x:0 end gaps are not weighted (default).

 One iteration only option (-1)
 ------------------------------- 
        With this option, final alignment can be obtained more quickly, but it
may not be the best possible alignment.

 Quiet (-q)
 ----------
        With this option, no messages are displayed to the screen.

 2/ Interactive mode
 ====================

        - type 'ma' without any option and answer the questions : they
correspond to the options that can be set with the command line mode, plus
other options :

 Clustering order output format
 ------------------------------
        When Multalin calculates the first clustering order (with Fast or from
a score table), it is saved in a file with .clu extension. The clustering
order used for the last iteration is saved in a file with .cl2 extension.
        By default, these files format is a list of the sequence names with
parentheses indicating how the clustering is done. In this case the files can
be used as input cluster file for an other alignment.
        The clustering order can also be saved as a dendrogram. The drawing uses
text characters and can be printed to any printer or screen.
        Answer l(ist) for the first format (default) and d(rawing) for the
other.

 Consensus levels
 ----------------
        Multalin generates a consensus sequence in which each character is a
function of the other characters in the same column. If one letter in the
column is present in more than 90% of the sequences, the consensus character
is the upper case equivalent of that letter. If not but a letter is present
in more than 50% of the sequences, the consensus character is the lower case
equivalent of that letter. If not, the consensus character is a blank.
        You can change the consensus levels (90 and 50) by answering this
question with other values.



                        _______________________
                       |                       |
                       |       Algorithm       |
                       |_______________________|



        The alignment of two sequences can be performed with any program that
has been developed since 1970. However, a rigorously optimal alignment of even
a small number of short sequences is currently intractable because of the
amount of time and memory that would be necessary.

        Multalin proposes an alternative approach that sacrifice a SMALL amount
of sensitivity for a high degree of computational tractability. Multalin does
a series of progressive pairwise alignments between sequences and clusters of
sequences. A cluster consists of two or more already aligned sequences.

        Multalin begins by computing similarity scores for every possible pair
of sequences using a fast algorithm (step 0). These scores are used to create
a hierarchical clustering represented by a dendrogram (step 1). This
clustering shows the order of the pairwise alignments that are performed to
produce the final alignment (step 2). A consensus sequence and pairwise scores
are computed (step 3). To achieve step 3, the scores of all the pairwise
alignments included in the multiple one are computed and they can be used to
do step 1 again; if the clustering order is different, a new multiple
alignment can be done following this new clustering (steps 2 and 3). This
process can be iterated until the clustering order remains unchanged by
iteration.         A. Similarity score for a pair of sequences

This score is equal to the sum of the values of the matches (each match scored
with the scoring table) less the gap penalty times the number of the internal
gaps and less the gap length weight times the total length of internal gaps.
By default, the gap length weight is 0 so the gap penalty is fixed, it is
charged for every internal gap, regardless of length. By default, no penalty
is charged for terminal gaps.

An optimal alignment is one with the maximum possible score. It is sensitive
to the symbol comparison values and to the gap penalty.

        B. The FAST alignments (step 0)

To initiate the process of aligning N sequences, Multalin must computes N
times (N-1) similarity scores. It would take to much time to look for the
optimal score. Therefore, Multalin uses an algorithm from Lipman and Pearson
(1985, Science 227, 1435-1441) that gives a score that is not surely the
maximum one (because the length of the gaps that can be inserted in each
sequence is limited) but that can measure quickly the similarity between two
sequences.

The first step finds the diagonals having the largest number of short perfect
matches (words). The word length depends on the size of the alphabet used to
describe the sequences:

        Alphabet size         Word length    Scoring factor 
           2 or 3                    6              24
           4 to 7                    4              16
           8 to 15                   3              12
          16 to 31                   2               8

If a word from the second sequence does exist in the first one, Fast adds a
score for the word to the score of the diagonal on which the word occurs. This
added score is equal to the word length times a scoring factor (if a word
match overlaps another word on the same diagonal, only the scoring factor for
non-overlapping symbols is added). When the diagonal is not new, the score is
decreased by a factor equal to the length between the two perfect matches,
unless the score becomes negative. In this latter case, the two regions are
considered as different and are scored separately.

In a second step, the five best diagonal regions are re-scored using the
symbol comparison table and the one with the best new score allows to select
the best diagonal.

In the last step, an alignment of the two sequences is performed around the
best diagonal, with a 31 symbol wide window, using the symbol comparison table
and the gap penalty given for the multiple alignment. Actually, the alignment
is not produced, only its score is computed.

This last score is entered in a similarity matrix that records the similarity
scores of all possible pair of sequences.

        C. The hierarchical clustering (step 1)

The approach used by Multalin is sensitive to the order in which sequences are
aligned. The multiple alignment will be better if closest sequences are
aligned first to each other and then to less similar sequences. A clustering
algorithm determines the order of these alignments, from the pairwise
similarity scores calculated at the previous step.

The method used by Multalin is called UPGMA for unweighted pair-group method
using arithmetic averages (Sneath, P.H.A. and Sokal, R.R. (1973) in Numerical
Taxonomy, 230- 234, Freeman, San Francisco). The hierarchy is built from its
base (the set of sequences) creating at each step a new cluster by union of
two clusters or sequences that are the closest ones. The distance between two
clusters or sequences is given by the matrix of similarity that is updated at
each step of the clustering as follow: the similarity score between the new
cluster and a cluster i is the arithmetic mean of the similarity scores
between each of the two clusters which union creates it and the cluster i. At
each step, the number of clusters decreases by one until there is only one
cluster.

The clustering can be represented as a dendrogram that is NOT a phylogenetic
tree although the horizontal branch lengths are proportional to the similarity
scores. The dendrogram purpose is only to produce a clustering order to create
the multiple alignment. This order is the only information from the clustering
used by Multalin.

     D. The Multiple alignment (step 2)

The clustering order is used as follow: the two most similar sequences are
aligned to produce the first cluster; then Multalin aligns the next most
related sequence to this cluster or the next two more similar sequences to
each other to produce another cluster; a series of such pairwise alignment of
clusters includes more and more sequences until there is only one cluster of
all the sequences and the final alignment is produced.

To align two sequences, Multalin uses an algorithm from Needleman and Wunsch
(1970, J. Mol. Biol. 48, 443-453) that allows to find the maximum possible
score between two sequences and one alignment that corresponds to it. The
method consists in building a matrix with one sequence across the top size and
the other one down the left size. An alignment between the sequences can be
represented by a path in this matrix: a path is a broken line joining the top
row or the left column to the bottom row or the right column. The segments of
this broken line are either parallel to the diagonal or parallel to one edge
(for a gap). An optimal path corresponds to an optimal alignment. The idea of
the method is to recursively find optimal paths beginning at each cell of the
matrix and to record their scores in the matrix at the beginning position of
the path. Once the matrix has been calculated, a traceback procedure is
performed to find the successive cells of the best path. It first cell is the
one with the maximum value in the top row or the left column. This value is
the score of the alignment.

To align two clusters (or a cluster and a sequence), Multalin uses an
extension of this method. For an alignment of two individual sequences, the
comparison score between any two sequence symbols is found in a symbol
comparison table. For an alignment of clusters of aligned sequences, the
comparison score between any two positions in these clusters is the arithmetic
average of the scores of all possible symbol comparisons at these positions.

     E. Consensus sequence and scores (step 3)

Multalin generates a consensus sequence finding at each position a character
that is function of the characters in all the sequences at its position. If
more than 90% of the characters in the column are the same letter, the
consensus character is this letter. If more than 90% of the characters in the
column are in the same conservative substitution cluster, the consensus
character is this cluster symbol. In both cases, the consensus character and
the characters that belong to its symbol cluster are represented with an
uppercase letter. If more than 50% of the characters in the column are the
same letter, the consensus character is this letter. If more than 50% of the
characters in the column are in the same conservative substitution cluster,
the consensus character is this cluster symbol. In both cases, the consensus
character and the characters that belong to its symbol cluster are represented
with a lowercase letter. If none of these conditions is true, the consensus
character is a space. The consensus levels (90 and 50) can be modified in the
configuration file (ma.cfg).

        The multiple alignment produces an alignment for each pair of sequences
that are included in itself. These pairwise alignments are not necessarily
optimal pairwise alignments because they must be compatible between
themselves. They are used to compute a new clustering of the sequences (new
step 1).

        F. Iteration

The complete process can be represented by the following figure:

method
step    0 & 1          2             3 & 1          2              3 & 1...
               Clust          Mult           Clust          Mult          Clust... 
pass #     0   1              1              2              2    ...

 where: Clust= Clustering order; Mult= Multiple alignment.

The iterations stop when two successive clustering orders are identical. If
the first clustering order is calculated with the Fast algorithm (step 0), the
process usually converges after one or two passes. With an arbitrary first
clustering order, more passes can be necessary (4 to 6). In some rare cases,
the process can oscillate: if it is between two clustering orders, Multalin
detects it and stop the process; if the cycle is bigger, the user must
interrupt the process himself (hitting Ctrl-C). In version 5.1, the maximal 
number of iterations is set to 10.

                        __________________________
                       |                          |
                       |       Files formats      |
                       |__________________________|

 Multalin Format
 ----------------
        > SeqName the sequence name is the
        > first word of the first comment line  
        > max: 7 letters  
        > comment lines begin with >  
        AAAACCGTTAAA
        > SeqNam2 the 2nd sequence beginning  
        > shows the end of the first one  
        AAACCTGGAC

 GenBank Format
 ----------------  
        LOCUS      SeqName  
        any lines  
        ORIGIN     anything              
        1 aggtcccttt tgtgttgttt

The sequence name is the first word after the LOCUS key-word. The sequence
begins on the line following the ORIGIN key-word. The next sequence
information begins with the LOCUS key-word.

 EMBL Format (flat file)
 ------------------------  
        ID   SeqName  
        any lines  
        SQ   anything          
        aauccagug gagaucaaag          
        any sequence lines  
        //

The sequence name is the first word after the ID key-word. The sequence begins
on the line following the SQ key-word. The next sequence information begins
on the line following //

 GCG Format
 ----------- 
        Only one sequence which name is the file name. The sequence begins  on
the line that follows .. Comments between <, > or $ are deleted.