Dali1d - Dali 1d sequence alignment


Introduction

I have created a stand-alone Java program that performs the 1d sequence alignment described in the Holm and Sander paper: 'Protein structure comparison by alignment of distance matrices', J Mol Biol. 1993 Sep 5;233(1):123-38. This program can be run from the command line with:

java -jar Dali1d.jar PDB-file-1 PDB-file-2 [1d-aligned-file]

as in:

java -jar build/Dali1d.jar data/1LYZ.pdb data/2LZM.pdb

The H&S paper is not as straighforward as the McLachlan paper about 3d alignment, and describes the 1d alignment technique in general terms without being specific about the details of all the steps involved or how they might be implemented. Nevertheless, I think I have a reasonable understanding of the overall process, and have implemented and tested each step fairly well.

Calculating distance matrices

The program calcuates and displays the distance matrices for each protein:

Calculating the similarity of a single pattern

Here is an example of calculating the similarity of 1 pattern in the first matrix compared to all patterns in the second matrix:

This operation compares the pattern contained in the red square with all of the second matrix, and plots the results of the search, correctly locating the similar occurrence in the second matrix. The similarity calculation used is that of eqns 1 and 3 in H&S, limited to positive values only. In the case of eqn 3, an important feature is that the result is dimensionless, so that additional pairs of matched residues can be added to the calculation (based on additional patterns), and the overall similarity score will rise or fall depending on the new residues added. This feature will be used in step 2 to combine similar patterns to create longer sequences of matched residues.

Also note that while in the previous instance the very distinctive pattern in matrix 1 was uniquely discovered in matrix 2, this is not usually the case:

A smaller, off-diagonal pattern produces a more distributed result. In the H&S paper, the pattern size used is 6x6 residues:

Even farther off the diagonal, the pattern produces a more uncertain result:

Comparing all patterns to all patterns

To compare all patterns in matrix 1 with all patterns in matrix 2, all positively correlated patterns are entered into a list. To save time, only those patterns in the lower triangle of each matrix (including the diagonal) will be used, as each matrix is symmetric. A technique used to reduce the number of similarity calculations is to calculate the mean distance of each pattern, sorting them, and then first comparing those patterns with the shortest distances in each matrix. Here is a plot of the mean distance for all 6x6 patterns in matrix 1:

This has the effect of performing a square convolution blur on the matrix. The resulting values can be sorted (black is lowest), and those patterns with the shortest distances compared first.

Here is a screenshot showing the homologous parts (non-red) of the distance matrices for 1LYZ and 2LZM based on the Dali 1d sequence alignment (at bottom). At right are the contiguous reduced matrices (red parts removed) for these two structures, showing the similarity in intra- and intersequence distances for equivalent positions:

To reduce the time spent in looking for similar hexapeptide-hexapeptide patterns between the two matrices, patterns in each matrix are filtered based on their mean intrapattern distances. Here are all patterns up to 10 Angstroms mean distance. This represents 11% of all patterns in matrix 1 and 9% of all patterns in matrix 2:

Up to 15 Angstroms (37% and 28% of all patterns):

Up to 25 Angstroms (the distance used in H&S, which leaves 87% and 69% of all patterns):

Since the number of pattern pairs to compare is based on the product of each set of patterns, the resulting filtered number of comparisons is only 60% of the unfiltered number for a cutoff of 25 A. In addition, before the elastic similarity comparison is performed (which uses the exponential function), the mean intrapattern distances of each pair are checked and the comparison aborted if the mean distance of each pattern is not within -18% to +22% of the mean distance of the other (the elastic similarity score uses a 20% zero threshold value). These two filters result in significant time savings in building the pair similarity list (see below).

Here is an example of running the program up to this point. Initially the 2 proteins are read and distance matrices for each created. Then, the mean intrapattern distance of each hexapeptide-hexapeptide pattern in each matrix is calculated, and the results filtered and sorted according to increasing distances. The first 10, and the last 10, entries are shown for each list of patterns. The first column is the starting position for 1 hexapeptide, the second column is the starting position for another hexapeptide (which is the same as the first for patterns on the diagonal), and the last column is the mean intrapattern distance. Note that the minimum distances are for patterns on the diagonals, and are of the order 4 Angstroms:

[Session started at 2007-06-10 15:09:06 -0700.]
1LYZ.pdb has 129 nodes
2LZM.pdb has 164 nodes
DaliAlign1d.DaliAlign1d: 1LYZ.PDB 2LZM.PDB
Calculating distance matrices
dMat1: 129x129
dMat2: 164x164
Calculating mean distances, threshold = 25.0
0.027 secs
Max1 = 24.996905362269136, 6716 out of 15376
   89    89         4.08364
   90    90         4.14011
   88    88         4.14650
   87    87         4.16585
    3     3         4.20221
    9     9         4.20650
   31    31         4.25014
  110   110         4.25701
   25    25         4.25737
   27    27         4.25838
