| distmat

## Function

Creates a distance matrix from multiple alignments

## Description

distmat calculates the evolutionary distances between every pair of sequences in a multiple alignment. The sequences need to be aligned before running this program. The quality of the alignment is of paramount importance in obtaining meaningful information from this analysis. This application calculates a distance matrix for the set of sequences in the alignment. The distances are expressed in terms of the number of substitutions per 100 bases or amino acids.

As sequence diverge so does the probability of there being multiple substitutions at any one site in the alignment increase. The distance will then be an underestimate of the true evolutionary distance between the sequences. Therefore, there are a number of methods for correcting the observed substitution rate for the occurence of multiple substutions.

For nucleotides, the "-position" flag allows the user to choose base positions to analyse in each codon, i.e. 123 (all bases), 12 (the first two bases), 1, 2, or 3 individual bases.

### Uncorrected distances

This method does not make any corrections for multiple substitutions. Therefore, the score will be an underestimate of the distance between the sequences. This will not be less significant for highly similar sets of sequences.

    S = m/(npos + gaps*gap_penalty)                                  (1)

    m 	    - score of matches (1 for an exact match, a fraction for partial
    	      matches and 0 for no match)
    npos	    - number of positions included in m
    gaps        - number of gaps in the sequences
    gap_penalty - the score given to a gapped position

    D = uncorrected distance = p-distance = 1-S          (2)

The score of match includes all exact matches. For nucleotides, if the flag "-ambiguous" is used then partial matches are included in the score. For example, a match of M (A or C) with A will increment m by 0.5 (0.5*1.0). Gaps are not included in the calculation unless a non zero value is given with "-gapweight". It should be noted that end gaps and internal gaps will be weighted by the same amount. So it is recommended that this be used with "-sbegin"and "-send" to specify the start and end of the region to calculate the distance from.

## Multiple Substitution correction algorithms

### Jukes-Cantor

This can be used for nucleotide and protein sequences.

    distance = -b ln (1-D/b)

    D - uncorrected distance
    b - constant. b= 3/4 for nucleotides and 19/20 for proteins.

Partial matches and gap positions can be taken into account in the calculation of D, by setting the "-ambiguous" and "-gapweight" flags (see "uncorrected distance" method).

Reference:
"Phylogenetic Inference", Swofford, Olsen, Waddell, and Hillis, in Molecular Systematics, 2nd ed., Sinauer Ass., Inc., 1996, Ch. 11.

### Tajima-Nei

