1 {- |
    2    Common substitution matrices for alignments.
    3 
    4    When in doubt, use BLOSUM62.
    5    Consult <http://www.ncbi.nlm.nih.gov/blast/blast_whatsnew.shtml#20051206>
    6    for some hints on good parameters for nucleotide alignments.
    7  
    8    See also <http://en.wikipedia.org/wiki/Substitution_matrix> for a
    9    summary about the difference between the different matrices. 
   10 -}
   11 
   12 module Bio.Alignment.Matrices
   13     (
   14     -- * BLOSUM matrices 
   15     -- | For BLOSUM matrices, the associated number determines the
   16     -- similarity of the sequences the matrices are derived from.
   17     --
   18     -- Henikoff, S. and Henikoff, J. Amino acid substitution matrices from protein blocks. Proc. Natl. Acad. Sci. USA. 89(biochemistry): 10915 - 10919 (1992).
   19     blosum45, blosum62, blosum80
   20 
   21     -- * PAM matrices 
   22     -- | For PAM matrics, the number indicates the number of mutations
   23     --   that have occurred between the sequences that are compared.
   24     --
   25     -- Dayhoff, M.O., Schwartz, R.M., Orcutt, B.C. A model of evolutionary change in proteins. In \"Atlas of Protein Sequence and Structure\" 5(3) M.O. Dayhoff (ed.), 345 - 352 (1978).
   26     , pam30, pam70
   27 
   28     -- * BLASTn defaults, for nucleotide sequences
   29     , blastn_default
   30 
   31     -- * Generic and simple matrix generator
   32     , simpleMx
   33     ) where
   34 
   35 import Bio.Alignment.AlignData (Chr)
   36 import qualified Data.Map as M
   37 
   38 -- | BLOSUM45 matrix, suitable for distantly related sequences
   39 blosum45 :: (Char,Char) -> Int
   40 blosum45 m = M.findWithDefault (-5) m $ M.fromList [(('A','A'),5),
   41     (('A','B'),-1), (('A','C'),-1), (('A','D'),-2), (('A','E'),-1),
   42     (('A','F'),-2), (('A','G'),0), (('A','H'),-2), (('A','I'),-1),
   43     (('A','K'),-1), (('A','L'),-1), (('A','M'),-1), (('A','N'),-1),
   44     (('A','P'),-1), (('A','Q'),-1), (('A','R'),-2), (('A','S'),1),
   45     (('A','T'),0), (('A','V'),0), (('A','W'),-2), (('A','X'),-1),
   46     (('A','Y'),-2), (('A','Z'),-1), (('B','A'),-1), (('B','B'),4),
   47     (('B','C'),-2), (('B','D'),5), (('B','E'),1), (('B','F'),-3),
   48     (('B','G'),-1), (('B','H'),0), (('B','I'),-3), (('B','K'),0),
   49     (('B','L'),-3), (('B','M'),-2), (('B','N'),4), (('B','P'),-2),
   50     (('B','Q'),0), (('B','R'),-1), (('B','S'),0), (('B','T'),0),
   51     (('B','V'),-3), (('B','W'),-4), (('B','X'),-1), (('B','Y'),-2),
   52     (('B','Z'),2), (('C','A'),-1), (('C','B'),-2), (('C','C'),12),
   53     (('C','D'),-3), (('C','E'),-3), (('C','F'),-2), (('C','G'),-3),
   54     (('C','H'),-3), (('C','I'),-3), (('C','K'),-3), (('C','L'),-2),
   55     (('C','M'),-2), (('C','N'),-2), (('C','P'),-4), (('C','Q'),-3),
   56     (('C','R'),-3), (('C','S'),-1), (('C','T'),-1), (('C','V'),-1),
   57     (('C','W'),-5), (('C','X'),-1), (('C','Y'),-3), (('C','Z'),-3),
   58     (('D','A'),-2), (('D','B'),5), (('D','C'),-3), (('D','D'),7),
   59     (('D','E'),2), (('D','F'),-4), (('D','G'),-1), (('D','H'),0),
   60     (('D','I'),-4), (('D','K'),0), (('D','L'),-3), (('D','M'),-3),
   61     (('D','N'),2), (('D','P'),-1), (('D','Q'),0), (('D','R'),-1),
   62     (('D','S'),0), (('D','T'),-1), (('D','V'),-3), (('D','W'),-4),
   63     (('D','X'),-1), (('D','Y'),-2), (('D','Z'),1), (('E','A'),-1),
   64     (('E','B'),1), (('E','C'),-3), (('E','D'),2), (('E','E'),6),
   65     (('E','F'),-3), (('E','G'),-2), (('E','H'),0), (('E','I'),-3),
   66     (('E','K'),1), (('E','L'),-2), (('E','M'),-2), (('E','N'),0),
   67     (('E','P'),0), (('E','Q'),2), (('E','R'),0), (('E','S'),0),
   68     (('E','T'),-1), (('E','V'),-3), (('E','W'),-3), (('E','X'),-1),
   69     (('E','Y'),-2), (('E','Z'),4), (('F','A'),-2), (('F','B'),-3),
   70     (('F','C'),-2), (('F','D'),-4), (('F','E'),-3), (('F','F'),8),
   71     (('F','G'),-3), (('F','H'),-2), (('F','I'),0), (('F','K'),-3),
   72     (('F','L'),1), (('F','M'),0), (('F','N'),-2), (('F','P'),-3),
   73     (('F','Q'),-4), (('F','R'),-2), (('F','S'),-2), (('F','T'),-1),
   74     (('F','V'),0), (('F','W'),1), (('F','X'),-1), (('F','Y'),3),
   75     (('F','Z'),-3), (('G','A'),0), (('G','B'),-1), (('G','C'),-3),
   76     (('G','D'),-1), (('G','E'),-2), (('G','F'),-3), (('G','G'),7),
   77     (('G','H'),-2), (('G','I'),-4), (('G','K'),-2), (('G','L'),-3),
   78     (('G','M'),-2), (('G','N'),0), (('G','P'),-2), (('G','Q'),-2),
   79     (('G','R'),-2), (('G','S'),0), (('G','T'),-2), (('G','V'),-3),
   80     (('G','W'),-2), (('G','X'),-1), (('G','Y'),-3), (('G','Z'),-2),
   81     (('H','A'),-2), (('H','B'),0), (('H','C'),-3), (('H','D'),0),
   82     (('H','E'),0), (('H','F'),-2), (('H','G'),-2), (('H','H'),10),
   83     (('H','I'),-3), (('H','K'),-1), (('H','L'),-2), (('H','M'),0),
   84     (('H','N'),1), (('H','P'),-2), (('H','Q'),1), (('H','R'),0),
   85     (('H','S'),-1), (('H','T'),-2), (('H','V'),-3), (('H','W'),-3),
   86     (('H','X'),-1), (('H','Y'),2), (('H','Z'),0), (('I','A'),-1),
   87     (('I','B'),-3), (('I','C'),-3), (('I','D'),-4), (('I','E'),-3),
   88     (('I','F'),0), (('I','G'),-4), (('I','H'),-3), (('I','I'),5),
   89     (('I','K'),-3), (('I','L'),2), (('I','M'),2), (('I','N'),-2),
   90     (('I','P'),-2), (('I','Q'),-2), (('I','R'),-3), (('I','S'),-2),
   91     (('I','T'),-1), (('I','V'),3), (('I','W'),-2), (('I','X'),-1),
   92     (('I','Y'),0), (('I','Z'),-3), (('K','A'),-1), (('K','B'),0),
   93     (('K','C'),-3), (('K','D'),0), (('K','E'),1), (('K','F'),-3),
   94     (('K','G'),-2), (('K','H'),-1), (('K','I'),-3), (('K','K'),5),
   95     (('K','L'),-3), (('K','M'),-1), (('K','N'),0), (('K','P'),-1),
   96     (('K','Q'),1), (('K','R'),3), (('K','S'),-1), (('K','T'),-1),
   97     (('K','V'),-2), (('K','W'),-2), (('K','X'),-1), (('K','Y'),-1),
   98     (('K','Z'),1), (('L','A'),-1), (('L','B'),-3), (('L','C'),-2),
   99     (('L','D'),-3), (('L','E'),-2), (('L','F'),1), (('L','G'),-3),
  100     (('L','H'),-2), (('L','I'),2), (('L','K'),-3), (('L','L'),5),
  101     (('L','M'),2), (('L','N'),-3), (('L','P'),-3), (('L','Q'),-2),
  102     (('L','R'),-2), (('L','S'),-3), (('L','T'),-1), (('L','V'),1),
  103     (('L','W'),-2), (('L','X'),-1), (('L','Y'),0), (('L','Z'),-2),
  104     (('M','A'),-1), (('M','B'),-2), (('M','C'),-2), (('M','D'),-3),
  105     (('M','E'),-2), (('M','F'),0), (('M','G'),-2), (('M','H'),0),
  106     (('M','I'),2), (('M','K'),-1), (('M','L'),2), (('M','M'),6),
  107     (('M','N'),-2), (('M','P'),-2), (('M','Q'),0), (('M','R'),-1),
  108     (('M','S'),-2), (('M','T'),-1), (('M','V'),1), (('M','W'),-2),
  109     (('M','X'),-1), (('M','Y'),0), (('M','Z'),-1), (('N','A'),-1),
  110     (('N','B'),4), (('N','C'),-2), (('N','D'),2), (('N','E'),0),
  111     (('N','F'),-2), (('N','G'),0), (('N','H'),1), (('N','I'),-2),
  112     (('N','K'),0), (('N','L'),-3), (('N','M'),-2), (('N','N'),6),
  113     (('N','P'),-2), (('N','Q'),0), (('N','R'),0), (('N','S'),1),
  114     (('N','T'),0), (('N','V'),-3), (('N','W'),-4), (('N','X'),-1),
  115     (('N','Y'),-2), (('N','Z'),0), (('P','A'),-1), (('P','B'),-2),
  116     (('P','C'),-4), (('P','D'),-1), (('P','E'),0), (('P','F'),-3),
  117     (('P','G'),-2), (('P','H'),-2), (('P','I'),-2), (('P','K'),-1),
  118     (('P','L'),-3), (('P','M'),-2), (('P','N'),-2), (('P','P'),9),
  119     (('P','Q'),-1), (('P','R'),-2), (('P','S'),-1), (('P','T'),-1),
  120     (('P','V'),-3), (('P','W'),-3), (('P','X'),-1), (('P','Y'),-3),
  121     (('P','Z'),-1), (('Q','A'),-1), (('Q','B'),0), (('Q','C'),-3),
  122     (('Q','D'),0), (('Q','E'),2), (('Q','F'),-4), (('Q','G'),-2),
  123     (('Q','H'),1), (('Q','I'),-2), (('Q','K'),1), (('Q','L'),-2),
  124     (('Q','M'),0), (('Q','N'),0), (('Q','P'),-1), (('Q','Q'),6),
  125     (('Q','R'),1), (('Q','S'),0), (('Q','T'),-1), (('Q','V'),-3),
  126     (('Q','W'),-2), (('Q','X'),-1), (('Q','Y'),-1), (('Q','Z'),4),
  127     (('R','A'),-2), (('R','B'),-1), (('R','C'),-3), (('R','D'),-1),
  128     (('R','E'),0), (('R','F'),-2), (('R','G'),-2), (('R','H'),0),
  129     (('R','I'),-3), (('R','K'),3), (('R','L'),-2), (('R','M'),-1),
  130     (('R','N'),0), (('R','P'),-2), (('R','Q'),1), (('R','R'),7),
  131     (('R','S'),-1), (('R','T'),-1), (('R','V'),-2), (('R','W'),-2),
  132     (('R','X'),-1), (('R','Y'),-1), (('R','Z'),0), (('S','A'),1),
  133     (('S','B'),0), (('S','C'),-1), (('S','D'),0), (('S','E'),0),
  134     (('S','F'),-2), (('S','G'),0), (('S','H'),-1), (('S','I'),-2),
  135     (('S','K'),-1), (('S','L'),-3), (('S','M'),-2), (('S','N'),1),
  136     (('S','P'),-1), (('S','Q'),0), (('S','R'),-1), (('S','S'),4),
  137     (('S','T'),2), (('S','V'),-1), (('S','W'),-4), (('S','X'),-1),
  138     (('S','Y'),-2), (('S','Z'),0), (('T','A'),0), (('T','B'),0),
  139     (('T','C'),-1), (('T','D'),-1), (('T','E'),-1), (('T','F'),-1),
  140     (('T','G'),-2), (('T','H'),-2), (('T','I'),-1), (('T','K'),-1),
  141     (('T','L'),-1), (('T','M'),-1), (('T','N'),0), (('T','P'),-1),
  142     (('T','Q'),-1), (('T','R'),-1), (('T','S'),2), (('T','T'),5),
  143     (('T','V'),0), (('T','W'),-3), (('T','X'),-1), (('T','Y'),-1),
  144     (('T','Z'),-1), (('V','A'),0), (('V','B'),-3), (('V','C'),-1),
  145     (('V','D'),-3), (('V','E'),-3), (('V','F'),0), (('V','G'),-3),
  146     (('V','H'),-3), (('V','I'),3), (('V','K'),-2), (('V','L'),1),
  147     (('V','M'),1), (('V','N'),-3), (('V','P'),-3), (('V','Q'),-3),
  148     (('V','R'),-2), (('V','S'),-1), (('V','T'),0), (('V','V'),5),
  149     (('V','W'),-3), (('V','X'),-1), (('V','Y'),-1), (('V','Z'),-3),
  150     (('W','A'),-2), (('W','B'),-4), (('W','C'),-5), (('W','D'),-4),
  151     (('W','E'),-3), (('W','F'),1), (('W','G'),-2), (('W','H'),-3),
  152     (('W','I'),-2), (('W','K'),-2), (('W','L'),-2), (('W','M'),-2),
  153     (('W','N'),-4), (('W','P'),-3), (('W','Q'),-2), (('W','R'),-2),
  154     (('W','S'),-4), (('W','T'),-3), (('W','V'),-3), (('W','W'),15),
  155     (('W','X'),-1), (('W','Y'),3), (('W','Z'),-2), (('X','A'),-1),
  156     (('X','B'),-1), (('X','C'),-1), (('X','D'),-1), (('X','E'),-1),
  157     (('X','F'),-1), (('X','G'),-1), (('X','H'),-1), (('X','I'),-1),
  158     (('X','K'),-1), (('X','L'),-1), (('X','M'),-1), (('X','N'),-1),
  159     (('X','P'),-1), (('X','Q'),-1), (('X','R'),-1), (('X','S'),-1),
  160     (('X','T'),-1), (('X','V'),-1), (('X','W'),-1), (('X','X'),-1),
  161     (('X','Y'),-1), (('X','Z'),-1), (('Y','A'),-2), (('Y','B'),-2),
  162     (('Y','C'),-3), (('Y','D'),-2), (('Y','E'),-2), (('Y','F'),3),
  163     (('Y','G'),-3), (('Y','H'),2), (('Y','I'),0), (('Y','K'),-1),
  164     (('Y','L'),0), (('Y','M'),0), (('Y','N'),-2), (('Y','P'),-3),
  165     (('Y','Q'),-1), (('Y','R'),-1), (('Y','S'),-2), (('Y','T'),-1),
  166     (('Y','V'),-1), (('Y','W'),3), (('Y','X'),-1), (('Y','Y'),8),
  167     (('Y','Z'),-2), (('Z','A'),-1), (('Z','B'),2), (('Z','C'),-3),
  168     (('Z','D'),1), (('Z','E'),4), (('Z','F'),-3), (('Z','G'),-2),
  169     (('Z','H'),0), (('Z','I'),-3), (('Z','K'),1), (('Z','L'),-2),
  170     (('Z','M'),-1), (('Z','N'),0), (('Z','P'),-1), (('Z','Q'),4),
  171     (('Z','R'),0), (('Z','S'),0), (('Z','T'),-1), (('Z','V'),-3),
  172     (('Z','W'),-2), (('Z','X'),-1), (('Z','Y'),-2), (('Z','Z'),4)]
  173 
  174 -- | The standard BLOSUM62 matrix.
  175 blosum62 :: (Char,Char) -> Int
  176 blosum62 m = M.findWithDefault (-4) m $ M.fromList 
  177     [(('A','A'),4), (('A','B'),-2), (('A','C'),0), (('A','D'),-2),
  178      (('A','E'),-1), (('A','F'),-2), (('A','G'),0), (('A','H'),-2),
  179      (('A','I'),-1), (('A','K'),-1), (('A','L'),-1), (('A','M'),-1),
  180      (('A','N'),-2), (('A','P'),-1), (('A','Q'),-1), (('A','R'),-1),
  181      (('A','S'),1), (('A','T'),0), (('A','V'),0), (('A','W'),-3),
  182      (('A','X'),-1), (('A','Y'),-2), (('A','Z'),-1), (('B','A'),-2),
  183      (('B','B'),4), (('B','C'),-3), (('B','D'),4), (('B','E'),1),
  184      (('B','F'),-3), (('B','G'),-1), (('B','H'),0), (('B','I'),-3),
  185      (('B','K'),0), (('B','L'),-4), (('B','M'),-3), (('B','N'),3),
  186      (('B','P'),-2), (('B','Q'),0), (('B','R'),-1), (('B','S'),0),
  187      (('B','T'),-1), (('B','V'),-3), (('B','W'),-4), (('B','X'),-1),
  188      (('B','Y'),-3), (('B','Z'),1), (('C','A'),0), (('C','B'),-3),
  189      (('C','C'),9), (('C','D'),-3), (('C','E'),-4), (('C','F'),-2),
  190      (('C','G'),-3), (('C','H'),-3), (('C','I'),-1), (('C','K'),-3),
  191      (('C','L'),-1), (('C','M'),-1), (('C','N'),-3), (('C','P'),-3),
  192      (('C','Q'),-3), (('C','R'),-3), (('C','S'),-1), (('C','T'),-1),
  193      (('C','V'),-1), (('C','W'),-2), (('C','X'),-1), (('C','Y'),-2),
  194      (('C','Z'),-3), (('D','A'),-2), (('D','B'),4), (('D','C'),-3),
  195      (('D','D'),6), (('D','E'),2), (('D','F'),-3), (('D','G'),-1),
  196      (('D','H'),-1), (('D','I'),-3), (('D','K'),-1), (('D','L'),-4),
  197      (('D','M'),-3), (('D','N'),1), (('D','P'),-1), (('D','Q'),0),
  198      (('D','R'),-2), (('D','S'),0), (('D','T'),-1), (('D','V'),-3),
  199      (('D','W'),-4), (('D','X'),-1), (('D','Y'),-3), (('D','Z'),1),
  200      (('E','A'),-1), (('E','B'),1), (('E','C'),-4), (('E','D'),2),
  201      (('E','E'),5), (('E','F'),-3), (('E','G'),-2), (('E','H'),0),
  202      (('E','I'),-3), (('E','K'),1), (('E','L'),-3), (('E','M'),-2),
  203      (('E','N'),0), (('E','P'),-1), (('E','Q'),2), (('E','R'),0),
  204      (('E','S'),0), (('E','T'),-1), (('E','V'),-2), (('E','W'),-3),
  205      (('E','X'),-1), (('E','Y'),-2), (('E','Z'),4), (('F','A'),-2),
  206      (('F','B'),-3), (('F','C'),-2), (('F','D'),-3), (('F','E'),-3),
  207      (('F','F'),6), (('F','G'),-3), (('F','H'),-1), (('F','I'),0),
  208      (('F','K'),-3), (('F','L'),0), (('F','M'),0), (('F','N'),-3),
  209      (('F','P'),-4), (('F','Q'),-3), (('F','R'),-3), (('F','S'),-2),
  210      (('F','T'),-2), (('F','V'),-1), (('F','W'),1), (('F','X'),-1),
  211      (('F','Y'),3), (('F','Z'),-3), (('G','A'),0), (('G','B'),-1),
  212      (('G','C'),-3), (('G','D'),-1), (('G','E'),-2), (('G','F'),-3),
  213      (('G','G'),6), (('G','H'),-2), (('G','I'),-4), (('G','K'),-2),
  214      (('G','L'),-4), (('G','M'),-3), (('G','N'),0), (('G','P'),-2),
  215      (('G','Q'),-2), (('G','R'),-2), (('G','S'),0), (('G','T'),-2),
  216      (('G','V'),-3), (('G','W'),-2), (('G','X'),-1), (('G','Y'),-3),
  217      (('G','Z'),-2), (('H','A'),-2), (('H','B'),0), (('H','C'),-3),
  218      (('H','D'),-1), (('H','E'),0), (('H','F'),-1), (('H','G'),-2),
  219      (('H','H'),8), (('H','I'),-3), (('H','K'),-1), (('H','L'),-3),
  220      (('H','M'),-2), (('H','N'),1), (('H','P'),-2), (('H','Q'),0),
  221      (('H','R'),0), (('H','S'),-1), (('H','T'),-2), (('H','V'),-3),
  222      (('H','W'),-2), (('H','X'),-1), (('H','Y'),2), (('H','Z'),0),
  223      (('I','A'),-1), (('I','B'),-3), (('I','C'),-1), (('I','D'),-3),
  224      (('I','E'),-3), (('I','F'),0), (('I','G'),-4), (('I','H'),-3),
  225      (('I','I'),4), (('I','K'),-3), (('I','L'),2), (('I','M'),1),
  226      (('I','N'),-3), (('I','P'),-3), (('I','Q'),-3), (('I','R'),-3),
  227      (('I','S'),-2), (('I','T'),-1), (('I','V'),3), (('I','W'),-3),
  228      (('I','X'),-1), (('I','Y'),-1), (('I','Z'),-3), (('K','A'),-1),
  229      (('K','B'),0), (('K','C'),-3), (('K','D'),-1), (('K','E'),1),
  230      (('K','F'),-3), (('K','G'),-2), (('K','H'),-1), (('K','I'),-3),
  231      (('K','K'),5), (('K','L'),-2), (('K','M'),-1), (('K','N'),0),
  232      (('K','P'),-1), (('K','Q'),1), (('K','R'),2), (('K','S'),0),
  233      (('K','T'),-1), (('K','V'),-2), (('K','W'),-3), (('K','X'),-1),
  234      (('K','Y'),-2), (('K','Z'),1), (('L','A'),-1), (('L','B'),-4),
  235      (('L','C'),-1), (('L','D'),-4), (('L','E'),-3), (('L','F'),0),
  236      (('L','G'),-4), (('L','H'),-3), (('L','I'),2), (('L','K'),-2),
  237      (('L','L'),4), (('L','M'),2), (('L','N'),-3), (('L','P'),-3),
  238      (('L','Q'),-2), (('L','R'),-2), (('L','S'),-2), (('L','T'),-1),
  239      (('L','V'),1), (('L','W'),-2), (('L','X'),-1), (('L','Y'),-1),
  240      (('L','Z'),-3), (('M','A'),-1), (('M','B'),-3), (('M','C'),-1),
  241      (('M','D'),-3), (('M','E'),-2), (('M','F'),0), (('M','G'),-3),
  242      (('M','H'),-2), (('M','I'),1), (('M','K'),-1), (('M','L'),2),
  243      (('M','M'),5), (('M','N'),-2), (('M','P'),-2), (('M','Q'),0),
  244      (('M','R'),-1), (('M','S'),-1), (('M','T'),-1), (('M','V'),1),
  245      (('M','W'),-1), (('M','X'),-1), (('M','Y'),-1), (('M','Z'),-1),
  246      (('N','A'),-2), (('N','B'),3), (('N','C'),-3), (('N','D'),1),
  247      (('N','E'),0), (('N','F'),-3), (('N','G'),0), (('N','H'),1),
  248      (('N','I'),-3), (('N','K'),0), (('N','L'),-3), (('N','M'),-2),
  249      (('N','N'),6), (('N','P'),-2), (('N','Q'),0), (('N','R'),0),
  250      (('N','S'),1), (('N','T'),0), (('N','V'),-3), (('N','W'),-4),
  251      (('N','X'),-1), (('N','Y'),-2), (('N','Z'),0), (('P','A'),-1),
  252      (('P','B'),-2), (('P','C'),-3), (('P','D'),-1), (('P','E'),-1),
  253      (('P','F'),-4), (('P','G'),-2), (('P','H'),-2), (('P','I'),-3),
  254      (('P','K'),-1), (('P','L'),-3), (('P','M'),-2), (('P','N'),-2),
  255      (('P','P'),7), (('P','Q'),-1), (('P','R'),-2), (('P','S'),-1),
  256      (('P','T'),-1), (('P','V'),-2), (('P','W'),-4), (('P','X'),-1),
  257      (('P','Y'),-3), (('P','Z'),-1), (('Q','A'),-1), (('Q','B'),0),
  258      (('Q','C'),-3), (('Q','D'),0), (('Q','E'),2), (('Q','F'),-3),
  259      (('Q','G'),-2), (('Q','H'),0), (('Q','I'),-3), (('Q','K'),1),
  260      (('Q','L'),-2), (('Q','M'),0), (('Q','N'),0), (('Q','P'),-1),
  261      (('Q','Q'),5), (('Q','R'),1), (('Q','S'),0), (('Q','T'),-1),
  262      (('Q','V'),-2), (('Q','W'),-2), (('Q','X'),-1), (('Q','Y'),-1),
  263      (('Q','Z'),3), (('R','A'),-1), (('R','B'),-1), (('R','C'),-3),
  264      (('R','D'),-2), (('R','E'),0), (('R','F'),-3), (('R','G'),-2),
  265      (('R','H'),0), (('R','I'),-3), (('R','K'),2), (('R','L'),-2),
  266      (('R','M'),-1), (('R','N'),0), (('R','P'),-2), (('R','Q'),1),
  267      (('R','R'),5), (('R','S'),-1), (('R','T'),-1), (('R','V'),-3),
  268      (('R','W'),-3), (('R','X'),-1), (('R','Y'),-2), (('R','Z'),0),
  269      (('S','A'),1), (('S','B'),0), (('S','C'),-1), (('S','D'),0),
  270      (('S','E'),0), (('S','F'),-2), (('S','G'),0), (('S','H'),-1),
  271      (('S','I'),-2), (('S','K'),0), (('S','L'),-2), (('S','M'),-1),
  272      (('S','N'),1), (('S','P'),-1), (('S','Q'),0), (('S','R'),-1),
  273      (('S','S'),4), (('S','T'),1), (('S','V'),-2), (('S','W'),-3),
  274      (('S','X'),-1), (('S','Y'),-2), (('S','Z'),0), (('T','A'),0),
  275      (('T','B'),-1), (('T','C'),-1), (('T','D'),-1), (('T','E'),-1),
  276      (('T','F'),-2), (('T','G'),-2), (('T','H'),-2), (('T','I'),-1),
  277      (('T','K'),-1), (('T','L'),-1), (('T','M'),-1), (('T','N'),0),
  278      (('T','P'),-1), (('T','Q'),-1), (('T','R'),-1), (('T','S'),1),
  279      (('T','T'),5), (('T','V'),0), (('T','W'),-2), (('T','X'),-1),
  280      (('T','Y'),-2), (('T','Z'),-1), (('V','A'),0), (('V','B'),-3),
  281      (('V','C'),-1), (('V','D'),-3), (('V','E'),-2), (('V','F'),-1),
  282      (('V','G'),-3), (('V','H'),-3), (('V','I'),3), (('V','K'),-2),
  283      (('V','L'),1), (('V','M'),1), (('V','N'),-3), (('V','P'),-2),
  284      (('V','Q'),-2), (('V','R'),-3), (('V','S'),-2), (('V','T'),0),
  285      (('V','V'),4), (('V','W'),-3), (('V','X'),-1), (('V','Y'),-1),
  286      (('V','Z'),-2), (('W','A'),-3), (('W','B'),-4), (('W','C'),-2),
  287      (('W','D'),-4), (('W','E'),-3), (('W','F'),1), (('W','G'),-2),
  288      (('W','H'),-2), (('W','I'),-3), (('W','K'),-3), (('W','L'),-2),
  289      (('W','M'),-1), (('W','N'),-4), (('W','P'),-4), (('W','Q'),-2),
  290      (('W','R'),-3), (('W','S'),-3), (('W','T'),-2), (('W','V'),-3),
  291      (('W','W'),11), (('W','X'),-1), (('W','Y'),2), (('W','Z'),-3),
  292      (('X','A'),-1), (('X','B'),-1), (('X','C'),-1), (('X','D'),-1),
  293      (('X','E'),-1), (('X','F'),-1), (('X','G'),-1), (('X','H'),-1),
  294      (('X','I'),-1), (('X','K'),-1), (('X','L'),-1), (('X','M'),-1),
  295      (('X','N'),-1), (('X','P'),-1), (('X','Q'),-1), (('X','R'),-1),
  296      (('X','S'),-1), (('X','T'),-1), (('X','V'),-1), (('X','W'),-1),
  297      (('X','X'),-1), (('X','Y'),-1), (('X','Z'),-1), (('Y','A'),-2),
  298      (('Y','B'),-3), (('Y','C'),-2), (('Y','D'),-3), (('Y','E'),-2),
  299      (('Y','F'),3), (('Y','G'),-3), (('Y','H'),2), (('Y','I'),-1),
  300      (('Y','K'),-2), (('Y','L'),-1), (('Y','M'),-1), (('Y','N'),-2),
  301      (('Y','P'),-3), (('Y','Q'),-1), (('Y','R'),-2), (('Y','S'),-2),
  302      (('Y','T'),-2), (('Y','V'),-1), (('Y','W'),2), (('Y','X'),-1),
  303      (('Y','Y'),7), (('Y','Z'),-2), (('Z','A'),-1), (('Z','B'),1),
  304      (('Z','C'),-3), (('Z','D'),1), (('Z','E'),4), (('Z','F'),-3),
  305      (('Z','G'),-2), (('Z','H'),0), (('Z','I'),-3), (('Z','K'),1),
  306      (('Z','L'),-3), (('Z','M'),-1), (('Z','N'),0), (('Z','P'),-1),
  307      (('Z','Q'),3), (('Z','R'),0), (('Z','S'),0), (('Z','T'),-1),
  308      (('Z','V'),-2), (('Z','W'),-3), (('Z','X'),-1), (('Z','Y'),-2),
  309      (('Z','Z'),4)]
  310 
  311 -- | BLOSUM80 matrix, suitable for closely related sequences. 
  312 blosum80 :: (Char,Char) -> Int
  313 blosum80 m = M.findWithDefault (-6) m $ M.fromList [(('A','A'),5),
  314     (('A','B'),-2), (('A','C'),-1), (('A','D'),-2), (('A','E'),-1),
  315     (('A','F'),-3), (('A','G'),0), (('A','H'),-2), (('A','I'),-2),
  316     (('A','K'),-1), (('A','L'),-2), (('A','M'),-1), (('A','N'),-2),
  317     (('A','P'),-1), (('A','Q'),-1), (('A','R'),-2), (('A','S'),1),
  318     (('A','T'),0), (('A','V'),0), (('A','W'),-3), (('A','X'),-1),
  319     (('A','Y'),-2), (('A','Z'),-1), (('B','A'),-2), (('B','B'),4),
  320     (('B','C'),-4), (('B','D'),4), (('B','E'),1), (('B','F'),-4),
  321     (('B','G'),-1), (('B','H'),-1), (('B','I'),-4), (('B','K'),-1),
  322     (('B','L'),-4), (('B','M'),-3), (('B','N'),4), (('B','P'),-2),
  323     (('B','Q'),0), (('B','R'),-2), (('B','S'),0), (('B','T'),-1),
  324     (('B','V'),-4), (('B','W'),-5), (('B','X'),-1), (('B','Y'),-3),
  325     (('B','Z'),0), (('C','A'),-1), (('C','B'),-4), (('C','C'),9),
  326     (('C','D'),-4), (('C','E'),-5), (('C','F'),-3), (('C','G'),-4),
  327     (('C','H'),-4), (('C','I'),-2), (('C','K'),-4), (('C','L'),-2),
  328     (('C','M'),-2), (('C','N'),-3), (('C','P'),-4), (('C','Q'),-4),
  329     (('C','R'),-4), (('C','S'),-2), (('C','T'),-1), (('C','V'),-1),
  330     (('C','W'),-3), (('C','X'),-1), (('C','Y'),-3), (('C','Z'),-4),
  331     (('D','A'),-2), (('D','B'),4), (('D','C'),-4), (('D','D'),6),
  332     (('D','E'),1), (('D','F'),-4), (('D','G'),-2), (('D','H'),-2),
  333     (('D','I'),-4), (('D','K'),-1), (('D','L'),-5), (('D','M'),-4),
  334     (('D','N'),1), (('D','P'),-2), (('D','Q'),-1), (('D','R'),-2),
  335     (('D','S'),-1), (('D','T'),-1), (('D','V'),-4), (('D','W'),-6),
  336     (('D','X'),-1), (('D','Y'),-4), (('D','Z'),1), (('E','A'),-1),
  337     (('E','B'),1), (('E','C'),-5), (('E','D'),1), (('E','E'),6),
  338     (('E','F'),-4), (('E','G'),-3), (('E','H'),0), (('E','I'),-4),
  339     (('E','K'),1), (('E','L'),-4), (('E','M'),-2), (('E','N'),-1),
  340     (('E','P'),-2), (('E','Q'),2), (('E','R'),-1), (('E','S'),0),
  341     (('E','T'),-1), (('E','V'),-3), (('E','W'),-4), (('E','X'),-1),
  342     (('E','Y'),-3), (('E','Z'),4), (('F','A'),-3), (('F','B'),-4),
  343     (('F','C'),-3), (('F','D'),-4), (('F','E'),-4), (('F','F'),6),
  344     (('F','G'),-4), (('F','H'),-2), (('F','I'),-1), (('F','K'),-4),
  345     (('F','L'),0), (('F','M'),0), (('F','N'),-4), (('F','P'),-4),
  346     (('F','Q'),-4), (('F','R'),-4), (('F','S'),-3), (('F','T'),-2),
  347     (('F','V'),-1), (('F','W'),0), (('F','X'),-1), (('F','Y'),3),
  348     (('F','Z'),-4), (('G','A'),0), (('G','B'),-1), (('G','C'),-4),
  349     (('G','D'),-2), (('G','E'),-3), (('G','F'),-4), (('G','G'),6),
  350     (('G','H'),-3), (('G','I'),-5), (('G','K'),-2), (('G','L'),-4),
  351     (('G','M'),-4), (('G','N'),-1), (('G','P'),-3), (('G','Q'),-2),
  352     (('G','R'),-3), (('G','S'),-1), (('G','T'),-2), (('G','V'),-4),
  353     (('G','W'),-4), (('G','X'),-1), (('G','Y'),-4), (('G','Z'),-3),
  354     (('H','A'),-2), (('H','B'),-1), (('H','C'),-4), (('H','D'),-2),
  355     (('H','E'),0), (('H','F'),-2), (('H','G'),-3), (('H','H'),8),
  356     (('H','I'),-4), (('H','K'),-1), (('H','L'),-3), (('H','M'),-2),
  357     (('H','N'),0), (('H','P'),-3), (('H','Q'),1), (('H','R'),0),
  358     (('H','S'),-1), (('H','T'),-2), (('H','V'),-4), (('H','W'),-3),
  359     (('H','X'),-1), (('H','Y'),2), (('H','Z'),0), (('I','A'),-2),
  360     (('I','B'),-4), (('I','C'),-2), (('I','D'),-4), (('I','E'),-4),
  361     (('I','F'),-1), (('I','G'),-5), (('I','H'),-4), (('I','I'),5),
  362     (('I','K'),-3), (('I','L'),1), (('I','M'),1), (('I','N'),-4),
  363     (('I','P'),-4), (('I','Q'),-3), (('I','R'),-3), (('I','S'),-3),
  364     (('I','T'),-1), (('I','V'),3), (('I','W'),-3), (('I','X'),-1),
  365     (('I','Y'),-2), (('I','Z'),-4), (('K','A'),-1), (('K','B'),-1),
  366     (('K','C'),-4), (('K','D'),-1), (('K','E'),1), (('K','F'),-4),
  367     (('K','G'),-2), (('K','H'),-1), (('K','I'),-3), (('K','K'),5),
  368     (('K','L'),-3), (('K','M'),-2), (('K','N'),0), (('K','P'),-1),
  369     (('K','Q'),1), (('K','R'),2), (('K','S'),-1), (('K','T'),-1),
  370     (('K','V'),-3), (('K','W'),-4), (('K','X'),-1), (('K','Y'),-3),
  371     (('K','Z'),1), (('L','A'),-2), (('L','B'),-4), (('L','C'),-2),
  372     (('L','D'),-5), (('L','E'),-4), (('L','F'),0), (('L','G'),-4),
  373     (('L','H'),-3), (('L','I'),1), (('L','K'),-3), (('L','L'),4),
  374     (('L','M'),2), (('L','N'),-4), (('L','P'),-3), (('L','Q'),-3),
  375     (('L','R'),-3), (('L','S'),-3), (('L','T'),-2), (('L','V'),1),
  376     (('L','W'),-2), (('L','X'),-1), (('L','Y'),-2), (('L','Z'),-3),
  377     (('M','A'),-1), (('M','B'),-3), (('M','C'),-2), (('M','D'),-4),
  378     (('M','E'),-2), (('M','F'),0), (('M','G'),-4), (('M','H'),-2),
  379     (('M','I'),1), (('M','K'),-2), (('M','L'),2), (('M','M'),6),
  380     (('M','N'),-3), (('M','P'),-3), (('M','Q'),0), (('M','R'),-2),
  381     (('M','S'),-2), (('M','T'),-1), (('M','V'),1), (('M','W'),-2),
  382     (('M','X'),-1), (('M','Y'),-2), (('M','Z'),-2), (('N','A'),-2),
  383     (('N','B'),4), (('N','C'),-3), (('N','D'),1), (('N','E'),-1),
  384     (('N','F'),-4), (('N','G'),-1), (('N','H'),0), (('N','I'),-4),
  385     (('N','K'),0), (('N','L'),-4), (('N','M'),-3), (('N','N'),6),
  386     (('N','P'),-3), (('N','Q'),0), (('N','R'),-1), (('N','S'),0),
  387     (('N','T'),0), (('N','V'),-4), (('N','W'),-4), (('N','X'),-1),
  388     (('N','Y'),-3), (('N','Z'),0), (('P','A'),-1), (('P','B'),-2),
  389     (('P','C'),-4), (('P','D'),-2), (('P','E'),-2), (('P','F'),-4),
  390     (('P','G'),-3), (('P','H'),-3), (('P','I'),-4), (('P','K'),-1),
  391     (('P','L'),-3), (('P','M'),-3), (('P','N'),-3), (('P','P'),8),
  392     (('P','Q'),-2), (('P','R'),-2), (('P','S'),-1), (('P','T'),-2),
  393     (('P','V'),-3), (('P','W'),-5), (('P','X'),-1), (('P','Y'),-4),
  394     (('P','Z'),-2), (('Q','A'),-1), (('Q','B'),0), (('Q','C'),-4),
  395     (('Q','D'),-1), (('Q','E'),2), (('Q','F'),-4), (('Q','G'),-2),
  396     (('Q','H'),1), (('Q','I'),-3), (('Q','K'),1), (('Q','L'),-3),
  397     (('Q','M'),0), (('Q','N'),0), (('Q','P'),-2), (('Q','Q'),6),
  398     (('Q','R'),1), (('Q','S'),0), (('Q','T'),-1), (('Q','V'),-3),
  399     (('Q','W'),-3), (('Q','X'),-1), (('Q','Y'),-2), (('Q','Z'),3),
  400     (('R','A'),-2), (('R','B'),-2), (('R','C'),-4), (('R','D'),-2),
  401     (('R','E'),-1), (('R','F'),-4), (('R','G'),-3), (('R','H'),0),
  402     (('R','I'),-3), (('R','K'),2), (('R','L'),-3), (('R','M'),-2),
  403     (('R','N'),-1), (('R','P'),-2), (('R','Q'),1), (('R','R'),6),
  404     (('R','S'),-1), (('R','T'),-1), (('R','V'),-3), (('R','W'),-4),
  405     (('R','X'),-1), (('R','Y'),-3), (('R','Z'),0), (('S','A'),1),
  406     (('S','B'),0), (('S','C'),-2), (('S','D'),-1), (('S','E'),0),
  407     (('S','F'),-3), (('S','G'),-1), (('S','H'),-1), (('S','I'),-3),
  408     (('S','K'),-1), (('S','L'),-3), (('S','M'),-2), (('S','N'),0),
  409     (('S','P'),-1), (('S','Q'),0), (('S','R'),-1), (('S','S'),5),
  410     (('S','T'),1), (('S','V'),-2), (('S','W'),-4), (('S','X'),-1),
  411     (('S','Y'),-2), (('S','Z'),0), (('T','A'),0), (('T','B'),-1),
  412     (('T','C'),-1), (('T','D'),-1), (('T','E'),-1), (('T','F'),-2),
  413     (('T','G'),-2), (('T','H'),-2), (('T','I'),-1), (('T','K'),-1),
  414     (('T','L'),-2), (('T','M'),-1), (('T','N'),0), (('T','P'),-2),
  415     (('T','Q'),-1), (('T','R'),-1), (('T','S'),1), (('T','T'),5),
  416     (('T','V'),0), (('T','W'),-4), (('T','X'),-1), (('T','Y'),-2),
  417     (('T','Z'),-1), (('V','A'),0), (('V','B'),-4), (('V','C'),-1),
  418     (('V','D'),-4), (('V','E'),-3), (('V','F'),-1), (('V','G'),-4),
  419     (('V','H'),-4), (('V','I'),3), (('V','K'),-3), (('V','L'),1),
  420     (('V','M'),1), (('V','N'),-4), (('V','P'),-3), (('V','Q'),-3),
  421     (('V','R'),-3), (('V','S'),-2), (('V','T'),0), (('V','V'),4),
  422     (('V','W'),-3), (('V','X'),-1), (('V','Y'),-2), (('V','Z'),-3),
  423     (('W','A'),-3), (('W','B'),-5), (('W','C'),-3), (('W','D'),-6),
  424     (('W','E'),-4), (('W','F'),0), (('W','G'),-4), (('W','H'),-3),
  425     (('W','I'),-3), (('W','K'),-4), (('W','L'),-2), (('W','M'),-2),
  426     (('W','N'),-4), (('W','P'),-5), (('W','Q'),-3), (('W','R'),-4),
  427     (('W','S'),-4), (('W','T'),-4), (('W','V'),-3), (('W','W'),11),
  428     (('W','X'),-1), (('W','Y'),2), (('W','Z'),-4), (('X','A'),-1),
  429     (('X','B'),-1), (('X','C'),-1), (('X','D'),-1), (('X','E'),-1),
  430     (('X','F'),-1), (('X','G'),-1), (('X','H'),-1), (('X','I'),-1),
  431     (('X','K'),-1), (('X','L'),-1), (('X','M'),-1), (('X','N'),-1),
  432     (('X','P'),-1), (('X','Q'),-1), (('X','R'),-1), (('X','S'),-1),
  433     (('X','T'),-1), (('X','V'),-1), (('X','W'),-1), (('X','X'),-1),
  434     (('X','Y'),-1), (('X','Z'),-1), (('Y','A'),-2), (('Y','B'),-3),
  435     (('Y','C'),-3), (('Y','D'),-4), (('Y','E'),-3), (('Y','F'),3),
  436     (('Y','G'),-4), (('Y','H'),2), (('Y','I'),-2), (('Y','K'),-3),
  437     (('Y','L'),-2), (('Y','M'),-2), (('Y','N'),-3), (('Y','P'),-4),
  438     (('Y','Q'),-2), (('Y','R'),-3), (('Y','S'),-2), (('Y','T'),-2),
  439     (('Y','V'),-2), (('Y','W'),2), (('Y','X'),-1), (('Y','Y'),7),
  440     (('Y','Z'),-3), (('Z','A'),-1), (('Z','B'),0), (('Z','C'),-4),
  441     (('Z','D'),1), (('Z','E'),4), (('Z','F'),-4), (('Z','G'),-3),
  442     (('Z','H'),0), (('Z','I'),-4), (('Z','K'),1), (('Z','L'),-3),
  443     (('Z','M'),-2), (('Z','N'),0), (('Z','P'),-2), (('Z','Q'),3),
  444     (('Z','R'),0), (('Z','S'),0), (('Z','T'),-1), (('Z','V'),-3),
  445     (('Z','W'),-4), (('Z','X'),-1), (('Z','Y'),-3), (('Z','Z'),4)]
  446 
  447 -- | The standard PAM30 matrix
  448 pam30 :: (Char,Char) -> Int
  449 pam30 m = M.findWithDefault (-17) m $ M.fromList [(('A','A'),6),
  450     (('A','B'),-3), (('A','C'),-6), (('A','D'),-3), (('A','E'),-2),
  451     (('A','F'),-8), (('A','G'),-2), (('A','H'),-7), (('A','I'),-5),
  452     (('A','K'),-7), (('A','L'),-6), (('A','M'),-5), (('A','N'),-4),
  453     (('A','P'),-2), (('A','Q'),-4), (('A','R'),-7), (('A','S'),0),
  454     (('A','T'),-1), (('A','V'),-2), (('A','W'),-13), (('A','X'),-3),
  455     (('A','Y'),-8), (('A','Z'),-3), (('B','A'),-3), (('B','B'),6),
  456     (('B','C'),-12), (('B','D'),6), (('B','E'),1), (('B','F'),-10),
  457     (('B','G'),-3), (('B','H'),-1), (('B','I'),-6), (('B','K'),-2),
  458     (('B','L'),-9), (('B','M'),-10), (('B','N'),6), (('B','P'),-7),
  459     (('B','Q'),-3), (('B','R'),-7), (('B','S'),-1), (('B','T'),-3),
  460     (('B','V'),-8), (('B','W'),-10), (('B','X'),-5), (('B','Y'),-6),
  461     (('B','Z'),0), (('C','A'),-6), (('C','B'),-12), (('C','C'),10),
  462     (('C','D'),-14), (('C','E'),-14), (('C','F'),-13), (('C','G'),-9),
  463     (('C','H'),-7), (('C','I'),-6), (('C','K'),-14), (('C','L'),-15),
  464     (('C','M'),-13), (('C','N'),-11), (('C','P'),-8), (('C','Q'),-14),
  465     (('C','R'),-8), (('C','S'),-3), (('C','T'),-8), (('C','V'),-6),
  466     (('C','W'),-15), (('C','X'),-9), (('C','Y'),-4), (('C','Z'),-14),
  467     (('D','A'),-3), (('D','B'),6), (('D','C'),-14), (('D','D'),8),
  468     (('D','E'),2), (('D','F'),-15), (('D','G'),-3), (('D','H'),-4),
  469     (('D','I'),-7), (('D','K'),-4), (('D','L'),-12), (('D','M'),-11),
  470     (('D','N'),2), (('D','P'),-8), (('D','Q'),-2), (('D','R'),-10),
  471     (('D','S'),-4), (('D','T'),-5), (('D','V'),-8), (('D','W'),-15),
  472     (('D','X'),-5), (('D','Y'),-11), (('D','Z'),1), (('E','A'),-2),
  473     (('E','B'),1), (('E','C'),-14), (('E','D'),2), (('E','E'),8),
  474     (('E','F'),-14), (('E','G'),-4), (('E','H'),-5), (('E','I'),-5),
  475     (('E','K'),-4), (('E','L'),-9), (('E','M'),-7), (('E','N'),-2),
  476     (('E','P'),-5), (('E','Q'),1), (('E','R'),-9), (('E','S'),-4),
  477     (('E','T'),-6), (('E','V'),-6), (('E','W'),-17), (('E','X'),-5),
  478     (('E','Y'),-8), (('E','Z'),6), (('F','A'),-8), (('F','B'),-10),
  479     (('F','C'),-13), (('F','D'),-15), (('F','E'),-14), (('F','F'),9),
  480     (('F','G'),-9), (('F','H'),-6), (('F','I'),-2), (('F','K'),-14),
  481     (('F','L'),-3), (('F','M'),-4), (('F','N'),-9), (('F','P'),-10),
  482     (('F','Q'),-13), (('F','R'),-9), (('F','S'),-6), (('F','T'),-9),
  483     (('F','V'),-8), (('F','W'),-4), (('F','X'),-8), (('F','Y'),2),
  484     (('F','Z'),-13), (('G','A'),-2), (('G','B'),-3), (('G','C'),-9),
  485     (('G','D'),-3), (('G','E'),-4), (('G','F'),-9), (('G','G'),6),
  486     (('G','H'),-9), (('G','I'),-11), (('G','K'),-7), (('G','L'),-10),
  487     (('G','M'),-8), (('G','N'),-3), (('G','P'),-6), (('G','Q'),-7),
  488     (('G','R'),-9), (('G','S'),-2), (('G','T'),-6), (('G','V'),-5),
  489     (('G','W'),-15), (('G','X'),-5), (('G','Y'),-14), (('G','Z'),-5),
  490     (('H','A'),-7), (('H','B'),-1), (('H','C'),-7), (('H','D'),-4),
  491     (('H','E'),-5), (('H','F'),-6), (('H','G'),-9), (('H','H'),9),
  492     (('H','I'),-9), (('H','K'),-6), (('H','L'),-6), (('H','M'),-10),
  493     (('H','N'),0), (('H','P'),-4), (('H','Q'),1), (('H','R'),-2),
  494     (('H','S'),-6), (('H','T'),-7), (('H','V'),-6), (('H','W'),-7),
  495     (('H','X'),-5), (('H','Y'),-3), (('H','Z'),-1), (('I','A'),-5),
  496     (('I','B'),-6), (('I','C'),-6), (('I','D'),-7), (('I','E'),-5),
  497     (('I','F'),-2), (('I','G'),-11), (('I','H'),-9), (('I','I'),8),
  498     (('I','K'),-6), (('I','L'),-1), (('I','M'),-1), (('I','N'),-5),
  499     (('I','P'),-8), (('I','Q'),-8), (('I','R'),-5), (('I','S'),-7),
  500     (('I','T'),-2), (('I','V'),2), (('I','W'),-14), (('I','X'),-5),
  501     (('I','Y'),-6), (('I','Z'),-6), (('K','A'),-7), (('K','B'),-2),
  502     (('K','C'),-14), (('K','D'),-4), (('K','E'),-4), (('K','F'),-14),
  503     (('K','G'),-7), (('K','H'),-6), (('K','I'),-6), (('K','K'),7),
  504     (('K','L'),-8), (('K','M'),-2), (('K','N'),-1), (('K','P'),-6),
  505     (('K','Q'),-3), (('K','R'),0), (('K','S'),-4), (('K','T'),-3),
  506     (('K','V'),-9), (('K','W'),-12), (('K','X'),-5), (('K','Y'),-9),
  507     (('K','Z'),-4), (('L','A'),-6), (('L','B'),-9), (('L','C'),-15),
  508     (('L','D'),-12), (('L','E'),-9), (('L','F'),-3), (('L','G'),-10),
  509     (('L','H'),-6), (('L','I'),-1), (('L','K'),-8), (('L','L'),7),
  510     (('L','M'),1), (('L','N'),-7), (('L','P'),-7), (('L','Q'),-5),
  511     (('L','R'),-8), (('L','S'),-8), (('L','T'),-7), (('L','V'),-2),
  512     (('L','W'),-6), (('L','X'),-6), (('L','Y'),-7), (('L','Z'),-7),
  513     (('M','A'),-5), (('M','B'),-10), (('M','C'),-13), (('M','D'),-11),
  514     (('M','E'),-7), (('M','F'),-4), (('M','G'),-8), (('M','H'),-10),
  515     (('M','I'),-1), (('M','K'),-2), (('M','L'),1), (('M','M'),11),
  516     (('M','N'),-9), (('M','P'),-8), (('M','Q'),-4), (('M','R'),-4),
  517     (('M','S'),-5), (('M','T'),-4), (('M','V'),-1), (('M','W'),-13),
  518     (('M','X'),-5), (('M','Y'),-11), (('M','Z'),-5), (('N','A'),-4),
  519     (('N','B'),6), (('N','C'),-11), (('N','D'),2), (('N','E'),-2),
  520     (('N','F'),-9), (('N','G'),-3), (('N','H'),0), (('N','I'),-5),
  521     (('N','K'),-1), (('N','L'),-7), (('N','M'),-9), (('N','N'),8),
  522     (('N','P'),-6), (('N','Q'),-3), (('N','R'),-6), (('N','S'),0),
  523     (('N','T'),-2), (('N','V'),-8), (('N','W'),-8), (('N','X'),-3),
  524     (('N','Y'),-4), (('N','Z'),-3), (('P','A'),-2), (('P','B'),-7),
  525     (('P','C'),-8), (('P','D'),-8), (('P','E'),-5), (('P','F'),-10),
  526     (('P','G'),-6), (('P','H'),-4), (('P','I'),-8), (('P','K'),-6),
  527     (('P','L'),-7), (('P','M'),-8), (('P','N'),-6), (('P','P'),8),
  528     (('P','Q'),-3), (('P','R'),-4), (('P','S'),-2), (('P','T'),-4),
  529     (('P','V'),-6), (('P','W'),-14), (('P','X'),-5), (('P','Y'),-13),
  530     (('P','Z'),-4), (('Q','A'),-4), (('Q','B'),-3), (('Q','C'),-14),
  531     (('Q','D'),-2), (('Q','E'),1), (('Q','F'),-13), (('Q','G'),-7),
  532     (('Q','H'),1), (('Q','I'),-8), (('Q','K'),-3), (('Q','L'),-5),
  533     (('Q','M'),-4), (('Q','N'),-3), (('Q','P'),-3), (('Q','Q'),8),
  534     (('Q','R'),-2), (('Q','S'),-5), (('Q','T'),-5), (('Q','V'),-7),
  535     (('Q','W'),-13), (('Q','X'),-5), (('Q','Y'),-12), (('Q','Z'),6),
  536     (('R','A'),-7), (('R','B'),-7), (('R','C'),-8), (('R','D'),-10),
  537     (('R','E'),-9), (('R','F'),-9), (('R','G'),-9), (('R','H'),-2),
  538     (('R','I'),-5), (('R','K'),0), (('R','L'),-8), (('R','M'),-4),
  539     (('R','N'),-6), (('R','P'),-4), (('R','Q'),-2), (('R','R'),8),
  540     (('R','S'),-3), (('R','T'),-6), (('R','V'),-8), (('R','W'),-2),
  541     (('R','X'),-6), (('R','Y'),-10), (('R','Z'),-4), (('S','A'),0),
  542     (('S','B'),-1), (('S','C'),-3), (('S','D'),-4), (('S','E'),-4),
  543     (('S','F'),-6), (('S','G'),-2), (('S','H'),-6), (('S','I'),-7),
  544     (('S','K'),-4), (('S','L'),-8), (('S','M'),-5), (('S','N'),0),
  545     (('S','P'),-2), (('S','Q'),-5), (('S','R'),-3), (('S','S'),6),
  546     (('S','T'),0), (('S','V'),-6), (('S','W'),-5), (('S','X'),-3),
  547     (('S','Y'),-7), (('S','Z'),-5), (('T','A'),-1), (('T','B'),-3),
  548     (('T','C'),-8), (('T','D'),-5), (('T','E'),-6), (('T','F'),-9),
  549     (('T','G'),-6), (('T','H'),-7), (('T','I'),-2), (('T','K'),-3),
  550     (('T','L'),-7), (('T','M'),-4), (('T','N'),-2), (('T','P'),-4),
  551     (('T','Q'),-5), (('T','R'),-6), (('T','S'),0), (('T','T'),7),
  552     (('T','V'),-3), (('T','W'),-13), (('T','X'),-4), (('T','Y'),-6),
  553     (('T','Z'),-6), (('V','A'),-2), (('V','B'),-8), (('V','C'),-6),
  554     (('V','D'),-8), (('V','E'),-6), (('V','F'),-8), (('V','G'),-5),
  555     (('V','H'),-6), (('V','I'),2), (('V','K'),-9), (('V','L'),-2),
  556     (('V','M'),-1), (('V','N'),-8), (('V','P'),-6), (('V','Q'),-7),
  557     (('V','R'),-8), (('V','S'),-6), (('V','T'),-3), (('V','V'),7),
  558     (('V','W'),-15), (('V','X'),-5), (('V','Y'),-7), (('V','Z'),-6),
  559     (('W','A'),-13), (('W','B'),-10), (('W','C'),-15),
  560     (('W','D'),-15), (('W','E'),-17), (('W','F'),-4), (('W','G'),-15),
  561     (('W','H'),-7), (('W','I'),-14), (('W','K'),-12), (('W','L'),-6),
  562     (('W','M'),-13), (('W','N'),-8), (('W','P'),-14), (('W','Q'),-13),
  563     (('W','R'),-2), (('W','S'),-5), (('W','T'),-13), (('W','V'),-15),
  564     (('W','W'),13), (('W','X'),-11), (('W','Y'),-5), (('W','Z'),-14),
  565     (('X','A'),-3), (('X','B'),-5), (('X','C'),-9), (('X','D'),-5),
  566     (('X','E'),-5), (('X','F'),-8), (('X','G'),-5), (('X','H'),-5),
  567     (('X','I'),-5), (('X','K'),-5), (('X','L'),-6), (('X','M'),-5),
  568     (('X','N'),-3), (('X','P'),-5), (('X','Q'),-5), (('X','R'),-6),
  569     (('X','S'),-3), (('X','T'),-4), (('X','V'),-5), (('X','W'),-11),
  570     (('X','X'),-5), (('X','Y'),-7), (('X','Z'),-5), (('Y','A'),-8),
  571     (('Y','B'),-6), (('Y','C'),-4), (('Y','D'),-11), (('Y','E'),-8),
  572     (('Y','F'),2), (('Y','G'),-14), (('Y','H'),-3), (('Y','I'),-6),
  573     (('Y','K'),-9), (('Y','L'),-7), (('Y','M'),-11), (('Y','N'),-4),
  574     (('Y','P'),-13), (('Y','Q'),-12), (('Y','R'),-10), (('Y','S'),-7),
  575     (('Y','T'),-6), (('Y','V'),-7), (('Y','W'),-5), (('Y','X'),-7),
  576     (('Y','Y'),10), (('Y','Z'),-9), (('Z','A'),-3), (('Z','B'),0),
  577     (('Z','C'),-14), (('Z','D'),1), (('Z','E'),6), (('Z','F'),-13),
  578     (('Z','G'),-5), (('Z','H'),-1), (('Z','I'),-6), (('Z','K'),-4),
  579     (('Z','L'),-7), (('Z','M'),-5), (('Z','N'),-3), (('Z','P'),-4),
  580     (('Z','Q'),6), (('Z','R'),-4), (('Z','S'),-5), (('Z','T'),-6),
  581     (('Z','V'),-6), (('Z','W'),-14), (('Z','X'),-5), (('Z','Y'),-9),
  582     (('Z','Z'),6)]
  583 
  584 -- | The standard PAM70 matrix.
  585 pam70 :: (Char,Char) -> Int
  586 pam70 m = M.findWithDefault (-11) m $ M.fromList [(('A','A'),5),
  587     (('A','B'),-1), (('A','C'),-4), (('A','D'),-1), (('A','E'),-1),
  588     (('A','F'),-6), (('A','G'),0), (('A','H'),-4), (('A','I'),-2),
  589     (('A','K'),-4), (('A','L'),-4), (('A','M'),-3), (('A','N'),-2),
  590     (('A','P'),0), (('A','Q'),-2), (('A','R'),-4), (('A','S'),1),
  591     (('A','T'),1), (('A','V'),-1), (('A','W'),-9), (('A','X'),-2),
  592     (('A','Y'),-5), (('A','Z'),-1), (('B','A'),-1), (('B','B'),5),
  593     (('B','C'),-8), (('B','D'),5), (('B','E'),2), (('B','F'),-7),
  594     (('B','G'),-1), (('B','H'),0), (('B','I'),-4), (('B','K'),-1),
  595     (('B','L'),-6), (('B','M'),-6), (('B','N'),5), (('B','P'),-4),
  596     (('B','Q'),-1), (('B','R'),-4), (('B','S'),0), (('B','T'),-1),
  597     (('B','V'),-5), (('B','W'),-7), (('B','X'),-2), (('B','Y'),-4),
  598     (('B','Z'),1), (('C','A'),-4), (('C','B'),-8), (('C','C'),9),
  599     (('C','D'),-9), (('C','E'),-9), (('C','F'),-8), (('C','G'),-6),
  600     (('C','H'),-5), (('C','I'),-4), (('C','K'),-9), (('C','L'),-10),
  601     (('C','M'),-9), (('C','N'),-7), (('C','P'),-5), (('C','Q'),-9),
  602     (('C','R'),-5), (('C','S'),-1), (('C','T'),-5), (('C','V'),-4),
  603     (('C','W'),-11), (('C','X'),-6), (('C','Y'),-2), (('C','Z'),-9),
  604     (('D','A'),-1), (('D','B'),5), (('D','C'),-9), (('D','D'),6),
  605     (('D','E'),3), (('D','F'),-10), (('D','G'),-1), (('D','H'),-1),
  606     (('D','I'),-5), (('D','K'),-2), (('D','L'),-8), (('D','M'),-7),
  607     (('D','N'),3), (('D','P'),-4), (('D','Q'),0), (('D','R'),-6),
  608     (('D','S'),-1), (('D','T'),-2), (('D','V'),-5), (('D','W'),-10),
  609     (('D','X'),-3), (('D','Y'),-7), (('D','Z'),2), (('E','A'),-1),
  610     (('E','B'),2), (('E','C'),-9), (('E','D'),3), (('E','E'),6),
  611     (('E','F'),-9), (('E','G'),-2), (('E','H'),-2), (('E','I'),-4),
  612     (('E','K'),-2), (('E','L'),-6), (('E','M'),-4), (('E','N'),0),
  613     (('E','P'),-3), (('E','Q'),2), (('E','R'),-5), (('E','S'),-2),
  614     (('E','T'),-3), (('E','V'),-4), (('E','W'),-11), (('E','X'),-3),
  615     (('E','Y'),-6), (('E','Z'),5), (('F','A'),-6), (('F','B'),-7),
  616     (('F','C'),-8), (('F','D'),-10), (('F','E'),-9), (('F','F'),8),
  617     (('F','G'),-7), (('F','H'),-4), (('F','I'),0), (('F','K'),-9),
  618     (('F','L'),-1), (('F','M'),-2), (('F','N'),-6), (('F','P'),-7),
  619     (('F','Q'),-9), (('F','R'),-7), (('F','S'),-4), (('F','T'),-6),
  620     (('F','V'),-5), (('F','W'),-2), (('F','X'),-5), (('F','Y'),4),
  621     (('F','Z'),-9), (('G','A'),0), (('G','B'),-1), (('G','C'),-6),
  622     (('G','D'),-1), (('G','E'),-2), (('G','F'),-7), (('G','G'),6),
  623     (('G','H'),-6), (('G','I'),-6), (('G','K'),-5), (('G','L'),-7),
  624     (('G','M'),-6), (('G','N'),-1), (('G','P'),-3), (('G','Q'),-4),
  625     (('G','R'),-6), (('G','S'),0), (('G','T'),-3), (('G','V'),-3),
  626     (('G','W'),-10), (('G','X'),-3), (('G','Y'),-9), (('G','Z'),-3),
  627     (('H','A'),-4), (('H','B'),0), (('H','C'),-5), (('H','D'),-1),
  628     (('H','E'),-2), (('H','F'),-4), (('H','G'),-6), (('H','H'),8),
  629     (('H','I'),-6), (('H','K'),-3), (('H','L'),-4), (('H','M'),-6),
  630     (('H','N'),1), (('H','P'),-2), (('H','Q'),2), (('H','R'),0),
  631     (('H','S'),-3), (('H','T'),-4), (('H','V'),-4), (('H','W'),-5),
  632     (('H','X'),-3), (('H','Y'),-1), (('H','Z'),1), (('I','A'),-2),
  633     (('I','B'),-4), (('I','C'),-4), (('I','D'),-5), (('I','E'),-4),
  634     (('I','F'),0), (('I','G'),-6), (('I','H'),-6), (('I','I'),7),
  635     (('I','K'),-4), (('I','L'),1), (('I','M'),1), (('I','N'),-3),
  636     (('I','P'),-5), (('I','Q'),-5), (('I','R'),-3), (('I','S'),-4),
  637     (('I','T'),-1), (('I','V'),3), (('I','W'),-9), (('I','X'),-3),
  638     (('I','Y'),-4), (('I','Z'),-4), (('K','A'),-4), (('K','B'),-1),
  639     (('K','C'),-9), (('K','D'),-2), (('K','E'),-2), (('K','F'),-9),
  640     (('K','G'),-5), (('K','H'),-3), (('K','I'),-4), (('K','K'),6),
  641     (('K','L'),-5), (('K','M'),0), (('K','N'),0), (('K','P'),-4),
  642     (('K','Q'),-1), (('K','R'),2), (('K','S'),-2), (('K','T'),-1),
  643     (('K','V'),-6), (('K','W'),-7), (('K','X'),-3), (('K','Y'),-7),
  644     (('K','Z'),-2), (('L','A'),-4), (('L','B'),-6), (('L','C'),-10),
  645     (('L','D'),-8), (('L','E'),-6), (('L','F'),-1), (('L','G'),-7),
  646     (('L','H'),-4), (('L','I'),1), (('L','K'),-5), (('L','L'),6),
  647     (('L','M'),2), (('L','N'),-5), (('L','P'),-5), (('L','Q'),-3),
  648     (('L','R'),-6), (('L','S'),-6), (('L','T'),-4), (('L','V'),0),
  649     (('L','W'),-4), (('L','X'),-4), (('L','Y'),-4), (('L','Z'),-4),
  650     (('M','A'),-3), (('M','B'),-6), (('M','C'),-9), (('M','D'),-7),
  651     (('M','E'),-4), (('M','F'),-2), (('M','G'),-6), (('M','H'),-6),
  652     (('M','I'),1), (('M','K'),0), (('M','L'),2), (('M','M'),10),
  653     (('M','N'),-5), (('M','P'),-5), (('M','Q'),-2), (('M','R'),-2),
  654     (('M','S'),-3), (('M','T'),-2), (('M','V'),0), (('M','W'),-8),
  655     (('M','X'),-3), (('M','Y'),-7), (('M','Z'),-3), (('N','A'),-2),
  656     (('N','B'),5), (('N','C'),-7), (('N','D'),3), (('N','E'),0),
  657     (('N','F'),-6), (('N','G'),-1), (('N','H'),1), (('N','I'),-3),
  658     (('N','K'),0), (('N','L'),-5), (('N','M'),-5), (('N','N'),6),
  659     (('N','P'),-3), (('N','Q'),-1), (('N','R'),-3), (('N','S'),1),
  660     (('N','T'),0), (('N','V'),-5), (('N','W'),-6), (('N','X'),-2),
  661     (('N','Y'),-3), (('N','Z'),-1), (('P','A'),0), (('P','B'),-4),
  662     (('P','C'),-5), (('P','D'),-4), (('P','E'),-3), (('P','F'),-7),
  663     (('P','G'),-3), (('P','H'),-2), (('P','I'),-5), (('P','K'),-4),
  664     (('P','L'),-5), (('P','M'),-5), (('P','N'),-3), (('P','P'),7),
  665     (('P','Q'),-1), (('P','R'),-2), (('P','S'),0), (('P','T'),-2),
  666     (('P','V'),-3), (('P','W'),-9), (('P','X'),-3), (('P','Y'),-9),
  667     (('P','Z'),-2), (('Q','A'),-2), (('Q','B'),-1), (('Q','C'),-9),
  668     (('Q','D'),0), (('Q','E'),2), (('Q','F'),-9), (('Q','G'),-4),
  669     (('Q','H'),2), (('Q','I'),-5), (('Q','K'),-1), (('Q','L'),-3),
  670     (('Q','M'),-2), (('Q','N'),-1), (('Q','P'),-1), (('Q','Q'),7),
  671     (('Q','R'),0), (('Q','S'),-3), (('Q','T'),-3), (('Q','V'),-4),
  672     (('Q','W'),-8), (('Q','X'),-2), (('Q','Y'),-8), (('Q','Z'),5),
  673     (('R','A'),-4), (('R','B'),-4), (('R','C'),-5), (('R','D'),-6),
  674     (('R','E'),-5), (('R','F'),-7), (('R','G'),-6), (('R','H'),0),
  675     (('R','I'),-3), (('R','K'),2), (('R','L'),-6), (('R','M'),-2),
  676     (('R','N'),-3), (('R','P'),-2), (('R','Q'),0), (('R','R'),8),
  677     (('R','S'),-1), (('R','T'),-4), (('R','V'),-5), (('R','W'),0),
  678     (('R','X'),-3), (('R','Y'),-7), (('R','Z'),-2), (('S','A'),1),
  679     (('S','B'),0), (('S','C'),-1), (('S','D'),-1), (('S','E'),-2),
  680     (('S','F'),-4), (('S','G'),0), (('S','H'),-3), (('S','I'),-4),
  681     (('S','K'),-2), (('S','L'),-6), (('S','M'),-3), (('S','N'),1),
  682     (('S','P'),0), (('S','Q'),-3), (('S','R'),-1), (('S','S'),5),
  683     (('S','T'),2), (('S','V'),-3), (('S','W'),-3), (('S','X'),-1),
  684     (('S','Y'),-5), (('S','Z'),-2), (('T','A'),1), (('T','B'),-1),
  685     (('T','C'),-5), (('T','D'),-2), (('T','E'),-3), (('T','F'),-6),
  686     (('T','G'),-3), (('T','H'),-4), (('T','I'),-1), (('T','K'),-1),
  687     (('T','L'),-4), (('T','M'),-2), (('T','N'),0), (('T','P'),-2),
  688     (('T','Q'),-3), (('T','R'),-4), (('T','S'),2), (('T','T'),6),
  689     (('T','V'),-1), (('T','W'),-8), (('T','X'),-2), (('T','Y'),-4),
  690     (('T','Z'),-3), (('V','A'),-1), (('V','B'),-5), (('V','C'),-4),
  691     (('V','D'),-5), (('V','E'),-4), (('V','F'),-5), (('V','G'),-3),
  692     (('V','H'),-4), (('V','I'),3), (('V','K'),-6), (('V','L'),0),
  693     (('V','M'),0), (('V','N'),-5), (('V','P'),-3), (('V','Q'),-4),
  694     (('V','R'),-5), (('V','S'),-3), (('V','T'),-1), (('V','V'),6),
  695     (('V','W'),-10), (('V','X'),-2), (('V','Y'),-5), (('V','Z'),-4),
  696     (('W','A'),-9), (('W','B'),-7), (('W','C'),-11), (('W','D'),-10),
  697     (('W','E'),-11), (('W','F'),-2), (('W','G'),-10), (('W','H'),-5),
  698     (('W','I'),-9), (('W','K'),-7), (('W','L'),-4), (('W','M'),-8),
  699     (('W','N'),-6), (('W','P'),-9), (('W','Q'),-8), (('W','R'),0),
  700     (('W','S'),-3), (('W','T'),-8), (('W','V'),-10), (('W','W'),13),
  701     (('W','X'),-7), (('W','Y'),-3), (('W','Z'),-10), (('X','A'),-2),
  702     (('X','B'),-2), (('X','C'),-6), (('X','D'),-3), (('X','E'),-3),
  703     (('X','F'),-5), (('X','G'),-3), (('X','H'),-3), (('X','I'),-3),
  704     (('X','K'),-3), (('X','L'),-4), (('X','M'),-3), (('X','N'),-2),
  705     (('X','P'),-3), (('X','Q'),-2), (('X','R'),-3), (('X','S'),-1),
  706     (('X','T'),-2), (('X','V'),-2), (('X','W'),-7), (('X','X'),-3),
  707     (('X','Y'),-5), (('X','Z'),-3), (('Y','A'),-5), (('Y','B'),-4),
  708     (('Y','C'),-2), (('Y','D'),-7), (('Y','E'),-6), (('Y','F'),4),
  709     (('Y','G'),-9), (('Y','H'),-1), (('Y','I'),-4), (('Y','K'),-7),
  710     (('Y','L'),-4), (('Y','M'),-7), (('Y','N'),-3), (('Y','P'),-9),
  711     (('Y','Q'),-8), (('Y','R'),-7), (('Y','S'),-5), (('Y','T'),-4),
  712     (('Y','V'),-5), (('Y','W'),-3), (('Y','X'),-5), (('Y','Y'),9),
  713     (('Y','Z'),-7), (('Z','A'),-1), (('Z','B'),1), (('Z','C'),-9),
  714     (('Z','D'),2), (('Z','E'),5), (('Z','F'),-9), (('Z','G'),-3),
  715     (('Z','H'),1), (('Z','I'),-4), (('Z','K'),-2), (('Z','L'),-4),
  716     (('Z','M'),-3), (('Z','N'),-1), (('Z','P'),-2), (('Z','Q'),5),
  717     (('Z','R'),-2), (('Z','S'),-2), (('Z','T'),-3), (('Z','V'),-4),
  718     (('Z','W'),-10), (('Z','X'),-3), (('Z','Y'),-7), (('Z','Z'),5)]
  719 
  720 -- | Blast defaults, use with gap_open = -5 gap_extend = -3
  721 --   This should really check for valid nucleotides, and perhaps be more
  722 --   lenient in the case of Ns.  Oh well.
  723 blastn_default :: Num a => (Chr,Chr) -> a
  724 blastn_default = simpleMx 1 (-3)
  725 
  726 -- | Construct a simple "matrix" from match score\/mismatch penalty
  727 simpleMx :: (Num a) => a -> a -> (Chr,Chr) -> a
  728 simpleMx match mismatch (x,y) = if x==y || x+32==y || x-32==y
  729                                 then match else mismatch
  730 
  731 {-
  732 -- Helper function for constructing matrices
  733 readMx s = let mx = filter (\l -> not (null l) && head l /= '#') (lines s)
  734                aas = map head $ words (head mx)
  735                row1 r = zipWith (,) (map (\x -> (head $ head r,x)) aas) (map readInt $ tail r)
  736                readInt :: String -> Int
  737                readInt = read
  738            in map (row1 . words) $ tail mx
  739 -}