...
   41     7        24.97055
   66    32        24.98210
  113    85        24.98252
  117    82        24.98335
   75    21        24.98774
  117    49        24.99144
   70    11        24.99405
   61     9        24.99413
   71    25        24.99552
  108    68        24.99691
Max2 = 24.999521434301894, 8803 out of 25281
   18    18         4.16684
  119   119         4.21104
  101   101         4.22916
    6     6         4.23382
   37    37         4.23769
   59    59         4.24111
  150   150         4.24452
   58    58         4.24778
   43    43         4.25311
    2     2         4.25367
...
  138    86        24.97092
   79    26        24.97537
   93    19        24.97740
  158    16        24.98221
  127    70        24.98452
  145    12        24.98976
   34     5        24.99032
  100    53        24.99749
   96    32        24.99817
  111    65        24.99952

Next the pattern pair similarities are calculated, starting with the patterns with the shortest mean distance in each matrix. After each 250 patterns in list 1 are compared with all patterns in list 2 (filtered using the technique described above), the list is sorted according to similarity score, and the number of entries in the list and the maximum and minimum scores in the list are printed. The total number of entries in the list is limited to 80000. After each sort, the list is trimmed to remove those entries with the lowest scores. When all patterns in both lists have been compared, the list is again sorted and trimmed to 40000 entries, and the top and bottom 10 entries are printed. The first 4 columns are the starting positions of 2 hexapeptides in matrix 1 and 2 hexapeptides in matrix 2, and the last column is the pair similarity score. Note that the time to compare all patterns of up to 25 Angstroms mean distance is now under 3 minutes, down from an estimated time of over 80 minutes without filtering:

Calculating pattern list similarities
   250     32499        6.246774        0.001404
   500     56313        6.246774        0.001404
   750     67575        6.246774        0.000215
  1000     79081        6.246774        0.000018
  1250     80000        6.246774        0.492194
  1500     80000        6.246774        0.845179
  1750     80000        6.246774        1.086240
  2000     80000        6.246774        1.238138
  2250     80000        6.246774        1.371546
  2500     80000        6.246774        1.479334
  2750     80000        6.246774        1.572037
  3000     80000        6.246774        1.650233
  3250     80000        6.246774        1.715589
  3500     80000        6.246774        1.764589
  3750     80000        6.246774        1.801670
  4000     80000        6.246774        1.826234
  4250     80000        6.246774        1.846153
  4500     80000        6.246774        1.858496
  4750     80000        6.246774        1.864129
  5000     80000        6.246774        1.868042
  5250     80000        6.246774        1.869864
  5500     80000        6.246774        1.870542
  5750     80000        6.246774        1.870618
  6000     80000        6.246774        1.870632
  6250     80000        6.246774        1.870632
  6500     80000        6.246774        1.870632
40000 entries, 161.547 secs
    6     6    60    60        6.246774
    6     6     3     3        6.181688
    6     6    58    58        6.178696
    8     8   118   118        6.164747
    6     6    65    65        6.128397
    7     7   117   117        6.127541
    7     7     4     4        6.123745
    6     6   116   116        6.119325
    7     6     4     3        6.099487
    6     6    98    98        6.097086
...
  103   103    12    12        2.452708
   28    13   104    66        2.452698
  105   102    63    60        2.452696
   83    81   152   150        2.452658
   96    88   132   124        2.452657
   87    79    52    39        2.452616
   80    77    63    60        2.452588
  108   105    39    36        2.452547
   24     1   144    94        2.452543
   72    68    24    20        2.452523

The previous calculations complete the construction of the pattern similarity list. Next, these pattern pairs are used to build candidate alignments for the 3d structures, by incrementally adding new pattern pairs (in units of tetrapeptides) to a set of several seed alignments consisting of 3 hexapeptide fragments in each protein. To create the seed list, the pair list is scanned for all non-overlapping sets of 3 hexapeptide fragments in each matrix which share common edges in up to 9 different patterns in each matrix. The overall score of each seed is the sum of the scores of all combinations of 3x3 equivalent pairs between each matrix. As new fragments are added to the alignment (or removed), the complexity of the score changes with the square of the number of fragments. Here are the first 10 entries in the seed list, sorted according to overall score. The first 3 columns are the starting positions of 3 hexapeptide fragments in matrix 1, the next 3 columns are the starting points of 3 hexapeptide fragments in matrix 2, and the last column is the overall score:

Scanning for seeds
101 entries, 21.875 secs
   25     9     3    96    75    69       37.156327
   94    87    55    66    59    28       36.891321
   91    10     4   107    72    66       36.887012
   93    87    55    65    59    28       36.880271
   94    88    55    66    60    28       36.824323
   96    90    58    64    58    45       35.456525
   96    90    59    64    58    46       34.980227
   92    86    55    64    58    28       34.941652
   94    86    55    66    58    28       34.773287
   92    86    24   118   112    95       34.715249