This method is only for nucleotide sequences. It uses the same equation as Jukes-Cantor, but the b-parameter is not constant. Also, only exact matches are considered in the calculation of the match score and gap positions are ignored.

    A = 1, T = 2, C = 3, G = 4

    b = 0.5(1.- Sum(i=A,G)(fraction[i]^2  + D^2/h)

    h = Sum(i=A,C)Sum(k=T,G) (0.5 * pair_frequency[i,k]^2/(fraction[i]*fraction[k]))

    distance = -b ln(1.-D/b)

    pair_frequency[i,k]   - frequency of the i and k base pair at sites in
    			the alignement of the pair of sequences.
    fraction[i]           - average content of the base i in both sequences

Reference:
F. Tajima and M. Nei, Mol. Biol. Evol. 1984, 1, 269.

### Kimura Two-Parameter distance

This method is only for nucleotide sequences. This uses the principle that transition substitutions (purine-purine and pyrimidine-purine) are more likely than transversion substitutions (purine-pyprimidine). Purine being the nucleic acid constituent of A and G, and pyrimidine being the nucleic acid derivative of the bases C, T and U. Gaps are ignored and abiguous symbols other than R (purine) and Y (pyrimidine) are ingnored.

    P = transitions/npos
    Q = transversions/npos

    npos - number of positions scored

    distance = -0.5 ln[ (1-2P-Q)*sqrt(1-2Q)]

Reference:
M. kimura, J. Mol. Evol. 1980, 16, 111.

### Tamura

This method is only for nucleotide sequences. This method uses transition and transversion rates and takes into account the deviation of GC content from the expected value of 50 %. Gap and ambiguous positions are ignored.

    P = transitions/npos
    Q = transversions/npos

    npos - number of positions scored

    GC1 = GC fraction in sequence 1
    GC2 = GC fraction in sequence 2
    C = GC1 + GC2 - 2*GC1*GC2

    distance = -C ln(1-P/C-Q) - 0.5(1-C) ln(1-2Q)

Reference:
K. Tamura, Mol. Biol. Evol. 1992, 9, 678.

### Jin-Nei Gamma distance

This method applies to nucleotides only. This again uses transition and transversion rates. As with the Kimura two parameter method, gaps and ambiguous symbols other than R and Y are not oncluded in the score. The shape parameter, i.e. "a", is the square of the inverse of the coefficient of variation of the average substitution,

    L = average substituition = transition_rate + 2 * transversion_rate
    a = (average L)^2/(variance of L)

    P = transitions/npos
    Q = transversions/npos

    npos - number of positions scored

    distance = 0.5 * a ((1-2P-Q)^(-1/a) + 0.5 (1-2Q)^(-1/a) -3/2)

It is suggested [Jin et al.], in general, that the distance be calculated with an a-value of 1. However, the user can specify their own value, using the "-parametera" option, or calculate for each pair of sequence, using "-calculatea".

Reference:
L. Jin and M. Nei, Mol. Biol. Evol. 1990, 7, 82.

### Kimura Protein distance

This method is used for proteins only. Gaps are ignored and only exact matches and ambiguity codes contribute to the match score.

    S = m/npos

    m  - exact match
    npos - number of positions scored

    D = 1-S
    distance = -ln(1 - D - 0.2D^2)

Reference:
M. Kimura, The Neutral Theory of Molecular Evolution, Camb. Uni. Press, Camb., 1983.

## Usage

Here is a sample session with distmat

    % distmat ../../data/pax.align
    Creates a distance matrix from multiple alignments
    Multiple substitution correction methods for proteins
             0 : Uncorrected
             1 : Jukes-Cantor
             2 : Kimura Protein
    Method to use [0]: 2
    Output file [pax.distmat]:

Go to the input files for this example
Go to the output files for this example

## Command line arguments

       Mandatory qualifiers (* if not always prompted):
      [-msf]               seqset     File containing a sequence alignment.
    *  -nucmethod          menu       Multiple substitution correction methods for
                                      nucleotides.
    *  -protmethod         menu       Multiple substitution correction methods for
                                      proteins.
      [-outf]              outfile    Enter a name for the distance matrix

       Optional qualifiers (* if not always prompted):
    *  -ambiguous          boolean    Option to use the abiguous codes in the
                                      calculation of the Jukes-Cantor method or if
                                      the sequences are proteins.
    *  -gapweight          float      Option to weight gaps in the uncorrected
                                      (nucleotide) and Jukes-Cantor distance
                                      methods.
    *  -position           integer    Choose base positions to analyse in each
                                      codon i.e. 123 (all bases), 12 (the first
                                      two bases), 1, 2, or 3 individual bases.
    *  -calculatea         boolean    This will force the calculation of the
                                      a-parameter in the Jin-Nei Gamma distance
                                      calculation, otherwise the default is 1.0
                                      (see -parametera option).
    *  -parametera         float      User defined a parameter to be use in the
                                      Jin-Nei Gamma distance calculation. The
                                      suggested value to be used is 1.0 [Jin et
                                      al.] and this is the default.

       Advanced qualifiers: (none)
       Associated qualifiers:
      "-msf" related qualifiers
       -sbegin1             integer    First base used
       -send1               integer    Last base used, def=seq length
       -sreverse1           boolean    Reverse (if DNA)
       -sask1               boolean    Ask for begin/end/reverse
       -snucleotide1        boolean    Sequence is nucleotide
       -sprotein1           boolean    Sequence is protein
       -slower1             boolean    Make lower case
       -supper1             boolean    Make upper case
       -sformat1            string     Input sequence format
       -sopenfile1          string     Input filename
       -sdbname1            string     Database name
       -sid1                string     Entryname
       -ufo1                string     UFO features
       -fformat1            string     Features format
       -fopenfile1          string     Features file name
      "-outf" related qualifiers
       -odirectory2         string     Output directory

       General qualifiers:
       -auto                boolean    Turn off prompts
       -stdout              boolean    Write standard output
       -filter              boolean    Read standard input, write standard output
       -options             boolean    Prompt for required and optional values
       -debug               boolean    Write debug output to program.dbg
       -acdlog              boolean    Write ACD processing log to program.acdlog
       -acdpretty           boolean    Rewrite ACD file as program.acdpretty
       -acdtable            boolean    Write HTML table of options
       -verbose             boolean    Report some/full command line options
       -help                boolean    Report command line options. More
                                      information on associated and general
                                      qualifiers can be found with -help -verbose
       -warning             boolean    Report warnings
       -error               boolean    Report errors
       -fatal               boolean    Report fatal errors
       -die                 boolean    Report deaths

Mandatory qualifiers | Allowed values | Default
--- | --- | ---
[-msf] (Parameter 1) | File containing a sequence alignment. | Readable sequences | Required
-nucmethod | Multiple substitution correction methods for nucleotides. |
0 | (Uncorrected)
1 | (Jukes-Cantor)
2 | (Kimura)
3 | (Tamura)
4 | (Tajima-Nei)
5 | (Jin-Nei Gamma)
| 0
-protmethod | Multiple substitution correction methods for proteins. |
0 | (Uncorrected)
1 | (Jukes-Cantor)
2 | (Kimura Protein)
| 0
[-outf] (Parameter 2) | Enter a name for the distance matrix | Output file | <sequence>.distmat
Optional qualifiers | Allowed values | Default
-ambiguous | Option to use the abiguous codes in the calculation of the Jukes-Cantor method or if the sequences are proteins. | Boolean value Yes/No | No
-gapweight | Option to weight gaps in the uncorrected (nucleotide) and Jukes-Cantor distance methods. | Any numeric value | 0.
-position | Choose base positions to analyse in each codon i.e. 123 (all bases), 12 (the first two bases), 1, 2, or 3 individual bases. | Any integer value | 123
-calculatea | This will force the calculation of the a-parameter in the Jin-Nei Gamma distance calculation, otherwise the default is 1.0 (see -parametera option). | Boolean value Yes/No | No
-parametera | User defined a parameter to be use in the Jin-Nei Gamma distance calculation. The suggested value to be used is 1.0 [Jin et al.] and this is the default. | Any numeric value | 1.0
Advanced qualifiers | Allowed values | Default
(none)

## Input file format

It reads in a normal multiple sequence alignment file.

The quality of the alignment is of paramount importance in obtaining meaningful information from this analysis.

### Input files for usage example

### File: ../../data/pax.align

    PileUp

       MSF:  603  Type: P    Check:  9004   ..

     Name: PAX4_HUMAN oo  Len:  603  Check:  6594  Weight:  11.2
     Name: PAX6_HUMAN oo  Len:  603  Check:  7176  Weight:  9.1
     Name: PAX3_HUMAN oo  Len:  603  Check:  7760  Weight:  9.5
     Name: PAX7_HUMAN oo  Len:  603  Check:  4677  Weight:  13.7
     Name: PAX1_HUMAN oo  Len:  603  Check:  9671  Weight:  8.7
     Name: PAX9_HUMAN oo  Len:  603  Check:   565  Weight:  12.0
     Name: PAX2_HUMAN oo  Len:  603  Check:  9553  Weight:  8.7
     Name: PAX5_HUMAN oo  Len:  603  Check:   448  Weight:  11.2
     Name: PX8A_HUMAN oo  Len:  603  Check:  6763  Weight:  7.5
     Name: PX8D_HUMAN oo  Len:  603  Check:  5797  Weight:  7.9

    //

    PAX4_HUMAN      .......... .......... .........M HQDGISSMNQ LGGLFVNGRP
    PAX6_HUMAN      .......... .......... .......... MQNSHSGVNQ LGGVFVNGRP
    PAX3_HUMAN      MTTLAGAVPR MMRPGPGQNY PRSGFPLEVS TPLGQGRVNQ LGGVFINGRP
    PAX7_HUMAN      MAALPGTVPR MMRPAPGQNY PRTGFPLEVS TPLGQGRVNQ LGGVFINGRP
    PAX1_HUMAN      .......... .......... .......... MEQTYGEVNQ LGGVFVNGRP
    PAX9_HUMAN      .......... .......... .......... MEPAFGEVNQ LGGVFVNGRP
    PAX2_HUMAN      .......... ........MD MHCKADPFSA MHPGHGGVNQ LGGVFVNGRP
    PAX5_HUMAN      .......... ........MD LEKNYPTPRT SRTGHGGVNQ LGGVFVNGRP
    PX8A_HUMAN      .......... .......... .....MPHNS IRSGHGGLNQ LGGAFVNGRP
    PX8D_HUMAN      .......... .......... .....MPHNS IRSGHGGLNQ LGGAFVNGRP

    PAX4_HUMAN      LPLDTRQQIV RLAVSGMRPC DISRILKVSN GCVSKILGRY YRTGVLEPKG
    PAX6_HUMAN      LPDSTRQKIV ELAHSGARPC DISRILQVSN GCVSKILGRY YETGSIRPRA
    PAX3_HUMAN      LPNHIRHKIV EMAHHGIRPC VISRQLRVSH GCVSKILCRY QETGSIRPGA
    PAX7_HUMAN      LPNHIRHKIV EMAHHGIRPC VISRQLRVSH GCVSKILCRY QETGSIRPGA
    PAX1_HUMAN      LPNAIRLRIV ELAQLGIRPC DISRQLRVSH GCVSKILARY NETGSILPGA
    PAX9_HUMAN      LPNAIRLRIV ELAQLGIRPC DISRQLRVSH GCVSKILARY NETGSILPGA
    PAX2_HUMAN      LPDVVRQRIV ELAHQGVRPC DISRQLRVSH GCVSKILGRY YETGSIKPGV
    PAX5_HUMAN      LPDVVRQRIV ELAHQGVRPC DISRQLRVSH GCVSKILGRY YETGSIKPGV
    PX8A_HUMAN      LPEVVRQRIV DLAHQGVRPC DISRQLRVSH GCVSKILGRY YETGSIRPGV
    PX8D_HUMAN      LPEVVRQRIV DLAHQGVRPC DISRQLRVSH GCVSKILGRY YETGSIRPGV

    PAX4_HUMAN      IGGSKPR.LA TPPVVARIAQ LKGECPALFA WEIQRQLCAE GLCTQDKTPS
    PAX6_HUMAN      IGGSKPR.VA TPEVVSKIAQ YKRECPSIFA WEIRDRLLSE GVCTNDNIPS
    PAX3_HUMAN      IGGSKPKQVT TPDVEKKIEE YKRENPGMFS WEIRDKLLKD AVCDRNTVPS
    PAX7_HUMAN      IGGSKPRQVA TPDVEKKIEE YKRENPGMFS WEIRDRLLKD GHCDRSTVPS
    PAX1_HUMAN      IGGSKPR.VT TPNVVKHIRD YKQGDPGIFA WEIRDRLLAD GVCDKYNVPS

      [Part of this file has been deleted for brevity]

    PX8A_HUMAN      VSSSSSTPSS LSSSAFLDLQ QVGSGVPPFN AFPHAASVYG QFTGQALLSG
    PX8D_HUMAN      ....KSAPGS RPS....... .....MP... .FPMLPPCTG SSRARPSSQG

    PAX4_HUMAN      .......... .......... .....ERCLS DTPPKACLKP CWDCGSFLLP
    PAX6_HUMAN      .......... .......... .SFTMANNLP MQPPVPSQTS SYSCMLPTSP
    PAX3_HUMAN      NGL.SPQVM. .......... GLLTNHGGVP HQPQTDYALS PLTGGLEPTT
    PAX7_HUMAN      NGL.SPQVM. .......... SILGNPSAVP PQPQADFSIS PLHGGLDSAT
    PAX1_HUMAN      .......... .......... GAGVAVHGGE LAAAMTFKHR EGTDRKPP..
    PAX9_HUMAN      .......... .......... ......HNCD IPASLAFKGM QAARE.....
    PAX2_HUMAN      .......... .......... GSYPTSTLAG MVPGSEFSGN PYSHPQYTAY
    PAX5_HUMAN      .......... .......... GSYSAPTLTG MVPGSEFSGS PYSHPQYSSY
    PX8A_HUMAN      REMVGPTLPG YPPHIPTSGQ GSYASSAIAG MVAGSEYSGN AYGHTPYSSY
    PX8D_HUMAN      ERWWGPRCP. .......... DTHPTSPPAD RAAMPPLPSQ AWWQEVN...

    PAX4_HUMAN      VIAPSCVDVA WP.CLDASLA HHLIGGAGKA TPTHFS.... ..........
    PAX6_HUMAN      SVNGRSYDTY TPPHMQTHMN SQPMGTSGTT STGLISPGVS VPVQVPGSEP
    PAX3_HUMAN      TVSASCSQRL DHMKSLDSLP TSQSYCPPTY STTGYSMDPV TGYQYGQYGQ
    PAX7_HUMAN      SISASCSQRA DSIKPGDSLP TSQAYCPPTY STTGYSVDPV AGYQYGQYGQ
    PAX1_HUMAN      ..SSGSKAPD ALSSLH.... ....GLPIPA STS....... ..........
    PAX9_HUMAN      ..GSHSVTAS AL........ .......... .......... ..........
    PAX2_HUMAN      NEAWRFSNPA LLSSPYYYSA APR.SAPAAR AAAYDRH... ..........
    PAX5_HUMAN      NDSWRFPNPG LLGSPYYYSA AARGAAPPAA ATAYDRH... ..........
    PX8A_HUMAN      SEAWGFPNSS LLSSPYYYSS TSRPSAPPTT ATAFDHL... ..........
    PX8D_HUMAN      ..TLAMPMAT PPTPP..... TARPGASPTP AC........ ..........

    PAX4_HUMAN      .....HWP.. .......... .......... .......... ..........
    PAX6_HUMAN      DMS.QYWPRL Q......... .......... .......... ..........
    PAX3_HUMAN      S...KPWTF. .......... .......... .......... ..........
    PAX7_HUMAN      SECLVPWASP VPIPSPTPRA SCLFMESYKV VSGWGMSISQ MEKLKSSQME
    PAX1_HUMAN      .......... .......... .......... .......... ..........
    PAX9_HUMAN      .......... .......... .......... .......... ..........
    PAX2_HUMAN      .......... .......... .......... .......... ..........
    PAX5_HUMAN      .......... .......... .......... .......... ..........
    PX8A_HUMAN      .......... .......... .......... .......... ..........
    PX8D_HUMAN      .......... .......... .......... .......... ..........

    PAX4_HUMAN      ...
    PAX6_HUMAN      ...
    PAX3_HUMAN      ...
    PAX7_HUMAN      QFT
    PAX1_HUMAN      ...
    PAX9_HUMAN      ...
    PAX2_HUMAN      ...
    PAX5_HUMAN      ...
    PX8A_HUMAN      ...
    PX8D_HUMAN      ...

## Output file format

The output from the program is a file containing a matrix of the calculated distances between each of the input aligned sequences. The distances are expressed in terms of the number of substitutions per 100 bases or amino acids.

### Output files for usage example

### File: pax.distmat

    Distance Matrix
    ---------------

    Using the Kimura correction method
    Gap weighting is 0.000000

    	    1	    2	    3	    4	    5	    6	    7	    8	    9	    10
    	  0.00	 96.15	137.48	128.72	161.14	160.37	157.55	154.23	164.32	152.68		PAX4_HUMAN 1
    		  0.00	111.86	109.96	156.25	149.70	143.75	135.71	150.60	146.87		PAX6_HUMAN 2
    			  0.00	 26.21	131.54	143.54	162.95	151.39	163.56	159.78		PAX3_HUMAN 3
    				  0.00	145.45	138.76	158.79	149.96	167.26	161.82		PAX7_HUMAN 4
    					  0.00	 44.29	120.84	123.00	131.69	130.22		PAX1_HUMAN 5
    						  0.00	123.56	130.21	131.64	130.17		PAX9_HUMAN 6
    							  0.00	 36.43	 53.12	 64.32		PAX2_HUMAN 7
    								  0.00	 60.88	 73.82		PAX5_HUMAN 8
    									  0.00	 20.37		PX8A_HUMAN 9
    										  0.00		PX8D_HUMAN 10

## Data files

None.

## Notes

None.

## References

See the following for details of the methods used:

1. "Phylogenetic Inference", Swofford, Olsen, Waddell, and Hillis, in Molecular Systematics, 2nd ed., Sinauer Ass., Inc., 1996, Ch. 11.
2. F. Tajima and M. Nei, Mol. Biol. Evol. 1984, 1, 269.
3. M. Kimura, J. Mol. Evol. 1980, 16, 111.
4. K. Tamura, Mol. Biol. Evol. 1992, 9, 678.
5. L. Jin and M. Nei, Mol. Biol. Evol. 1990, 7, 82.
6. M. Kimura, The Neutral Theory of Molecular Evolution, Camb. Uni. Press, Camb., 1983.

## Warnings

The quality of the alignment is of paramount importance in obtaining meaningful information from this analysis.

## Diagnostic Error Messages

None.

## Exit status

It always exits with status 0.

## Known bugs

None.

## See also

Program name | Description
--- | ---

## Author(s)

Tim Carver (tcarver © hgmp.mrc.ac.uk)
HGMP-RC, Genome Campus, Hinxton, Cambridge CB10 1SB, UK

## History

Written (March 2001) - Tim Carver

## Target users

This program is intended to be used by everyone and everything, from naive users to embedded scripts.

## Comments