Note that there are already commonalities to the different seeds. For example, fragment 94A with 66B, 86A with 58B, 87A with 59B, 88A with 60B, 55A with 28B, etc... The next step is to use the seed list to create new alignment candidates by adding/removing other fragments, while attempting to maximize the score of the overall NxN set of pattern pairs. First, single-fragment alignments are created and expanded from the 3-fragment seeds:

Scanning for singlets
104 entries, 0.0010 secs
   25    96     6        0.000000
    9    75     6        0.000000
    3    69     6        0.000000
   94    66     6        0.000000
   87    59     6        0.000000
   55    28     6        0.000000
   91   107     6        0.000000
   10    72     6        0.000000
    4    66     6        0.000000
   93    65     6        0.000000
Combining singlets
63 entries, 0.0030 secs
   87    59    12       19.600970
    3    69    11       17.767413
   88    38    11       16.266305
   86   112    11       15.854394
   22    65    11       15.667814
   89    93    11       15.572934
   28    98    11       15.403245
   22    92    11       15.381562
   27    94    10       11.988151
   27     3     9       11.628768

2500 alignment candidates are created from the singlets, and these candidates are allowed to 'evolve' according to a straightforward set of rules. Alignments are represented by 3 equivalent data formats:

  1. Strings of 0s and 1s indicating the residues used from each protein in performing the alignment. These strings are also referred to as 'residue pair masks' or just 'masks'.
  2. Arrays of index numbers showing which residues are paired in each protein.
  3. Two sequence strings of residue codes and gaps similar to standard 1d alignment notation.

To save printout space, generally only the first and last format are shown. The initial population is subjected to 200 iterations in which the following steps are performed:

  1. Randomly, 2 of the 25 best alignments are combined by residue pair mask crossover to create a new alignment. This crossover combines sequential parts of the masks of each alignment to create new masks, preserving the number of paired residues (1s).
  2. Each of the new alignnments is subjected to a mutation of the following form with equal probability:
    1. Contiguous bits of each mask are cleared to 0 (i.e. residue pairs are removed from the alignment).
    2. Contiguous bits of each mask are moved from one position to another in the mask.
    3. Contiguous bits of each mask are set to 1 (i.e. residue pairs are added to the alignment).
  3. After each combination and mutation, the list is again sorted, and the best 25 alignments are kept for the next iteration.
  4. If the best scoring alignment in the population does not change for 5 iterations, all 25 best alignments are subjected to 20% 'pair knockout' (i.e. 20% of all bits in each mask are cleared to 0) before the next combination/mutation iteration.
  5. After 200 iterations, the process is stopped and the best alignment over all iterations is returned. Actually, the best alignment is usually produced in <= 100 iterations, so that the additional iterations are generally unnecessary in practice.

Iter   Index  Length  Score
-----  -----  ------  ---------------
0      132    12      19.600970      
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQATNRNTDGSTDYGILQINSRWWCNDGRTPGSRNLCNIPCSALLSSD...........................................................ITASVNCAKKIVSDGNGMNAWVAWRNRCKGTDVQAWIRGCRL.............................................................................................
.......................................................................................MNIFEMLRIDEGLRLKIYKDTEGYYTIGIGHLLTKSPSLNAAKSELDKAIGRNCNGVITKDEAEKLFNQDV..............................DAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQMGETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL
1      583    18      27.569675      
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111000000000000000000011111100000
00000000000000000000000000000000000000000000000000000000000111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000011111100
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQATNRNTDGSTDYGILQINSRWWCNDGRTPGSRNLCNIPCSALLSSD...........................................................ITASVNCAKKIVSDGNGMNAWVAWRNRCKGT.....................................................................................DVQAWIRGCRL..
.......................................................................................MNIFEMLRIDEGLRLKIYKDTEGYYTIGIGHLLTKSPSLNAAKSELDKAIGRNCNGVITKDEAEKLFNQDV...................DAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQMGETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYK.....NL
2      702    24      37.437811      
000000000000000000000000000000000000000000000001111110000000000000000000000000000000000111111111111000000000000001111110000000000
00000000000000000000011111100000000000000000000000000000000111111111111000000000000111111000000000000000000000000000000000000000000000000000000000000000000000000000
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQATNRNT.....................DGSTDYGILQINSRWWCNDGRTPGSRNLCNIPCSALLSSD................................ITASVNCAKKIVSDGNGMNAWVAWRN............RCKGTDVQAWIRGCRL...........................................................................
...............................................MNIFEMLRIDEGLRLKIYKDTEGYYTI..................................GIGHLLTKSPSLNAAKSELDKAIGRNCNGVITKDEAEKLFNQDV..............DAAVRGILRNAKLKPVYD..........SLDAVRRCALINMVFQMGETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL
3      890    31      50.726401      
000000000000000000000000000000000000000000000001111110000000000000000000000001000000000111111111111000000011111100001111110000000
00000000000000000000011111100000000000000000000001000000000111111111111000000000000000000000000000000011111100011111100000000000000000000000000000000000000000000000
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQATNRNT.....................DGSTDYGILQINSRWWCNDGRTPGSRNLCN......................IPCSALLSSD.........ITASVNCAKKIVSDGNGMN...............................AWVAWRNRCK...GTDVQAWIRGCRL...............................................
...............................................MNIFEMLRIDEGLRLKIYKDTEGYYTI........................GIGHLLTKSPSLNAAKSELDKAI.........GRNCNGVITKDEAEKLFNQDV.......DAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQMGE....TGVAGFTNS.......LRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL
4      198    29      58.398926      
000000000000000000000000000000000000000000000001111100011111100000000000000000000000000111111111111000000000000000011111100000000
00000000000000000000011111001111110000000000000000000000000111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111000
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQATNRNT.....................DGSTDYGI..LQINSRWWCNDGRTPGSRNLCNIPCSALLSSD.........................ITASVNCAKKIVSDGNGMNAWVAWRNRC....................................................................................KGTDVQAWIRGCRL...
...............................................MNIFEMLRIDEGLRLKIYKDTEGYYT...IGIGHLLT..........................KSPSLNAAKSELDKAIGRNCNGVITKDEAEKLFNQDV................DAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQMGETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAY........KNL
5      683    36      70.184682      
000000000000000000000000000000000000000000000001111100011111100000000000000001000000000111111111111000000011111100001111110000000
00000000000000000000011111001111110000000000000001000000000111111111111000000000000000000000000000000011111100011111100000000000000000000000000000000000000000000000
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQATNRNT.....................DGSTDYGI..LQINSRWWCNDGRTPGSRNLCN...............IPCSALLSSD.........ITASVNCAKKIVSDGNGMN...............................AWVAWRNRCK...GTDVQAWIRGCRL...............................................
...............................................MNIFEMLRIDEGLRLKIYKDTEGYYT...IGIGHLLT................KSPSLNAAKSELDKAI.........GRNCNGVITKDEAEKLFNQDV.......DAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQMGE....TGVAGFTNS.......LRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL

...etc...

48     100    79      229.679747     
000000000000000000000000111111111111000101111111011111011111100000111111111011000100001111111111111111111111100011111111111110000
11111111111111001111011111111111110011111101101011000000011111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNRN.TDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPCS.......ALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG.YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI...GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
49     810    79      233.081314     
000000000000000000000000111111111111000101111110011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001111001111111111110011111101001111000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNRN..TDGSTDYGILQINSRWWCND..GRTPGS.R..NLCNIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT.....KSPSLNAAKSELDK.AI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
50     419    80      234.713042     
000000000000000000000000111111111111000101111111011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001111011111111111110011111101101011000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNRN.TDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG.YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
51     0      80      234.713042     
000000000000000000000000111111111111000101111111011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001111011111111111110011111101101011000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNRN.TDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG.YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
52     711    79      234.803563     
000000000000000000000000111111111111000101111110011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001110011111111111110011111101101011000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNR..NTDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
53     0      79      234.803563     
000000000000000000000000111111111111000101111110011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001110011111111111110011111101101011000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNR..NTDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
54     0      79      234.803563     
000000000000000000000000111111111111000101111110011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001110011111111111110011111101101011000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNR..NTDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
55     0      79      234.803563     
000000000000000000000000111111111111000101111110011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001110011111111111110011111101101011000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNR..NTDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
56     0      79      234.803563     
000000000000000000000000111111111111000101111110011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001110011111111111110011111101101011000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNR..NTDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
57     0      79      234.803563     
000000000000000000000000111111111111000101111110011111011111100000111111111011001100001111111111111111111111100011111111111110000
11111111111111001110011111111111110011111101101011000000111111111111111111100000000000000000000000011101110000000000000000000000000000000000000011011110000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA..TNR..NTDGSTDYGILQINSRWWCND..GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR......................................NR.CKGT.....DVQAWIRGCRL.
........................MNIFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT.....KSPSLNAAKSELD.KAI..GRNCNGVI....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L

The best alignment has not changed for 5 iterations, so all parents are trimmed and evolution continues:

58     870    64      38.388020      
000000000000000000000000011111101111000100110110011101001011100000110110111011001100001001101101111111111100100011111111111110000
11011110111011000111001111100011110011111100001101000000110101111110101111100000000000000000000000011101010000000000000000000000000000000000000011011110000011110110
KVFGRCELAAAMKRHGLDNYRGYSLGN.WVCAA.KFE.SNFNTQA...TNRN..TDGSTDYGIL...QINSRWWCND..GRTPGSRN....LCN.IPC......SALLSS.DIT.ASVNCAKK.I.VSDGN........................GMNAW.VAWR.N......................................RC.KGTD.....VQAW.IRGCRL.
.........................MNIFEML.RIDEGL...R..LKIYK.DTEG..YYT.I..GIGH.LLT.....KSPS.LN.AAKSELD.KAI..GRNCNGVI....TK..DEA.EK.LFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINM..VF...QMGETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKN....L
59     601    66      62.240708      
000000000000000000000000111011111111000100111010010110010111100000100111110001001100001111111111111001111111100011111111101110000
11110101111111000101001111010111110000011111100011000000011110111111111110100000000000000000000000011101110000000000000000000000000000000000000011011110000001111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWV.C.AAKFESNFNTQA...T.N..RNTDGSTD.YGI.LQINSRWWCND.....GRTPGSRNLCN...IPCS.......ALLSSDIT.ASVNCAKKIVSDG.N........................GMN.AWVAWR......................................NR.CKGT......DVQAWIRGCRL.
........................MNI.FEMLRIDEGL...R..LKIYKDTEG.Y..Y.TIG..IG.HLLT.....KSPSLN..AAKSE...LDKA..IGRNCNGVI....TKDEAEKLFNQDVD..AAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDA.YKN....L
60     926    66      87.598664      
000000000000000000000000011111101111000100110110011101001011100000110110111011001100001111111110111001111111100011111111101110000
11011111111011001010001101110011110000111101101011000000111111111110101111100000000000000000000000011101010000000000000000000000000000000000000011011110000001111110
KVFGRCELAAAMKRHGLDNYRGYSLGN.WVCAAKFESNFN.TQAT..NR.N...TDGS.TDYGIL..QINSRWWCND....GRTPGS.RN.LC.NIPC......SALLSSDITASVNCAK.K.IVSDGNG........................MNA.W.VAWR......................................NR.CKGT......DVQAWIRGCRL.
.........................MNIFEML.RIDE...GL..RLKI.YKDTEG..YYTI.G..IGH.LLT.....KSPSLN.AA.KSELD.KAI..GRNCNGVI....TKDEAEKLF.NQDVD..AAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDA.YKN....L
61     98     71      108.778177     
000000000000000000000000011111101111000101111110001111010111100000111111011011001100001111111111111001111111100011111111101110000
11011110111111000111011111010111110000111101101011000000111111111111111110100000000000000000000000011101110000000000000000000000000000000000000011011110000001111110
KVFGRCELAAAMKRHGLDNYRGYSLGN.WVCAA.KFESNFNTQA...TNR.NTDGSTDY.GI.LQINSRWWCND....GRTP.GSR.N.LCN......IPCSALLSSDITASVNCAKKIVSDG.N........................GMN.AWVAWR......................................NR.CKGT......DVQAWIRGCRL.
.........................MNIFEML.RIDEG...L.RLKIYKDTEG...YYTIG.IG.HLLT.....KSPSLNAAKSE.LDKA.IGRNCNGV..IT....KDEAEKLFNQDVD..AAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDA.YKN....L
62     741    71      140.693675     
000000000000000000000000011111101111000101111110001111010111100000111111011011001100001111111111111001111111100011111111101110000
11011110111111000111011111010111110000111101101011100000111111111111111100100000000000000000000000011101110000000000000000000000000000000000000011011110000001111110
KVFGRCELAAAMKRHGLDNYRGYSLGN.WVCAA.KFESNFNTQA...TNR.NTDGSTDY.GI.LQINSRWWCND....GRTP.GSR.N.LCNIPC.....SALLSSDITASVNCAKKIVSDG..N........................GMN.AWVAWR......................................NR.CKGT......DVQAWIRGCRL.
.........................MNIFEML.RIDEG...L.RLKIYKDTEG...YYTIG.IG.HLLT.....KSPSLNAAKSE.LDKA.IG..RNCNGVI....TKDEAEKLFNQDV..DAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDA.YKN....L

...etc...

000000000000000000000001101111111111000101111110011111011111100000011111110011101000001111111111111111111111100010011111111110000
11111111111111000111011111111111110001111101100011000001011111111111111111100000000000000000000000011011110000000000000000000000000000000000000001001101000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA...TNR.NTDGSTDYGILQINSRWWCNDG...RTPGS.RNLC...NI.....PC.SALLSSDITASVNCAKKIVSDGN........................GM.NAWVAWR.......................................NRC..KG.T....DVQAWIRGCRL.
.......................MN.IFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT......KSPSLNAAKSE..LDKAIGRNCNG.VI.....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRA..KRVITTFRTGTWDAYKN....L
197    0      75      227.316548     
000000000000000000000001101111111111000101111110011111011111100000011111110011101000001111111111111111111111100010011111111110000
11111111111111000111011111111111110001111101100011000001011111111111111111100000000000000000000000011011110000000000000000000000000000000000000001001101000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA...TNR.NTDGSTDYGILQINSRWWCNDG...RTPGS.RNLC...NI.....PC.SALLSSDITASVNCAKKIVSDGN........................GM.NAWVAWR.......................................NRC..KG.T....DVQAWIRGCRL.
.......................MN.IFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT......KSPSLNAAKSE..LDKAIGRNCNG.VI.....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRA..KRVITTFRTGTWDAYKN....L
198    839    77      228.382324     
000000000000000000000001101111111111000101111110011111011111100000011111111011101000101111111111111111111111100010011111111110000
11111111111111000111011111111111110001111101110011000001111111111111111111100000000000000000000000011011110000000000000000000000000000000000000001001101000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA...TNR.NTDGSTDYGILQINSRWWCNDG...RTPGS.RNLC..NI.....PCSALLSSDITASVNCAKKIVSDGN........................GM.NAWVAWR.......................................NRC..KG.T....DVQAWIRGCRL.
.......................MN.IFEMLRIDEG...L.RLKIYKDTEG..YYTIG.IGHLLT......KSPSLNAAKSEL.DKAIGRNCNG.V...I.TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRA..KRVITTFRTGTWDAYKN....L
199    831    74      230.148052     
000000000000000000000001101111111111000101011110011111011111100000011111110011101000001111111111111111111111100010011111111110000
11111111111111000110011111111111110001111101100011000001011111111111111111100000000000000000000000011011110000000000000000000000000000000000000001001101000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQAT...NR..NTDGSTDYGILQINSRWWCNDG...RTPGS.RNLC...NI.....PC.SALLSSDITASVNCAKKIVSDGN........................GM.NAWVAWR.......................................NRC..KG.T....DVQAWIRGCRL.
.......................MN.IFEMLRIDEG...L.R.LKIYKDTEG..YYTIG.IGHLLT......KSPSLNAAKSE..LDKAIGRNCNG.VI.....TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRA..KRVITTFRTGTWDAYKN....L
200    294    75      232.735970     
000000000000000000000001101111111111000101011110011111011111100000011111110011101000101111111111111111111111100010011111111110000
11111111111111000110011111111111110001111101100011000001111111111111111111100000000000000000000000011011110000000000000000000000000000000000000010001101000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQAT...NR..NTDGSTDYGILQINSRWWCNDG...RTPGS.RNLC...NI.....PCSALLSSDITASVNCAKKIVSDGN........................GM.NAWVAWR......................................NRC...KG.T....DVQAWIRGCRL.
.......................MN.IFEMLRIDEG...L.R.LKIYKDTEG..YYTIG.IGHLLT......KSPSLNAAKSE..LDKAIGRNCNG.V...I.TKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNR..AKRVITTFRTGTWDAYKN....L

Iterations are stopped, and the best alignment over all is returned:

***** Best result:  75      243.592558     
000000000000000000000001101111111111000101011100011111011111100000111111111011001100001111111111111111011111100011011111111110000
11111111111111000110001111111111110011111011100111000000111111111111111110100000000000000000000000011011110000000000000000000000000000000000000011001101000011111110
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQAT...NR...NTDGSTDYGILQINSRWWCND..GRTPG.SRN..LCNIPC......SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NRC..KG.T....DVQAWIRGCRL.
.......................MN.IFEMLRIDEG...L.R.LKIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AI..GRNCNGVI....TKDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRA.KRVITTFRTGTWDAYKN....L

Total time: 348.823 secs
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQAT---NR---NTDGSTDYGILQINSRWWCND--GRTPG-SRN--LCNIPC------SALLSSDITASVNCAKKIVSD-GN------------------------GM-NAWVAWR--------------------------------------NRC--KG-T----DVQAWIRGCRL-
-----------------------MN-IFEMLRIDEG---L-R-LKIYKDTEG---YYTIG-IGHLLT-----KSPSLNAAKSELDK-AI--GRNCNGVI----TKDEAEKLFNQDVDAAV-RGILRNAKLKPVYDSLDAVRRCALINMVFQM---GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRA-KRVITTFRTGTWDAYKN----L

Program run-times are on the order of 3-10 minutes on a MacBook, depending on the parameters used, which is pretty good for a Java program. Longer runs generally produce better results, while shorter runs can be used to quickly examine the space of possible alignments. The resulting 1d alignment can then be used to perform a 3d alignment:

1LYZ has 129 nodes
2LZM has 164 nodes
2LZM has 75 links to 1LYZ
2LZM       center at       40.880933       -8.357147       15.104293
1LYZ       center at        0.871867       21.397107       21.101840
Initial error =       16.322712
    1        3.956975
    2        3.773326
    3        3.747428
    4        3.747418
    5        3.747418
    6        3.747418
    7        3.747418
    8        3.747418
    9        3.747418
   10        3.747418
   11        3.747418
   12        3.747418
   13        3.747418
   14        3.747418
   15        3.747418
   16        3.747418
   17        3.747418
   18        3.747418
Rotation matrix:
       0.574672        0.768853       -0.280385 
      -0.552787        0.112039       -0.825756 
      -0.603472        0.629533        0.489398 

Here are the final results from 6 different runs performed on 1LYZ and 2LZM. The output shows length, score, masks, indices, and sequences:

***** Best result:  79      247.519583     
000000000000000000000001101111111111001110111100011111011111100000111111111011101100100111111111111111111111100011111110111110000
11111111111111101110001111111111110011111101100111000100111111111111111111100000000000000000000000011011110000000000000000000000000000000000000011011111000001101110
23  24  26  27  28  29  30  31  32  33  34  35  38  39  40  42  43  44  45  49  50  51  52  53  55  56  57  58  59  60  66  67  68  69  70  71  72  73  74  76  77  78  80  81  84  87  88  89  90  91  92  93  94  95  96  97  98  99  100 101 102 103 104 105 106 107 108 112 113 114 115 116 117 118 120 121 122 123 124 
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  16  17  18  22  23  24  25  26  27  28  29  30  31  32  33  36  37  38  39  40  41  43  44  47  48  49  53  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  99  100 102 103 104 105 144 145 147 148 149 150 151 157 158 160 161 162 
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSDGN........................GM.NAWVAWR......................................NR.CKGTDV.....QA.WIRGCRL.
.......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITT.FRTGTWDAYKN....L

***** Best result:  77      247.010420     
000000000000000000000001101111111111001110111100011111011111100000111111111011101100100111111111111111011111100011111111111000000
11111111111111101110001111111111110011111101100111000100111111111111111110100000000000000000000000011011110000000000000000000000000000000000000011011001000001101111
23  24  26  27  28  29  30  31  32  33  34  35  38  39  40  42  43  44  45  49  50  51  52  53  55  56  57  58  59  60  66  67  68  69  70  71  72  73  74  76  77  78  80  81  84  87  88  89  90  91  92  93  94  95  96  97  98  99  100 101 103 104 105 106 107 108 112 113 114 115 116 117 118 119 120 121 122 
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  16  17  18  22  23  24  25  26  27  28  29  30  31  32  33  36  37  38  39  40  41  43  44  47  48  49  53  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  74  99  100 102 103 104 105 144 145 147 148 151 157 158 160 161 162 163 
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NR.CK..G.....TD.VQAWIRGCRL
.......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL......

***** Best result:  77      247.010420     
000000000000000000000001101111111111001110111100011111011111100000111111111011101100100111111111111111011111100011111111111000000
11111111111111101110001111111111110011111101100111000100111111111111111110100000000000000000000000011011110000000000000000000000000000000000000011011001000001101111
23  24  26  27  28  29  30  31  32  33  34  35  38  39  40  42  43  44  45  49  50  51  52  53  55  56  57  58  59  60  66  67  68  69  70  71  72  73  74  76  77  78  80  81  84  87  88  89  90  91  92  93  94  95  96  97  98  99  100 101 103 104 105 106 107 108 112 113 114 115 116 117 118 119 120 121 122 
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  16  17  18  22  23  24  25  26  27  28  29  30  31  32  33  36  37  38  39  40  41  43  44  47  48  49  53  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  74  99  100 102 103 104 105 144 145 147 148 151 157 158 160 161 162 163 
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NR.CK..G.....TD.VQAWIRGCRL
.......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL......

***** Best result:  77      240.223119     
000000000000000001100010101110110011000111111100011111011111100000111111111011101100100111111111111111111111100011111111111000000
11101110111111111110001111111111110011111101100111000100111111111111111111100000000000000000000000011101110000000000000000000000000000000000010111110000000000011111
17  18  22  24  26  27  28  30  31  34  35  39  40  41  42  43  44  45  49  50  51  52  53  55  56  57  58  59  60  66  67  68  69  70  71  72  73  74  76  77  78  80  81  84  87  88  89  90  91  92  93  94  95  96  97  98  99  100 101 102 103 104 105 106 107 108 112 113 114 115 116 117 118 119 120 121 122 
0   1   2   4   5   6   8   9   10  11  12  13  14  15  16  17  18  22  23  24  25  26  27  28  29  30  31  32  33  36  37  38  39  40  41  43  44  47  48  49  53  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73  74  99  100 101 103 104 105 141 143 144 145 146 147 159 160 161 162 163 
KVFGRCELAAAMKRHGLDNYRGYS.LGNW.VCAAKFESNFNTQATNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR...................................N.RCKGT...........DVQAWIRGCRL
.................MN...I.FE.MLRI.DE..GL...RLKIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL......

***** Best result:  78      247.731373     
000000000000000000000001101111111111001110111100011111011111100000111111111011101100100111111111111111011111100011111110111110000
11111111111111101110001111111111110011111101100111000100111111111111111110100000000000000000000000011011110000000000000000000000000000000000000011011111000001101110
23  24  26  27  28  29  30  31  32  33  34  35  38  39  40  42  43  44  45  49  50  51  52  53  55  56  57  58  59  60  66  67  68  69  70  71  72  73  74  76  77  78  80  81  84  87  88  89  90  91  92  93  94  95  96  97  98  99  100 101 103 104 105 106 107 108 112 113 114 115 116 117 118 120 121 122 123 124 
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  16  17  18  22  23  24  25  26  27  28  29  30  31  32  33  36  37  38  39  40  41  43  44  47  48  49  53  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  74  99  100 102 103 104 105 144 145 147 148 149 150 151 157 158 160 161 162 
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NR.CKGTDV.....QA.WIRGCRL.
.......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITT.FRTGTWDAYKN....L

***** Best result:  78      247.731373     
000000000000000000000001101111111111001110111100011111011111100000111111111011101100100111111111111111011111100011111110111110000
11111111111111101110001111111111110011111101100111000100111111111111111110100000000000000000000000011011110000000000000000000000000000000000000011011111000001101110
23  24  26  27  28  29  30  31  32  33  34  35  38  39  40  42  43  44  45  49  50  51  52  53  55  56  57  58  59  60  66  67  68  69  70  71  72  73  74  76  77  78  80  81  84  87  88  89  90  91  92  93  94  95  96  97  98  99  100 101 103 104 105 106 107 108 112 113 114 115 116 117 118 120 121 122 123 124 
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  16  17  18  22  23  24  25  26  27  28  29  30  31  32  33  36  37  38  39  40  41  43  44  47  48  49  53  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  74  99  100 102 103 104 105 144 145 147 148 149 150 151 157 158 160 161 162 
KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NR.CKGTDV.....QA.WIRGCRL.
.......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITT.FRTGTWDAYKN....L

Here are the residue sequences of these runs compared to the optimal Dali server output:

DS: KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQATNRNTDGSTDYGILQINSRWWCNDGRT.PGSRNLCNIPCSALLSSDITASVNCAKKIVSD........................GNGMNAWV.....................................AWRNRCKGT........DVQAWIRGCRL
    ........................MNIFEMLRIDEG..LRLKIYKDTEGYYTIG.IGHLLTKSPSLNAAKSELDKAIG..RNCNGVITKDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQMGETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL......

1:  KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSDGN........................GM.NAWVAWR......................................NR.CKGTDV.....QA.WIRGCRL.
    .......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITT.FRTGTWDAYKN....L
2:  KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NR.CK..G.....TD.VQAWIRGCRL
    .......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL......
3:  KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NR.CK..G.....TD.VQAWIRGCRL
    .......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL......
4:  KVFGRCELAAAMKRHGLDNYRGYS.LGNW.VCAAKFESNFNTQATNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSDGN........................GMN.AWVAWR...................................N.RCKGT...........DVQAWIRGCRL
    .................MN...I.FE.MLRI.DE..GL...RLKIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAVRGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITTFRTGTWDAYKNL......
5:  KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NR.CKGTDV.....QA.WIRGCRL.
    .......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITT.FRTGTWDAYKN....L
6:  KVFGRCELAAAMKRHGLDNYRGYSLGNWVCAAKFESNFNTQA.TNR...NTDGSTDYGILQINSRWWCND..GRTPGS.RN..LCNI...PC..SALLSSDITASVNCAKKIVSD.GN........................GM.NAWVAWR......................................NR.CKGTDV.....QA.WIRGCRL.
    .......................MN.IFEMLRIDEG..LRL.KIYKDTEG...YYTIG.IGHLLT.....KSPSLNAAKSELDK.AIGRNC.NGVI..T..KDEAEKLFNQDVDAAV.RGILRNAKLKPVYDSLDAVRRCALINMVFQM...GETGVAGFTNSLRMLQQKRWDEAAVNLAKSRWYNQTPNRAKRVITT.FRTGTWDAYKN....L

Here are the RMSD values obtained from 3d alignment of 1LYZ and 2LZM using these 1d alignments:

DS: 5.485784

1:  3.710317
2:  3.607497
3:  3.607497
4:  3.756042
5:  3.700215
6:  3.700215

It's interesting to note that while the Dali server produces an alignment with a better H&S similarity score, the final 3d RMSD values are better for alignments from the Java program.


© 2007 Sky Coyote