forked from pylelab/USalign
-
Notifications
You must be signed in to change notification settings - Fork 0
/
USalign.cpp
3318 lines (3122 loc) · 141 KB
/
USalign.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* command line argument parsing and document of US-align main program */
#include "MMalign.h"
#include "SOIalign.h"
#include "flexalign.h"
using namespace std;
void print_version()
{
cout <<
"\n"
" ********************************************************************\n"
" * US-align (Version 20230609) *\n"
" * Universal Structure Alignment of Proteins and Nucleic Acids *\n"
" * Reference: C Zhang, M Shine, AM Pyle, Y Zhang. (2022) Nat Methods*\n"
" * Please email comments and suggestions to zhang@zhanggroup.org *\n"
" ********************************************************************"
<< endl;
}
void print_extra_help()
{
cout <<
"Additional options:\n"
" -v Print the version of US-align\n"
"\n"
" -a TM-score normalized by the average length of two structures\n"
" T or F, (default F). -a does not change the final alignment.\n"
"\n"
" -fast Fast but slightly inaccurate alignment\n"
"\n"
" -dir Perform all-against-all alignment among the list of PDB\n"
" chains listed by 'chain_list' under 'chain_folder'.\n"
" $ USalign -dir chain_folder/ chain_list\n"
"\n"
//"-dirpair Perform batch alignment for each pair of chains listed by\n"
//" 'chain_pair_list' under 'chain_folder'. Each line consist of\n"
//" two chains, separated by tab or space.\n"
//" $ USalign -dirpair chain_folder/ chain_pair_list\n"
//"\n"
" -dir1 Use chain2 to search a list of PDB chains listed by 'chain1_list'\n"
" under 'chain1_folder'.\n"
" $ USalign -dir1 chain1_folder/ chain1_list chain2\n"
"\n"
" -dir2 Use chain1 to search a list of PDB chains listed by 'chain2_list'\n"
" under 'chain2_folder'\n"
" $ USalign chain1 -dir2 chain2_folder/ chain2_list\n"
"\n"
" -suffix (Only when -dir1 and/or -dir2 are set, default is empty)\n"
" add file name suffix to files listed by chain1_list or chain2_list\n"
"\n"
" -atom 4-character atom name used to represent a residue.\n"
" Default is \" C3'\" for RNA/DNA and \" CA \" for proteins\n"
" (note the spaces before and after CA).\n"
"\n"
" -split Whether to split PDB file into multiple chains\n"
" 0: treat the whole structure as one single chain\n"
" 1: treat each MODEL as a separate chain\n"
" 2: (default) treat each chain as a separate chain\n"
"\n"
" -outfmt Output format\n"
" 0: (default) full output\n"
" 1: fasta format compact output\n"
" 2: tabular format very compact output\n"
" -1: full output, but without version or citation information\n"
"\n"
" -TMcut -1: (default) do not consider TMcut\n"
" Values in [0.5,1): Do not proceed with TM-align for this\n"
" structure pair if TM-score is unlikely to reach TMcut.\n"
" TMcut is normalized as set by -a option:\n"
" -2: normalized by longer structure length\n"
" -1: normalized by shorter structure length\n"
" 0: (default, same as F) normalized by second structure\n"
" 1: same as T, normalized by average structure length\n"
"\n"
" -mirror Whether to align the mirror image of input structure\n"
" 0: (default) do not align mirrored structure\n"
" 1: align mirror of Structure_1 to origin Structure_2,\n"
" which usually requires the '-het 1' option:\n"
" $ USalign 4glu.pdb 3p9w.pdb -mirror 1 -het 1\n"
"\n"
" -het Whether to align residues marked as 'HETATM' in addition to 'ATOM '\n"
" 0: (default) only align 'ATOM ' residues\n"
" 1: align both 'ATOM ' and 'HETATM' residues\n"
" 2: align both 'ATOM ' and MSE residues\n"
"\n"
" -full Whether to show full pairwise alignment of individual chains for\n"
" -mm 2 or 4. T or F, (default F)\n"
//"\n"
//" -closeK Number of closest atoms used for sequence order independent\n"
//" initial alignment. default: 5\n"
//"\n"
//" -hinge Maximum number of hinge allowed in flexible alignment. default: 9\n"
"\n"
" -se Do not perform superposition. Useful for extracting alignment from\n"
" superposed structure pairs\n"
"\n"
" -infmt1 Input format for structure_1\n"
" -infmt2 Input format for structure_2\n"
" -1: (default) automatically detect PDB or PDBx/mmCIF format\n"
" 0: PDB format\n"
" 1: SPICKER format\n"
//" 2: xyz format\n"
" 3: PDBx/mmCIF format\n"
"\n"
//"-chainmap (only useful for -mm 1) use the final chain mapping 'chainmap.txt'\n"
//" specified by user. 'chainmap.txt' is a tab-seperated text with two\n"
//" columns, one for each complex\n"
//"\n"
"Advanced usage 1 (generate an image for a pair of superposed structures):\n"
" USalign 1cpc.pdb 1mba.pdb -o sup\n"
" pymol -c -d @sup_all_atm.pml -g sup_all_atm.png\n"
"\n"
"Advanced usage 2 (a quick search of query.pdb against I-TASSER PDB library):\n"
" wget https://zhanggroup.org/library/PDB.tar.bz2\n"
" tar -xjvf PDB.tar.bz2\n"
" USalign query.pdb -dir2 PDB/ PDB/list -suffix .pdb -outfmt 2 -fast\n"
<<endl;
}
void print_help(bool h_opt=false)
{
print_version();
cout <<
"\n"
"Usage: USalign PDB1.pdb PDB2.pdb [Options]\n"
"\n"
"Options:\n"
" -mol Type of molecule(s) to align.\n"
" auto: (default) align both protein and nucleic acids.\n"
" prot: only align proteins in a structure.\n"
" RNA : only align RNA and DNA in a structure.\n"
"\n"
" -mm Multimeric alignment option:\n"
" 0: (default) alignment of two monomeric structures\n"
" 1: alignment of two multi-chain oligomeric structures\n"
" 2: alignment of individual chains to an oligomeric structure\n"
" $ USalign -dir1 monomers/ list oligomer.pdb -ter 0 -mm 2\n"
" 3: alignment of circularly permuted structure\n"
" 4: alignment of multiple monomeric chains into a consensus alignment\n"
" $ USalign -dir chains/ list -suffix .pdb -mm 4\n"
" 5: fully non-sequential (fNS) alignment\n"
" 6: semi-non-sequential (sNS) alignment\n"
" To use -mm 1 or -mm 2, '-ter' option must be 0 or 1.\n"
"\n"
" -ter Number of chains to align.\n"
" 3: only align the first chain, or the first segment of the\n"
" first chain as marked by the 'TER' string in PDB file\n"
" 2: (default) only align the first chain\n"
" 1: align all chains of the first model (recommended for aligning\n"
" asymmetric units)\n"
" 0: align all chains from all models (recommended for aligning\n"
" biological assemblies, i.e. biounits)\n"
"\n"
" -TMscore Whether to perform TM-score superposition without structure-based\n"
" alignment. The same as -byresi.\n"
" 0: (default) sequence independent structure alignment\n"
" 1: superpose two structures by assuming that a pair of residues\n"
" with the same residue index are equivalent between the two\n"
" structures\n"
" 2: superpose two complex structures, assuming that a pair of\n"
" residues with the same residue index and the same chain ID\n"
" are equivalent between the two structures\n"
//" 3: (similar to TMscore '-c' option; used with -ter 0 or 1)\n"
//" align by residue index and order of chain\n"
//" 4: sequence dependent alignment: perform Needleman-Wunsch\n"
//" global sequence alignment, followed by TM-score superposition\n"
" 5: sequence dependent alignment: perform glocal sequence\n"
" alignment followed by TM-score superposition.\n"
" -byresi 5 is the same as -seq\n"
" 6: superpose two complex structures by first deriving optimal\n"
" chain mapping, followed by TM-score superposition for residues\n"
" with the same residue ID\n"
" 7: sequence dependent alignment of two complex structures:\n"
" perform global sequence alignment of each chain pair, derive\n"
" optimal chain mapping, and then superpose two complex\n"
" structures by TM-score\n"
"\n"
" -I Use the final alignment specified by FASTA file 'align.txt'\n"
"\n"
" -i Use alignment specified by 'align.txt' as an initial alignment\n"
"\n"
" -m Output rotation matrix for superposition\n"
"\n"
" -d TM-score scaled by an assigned d0, e.g., '-d 3.5' reports MaxSub\n"
" score, where d0 is 3.5 Angstrom. -d does not change final alignment.\n"
"\n"
" -u TM-score normalized by an assigned length. It should be >= length\n"
" of protein to avoid TM-score >1. -u does not change final alignment.\n"
"\n"
" -o Output superposed structure1 to sup.* for PyMOL viewing.\n"
" $ USalign structure1.pdb structure2.pdb -o sup\n"
" $ pymol -d @sup.pml # C-alpha trace aligned region\n"
" $ pymol -d @sup_all.pml # C-alpha trace whole chain\n"
" $ pymol -d @sup_atm.pml # full-atom aligned region\n"
" $ pymol -d @sup_all_atm.pml # full-atom whole chain\n"
" $ pymol -d @sup_all_atm_lig.pml # full-atom with all molecules\n"
"\n"
" -rasmol Output superposed structure1 to sup.* for RasMol viewing.\n"
" $ USalign structure1.pdb structure2.pdb -rasmol sup\n"
" $ rasmol -script sup # C-alpha trace aligned region\n"
" $ rasmol -script sup_all # C-alpha trace whole chain\n"
" $ rasmol -script sup_atm # full-atom aligned region\n"
" $ rasmol -script sup_all_atm # full-atom whole chain\n"
" $ rasmol -script sup_all_atm_lig # full-atom with all molecules\n"
"\n"
//" -h Print the full help message, including additional options\n"
//"\n"
"Example usages ('gunzip' program is needed to read .gz compressed files):\n"
" USalign 101m.cif.gz 1mba.pdb # pairwise monomeric protein alignment\n"
" USalign 1qf6.cif 5yyn.pdb.gz -mol RNA # pairwise monomeric RNA alignment\n"
" USalign model.pdb native.pdb -TMscore 1 # calculate TM-score between two conformations of a monomer\n"
" USalign 4v4a.cif 4v49.cif -mm 1 -ter 1 # oligomeric alignment for asymmetic units\n"
" USalign 3ksc.pdb1 4lej.pdb1 -mm 1 -ter 0 # oligomeric alignment for biological units\n"
" USalign 1ajk.pdb.gz 2ayh.pdb.gz -mm 3 # circular permutation alignment\n"
<<endl;
//if (h_opt)
print_extra_help();
exit(EXIT_SUCCESS);
}
/* TMalign, RNAalign, CPalign, TMscore */
int TMalign(string &xname, string &yname, const string &fname_super,
const string &fname_lign, const string &fname_matrix,
vector<string> &sequence, const double Lnorm_ass, const double d0_scale,
const bool m_opt, const int i_opt, const int o_opt, const int a_opt,
const bool u_opt, const bool d_opt, const double TMcut,
const int infmt1_opt, const int infmt2_opt, const int ter_opt,
const int split_opt, const int outfmt_opt, const bool fast_opt,
const int cp_opt, const int mirror_opt, const int het_opt,
const string &atom_opt, const bool autojustify, const string &mol_opt,
const string &dir_opt, const string &dirpair_opt, const string &dir1_opt,
const string &dir2_opt, const int byresi_opt, const vector<string> &chain1_list,
const vector<string> &chain2_list, const bool se_opt)
{
/* declare previously global variables */
vector<vector<string> >PDB_lines1; // text of chain1
vector<vector<string> >PDB_lines2; // text of chain2
vector<int> mol_vec1; // molecule type of chain1, RNA if >0
vector<int> mol_vec2; // molecule type of chain2, RNA if >0
vector<string> chainID_list1; // list of chainID1
vector<string> chainID_list2; // list of chainID2
int i,j; // file index
int chain_i,chain_j; // chain index
int r; // residue index
int xlen, ylen; // chain length
int xchainnum,ychainnum;// number of chains in a PDB file
char *seqx, *seqy; // for the protein sequence
char *secx, *secy; // for the secondary structure
double **xa, **ya; // for input vectors xa[0...xlen-1][0..2] and
// ya[0...ylen-1][0..2], in general,
// ya is regarded as native structure
// --> superpose xa onto ya
vector<string> resi_vec1; // residue index for chain1
vector<string> resi_vec2; // residue index for chain2
int read_resi=byresi_opt; // whether to read residue index
if (byresi_opt==0 && o_opt) read_resi=2;
/* loop over file names */
for (i=0;i<chain1_list.size();i++)
{
/* parse chain 1 */
xname=chain1_list[i];
xchainnum=get_PDB_lines(xname, PDB_lines1, chainID_list1, mol_vec1,
ter_opt, infmt1_opt, atom_opt, autojustify, split_opt, het_opt);
if (!xchainnum)
{
cerr<<"Warning! Cannot parse file: "<<xname
<<". Chain number 0."<<endl;
continue;
}
for (chain_i=0;chain_i<xchainnum;chain_i++)
{
xlen=PDB_lines1[chain_i].size();
if (mol_opt=="RNA") mol_vec1[chain_i]=1;
else if (mol_opt=="protein") mol_vec1[chain_i]=-1;
if (!xlen)
{
cerr<<"Warning! Cannot parse file: "<<xname
<<". Chain length 0."<<endl;
continue;
}
else if (xlen<3)
{
cerr<<"Sequence is too short <3!: "<<xname<<endl;
continue;
}
NewArray(&xa, xlen, 3);
seqx = new char[xlen + 1];
secx = new char[xlen + 1];
xlen = read_PDB(PDB_lines1[chain_i], xa, seqx,
resi_vec1, read_resi);
if (mirror_opt) for (r=0;r<xlen;r++) xa[r][2]=-xa[r][2];
if (mol_vec1[chain_i]>0) make_sec(seqx,xa, xlen, secx,atom_opt);
else make_sec(xa, xlen, secx); // secondary structure assignment
for (j=(dir_opt.size()>0)*(i+1);j<chain2_list.size();j++)
{
if (dirpair_opt.size() && j!=i) continue;
/* parse chain 2 */
if (PDB_lines2.size()==0)
{
yname=chain2_list[j];
ychainnum=get_PDB_lines(yname, PDB_lines2, chainID_list2,
mol_vec2, ter_opt, infmt2_opt, atom_opt, autojustify,
split_opt, het_opt);
if (!ychainnum)
{
cerr<<"Warning! Cannot parse file: "<<yname
<<". Chain number 0."<<endl;
continue;
}
}
for (chain_j=0;chain_j<ychainnum;chain_j++)
{
ylen=PDB_lines2[chain_j].size();
if (mol_opt=="RNA") mol_vec2[chain_j]=1;
else if (mol_opt=="protein") mol_vec2[chain_j]=-1;
if (!ylen)
{
cerr<<"Warning! Cannot parse file: "<<yname
<<". Chain length 0."<<endl;
continue;
}
else if (ylen<3)
{
cerr<<"Sequence is too short <3!: "<<yname<<endl;
continue;
}
NewArray(&ya, ylen, 3);
seqy = new char[ylen + 1];
secy = new char[ylen + 1];
ylen = read_PDB(PDB_lines2[chain_j], ya, seqy,
resi_vec2, read_resi);
if (mol_vec2[chain_j]>0)
make_sec(seqy, ya, ylen, secy, atom_opt);
else make_sec(ya, ylen, secy);
if (byresi_opt) extract_aln_from_resi(sequence,
seqx,seqy,resi_vec1,resi_vec2,byresi_opt);
/* declare variable specific to this pair of TMalign */
double t0[3], u0[3][3];
double TM1, TM2;
double TM3, TM4, TM5; // for a_opt, u_opt, d_opt
double d0_0, TM_0;
double d0A, d0B, d0u, d0a;
double d0_out=5.0;
string seqM, seqxA, seqyA;// for output alignment
double rmsd0 = 0.0;
int L_ali; // Aligned length in standard_TMscore
double Liden=0;
double TM_ali, rmsd_ali; // TMscore and rmsd in standard_TMscore
int n_ali=0;
int n_ali8=0;
bool force_fast_opt=(getmin(xlen,ylen)>1500)?true:fast_opt;
/* entry function for structure alignment */
if (cp_opt) CPalign_main(
xa, ya, seqx, seqy, secx, secy,
t0, u0, TM1, TM2, TM3, TM4, TM5,
d0_0, TM_0, d0A, d0B, d0u, d0a, d0_out,
seqM, seqxA, seqyA,
rmsd0, L_ali, Liden, TM_ali, rmsd_ali, n_ali, n_ali8,
xlen, ylen, sequence, Lnorm_ass, d0_scale,
i_opt, a_opt, u_opt, d_opt, force_fast_opt,
mol_vec1[chain_i]+mol_vec2[chain_j],TMcut);
else if (se_opt)
{
int *invmap = new int[ylen+1];
u0[0][0]=u0[1][1]=u0[2][2]=1;
u0[0][1]= u0[0][2]=
u0[1][0]= u0[1][2]=
u0[2][0]= u0[2][1]=
t0[0] =t0[1] =t0[2] =0;
se_main(
xa, ya, seqx, seqy, TM1, TM2, TM3, TM4, TM5,
d0_0, TM_0, d0A, d0B, d0u, d0a, d0_out,
seqM, seqxA, seqyA,
rmsd0, L_ali, Liden, TM_ali, rmsd_ali, n_ali, n_ali8,
xlen, ylen, sequence, Lnorm_ass, d0_scale,
i_opt, a_opt, u_opt, d_opt,
mol_vec1[chain_i]+mol_vec2[chain_j],
outfmt_opt, invmap);
if (outfmt_opt>=2)
{
Liden=L_ali=0;
int r1,r2;
for (r2=0;r2<ylen;r2++)
{
r1=invmap[r2];
if (r1<0) continue;
L_ali+=1;
Liden+=(seqx[r1]==seqy[r2]);
}
}
delete [] invmap;
}
else TMalign_main(
xa, ya, seqx, seqy, secx, secy,
t0, u0, TM1, TM2, TM3, TM4, TM5,
d0_0, TM_0, d0A, d0B, d0u, d0a, d0_out,
seqM, seqxA, seqyA,
rmsd0, L_ali, Liden, TM_ali, rmsd_ali, n_ali, n_ali8,
xlen, ylen, sequence, Lnorm_ass, d0_scale,
i_opt, a_opt, u_opt, d_opt, force_fast_opt,
mol_vec1[chain_i]+mol_vec2[chain_j],TMcut);
/* print result */
if (outfmt_opt==0) print_version();
int left_num=0;
int right_num=0;
int left_aln_num=0;
int right_aln_num=0;
bool after_cp=false;
if (cp_opt) after_cp=output_cp(
xname.substr(dir1_opt.size()+dir_opt.size()),
yname.substr(dir2_opt.size()+dir_opt.size()),
seqxA,seqyA,outfmt_opt,left_num,right_num,
left_aln_num,right_aln_num);
output_results(
xname.substr(dir1_opt.size()+dir_opt.size()+dirpair_opt.size()),
yname.substr(dir2_opt.size()+dir_opt.size()+dirpair_opt.size()),
chainID_list1[chain_i], chainID_list2[chain_j],
xlen, ylen, t0, u0, TM1, TM2, TM3, TM4, TM5,
rmsd0, d0_out, seqM.c_str(),
seqxA.c_str(), seqyA.c_str(), Liden,
n_ali8, L_ali, TM_ali, rmsd_ali, TM_0, d0_0,
d0A, d0B, Lnorm_ass, d0_scale, d0a, d0u,
(m_opt?fname_matrix:"").c_str(),
outfmt_opt, ter_opt, false, split_opt, o_opt,
fname_super, i_opt, a_opt, u_opt, d_opt, mirror_opt,
resi_vec1, resi_vec2);
if (cp_opt && outfmt_opt<=0)
{
cout<<"###############\t###############\n"
<<"#Aligned atom 1\tAligned atom 2#\n";
size_t r1=right_num;
size_t r2=0;
size_t r;
for (r=0;r<seqxA.size();r++)
{
r1+=seqxA[r]!='-';
r2+=seqyA[r]!='-';
if (seqxA[r]=='*')
{
cout<<"###### Circular\tPermutation ###\n";
r1=0;
}
else if (seqxA[r]!='-' && seqyA[r]!='-')
{
cout<<PDB_lines1[chain_i][r1-1].substr(12,15)<<'\t'
<<PDB_lines2[chain_j][r2-1].substr(12,15)<<'\n';
}
}
cout<<"###############\t###############"<<endl;
}
/* Done! Free memory */
seqM.clear();
seqxA.clear();
seqyA.clear();
DeleteArray(&ya, ylen);
delete [] seqy;
delete [] secy;
resi_vec2.clear();
} // chain_j
if (chain2_list.size()>1)
{
yname.clear();
for (chain_j=0;chain_j<ychainnum;chain_j++)
PDB_lines2[chain_j].clear();
PDB_lines2.clear();
chainID_list2.clear();
mol_vec2.clear();
}
} // j
PDB_lines1[chain_i].clear();
DeleteArray(&xa, xlen);
delete [] seqx;
delete [] secx;
resi_vec1.clear();
} // chain_i
xname.clear();
PDB_lines1.clear();
chainID_list1.clear();
mol_vec1.clear();
} // i
if (chain2_list.size()==1)
{
yname.clear();
for (chain_j=0;chain_j<ychainnum;chain_j++)
PDB_lines2[chain_j].clear();
PDB_lines2.clear();
resi_vec2.clear();
chainID_list2.clear();
mol_vec2.clear();
}
return 0;
}
/* MMalign if more than two chains. TMalign if only one chain */
int MMalign(const string &xname, const string &yname,
const string &fname_super, const string &fname_lign,
const string &fname_matrix, vector<string> &sequence,
const double d0_scale, const bool m_opt, const int o_opt,
const int a_opt, const bool d_opt, const bool full_opt,
const double TMcut, const int infmt1_opt, const int infmt2_opt,
const int ter_opt, const int split_opt, const int outfmt_opt,
bool fast_opt, const int mirror_opt, const int het_opt,
const string &atom_opt, const bool autojustify, const string &mol_opt,
const string &dir1_opt, const string &dir2_opt,
const vector<string> &chain1_list, const vector<string> &chain2_list,
const int byresi_opt,const string&chainmapfile)
{
/* declare previously global variables */
vector<vector<vector<double> > > xa_vec; // structure of complex1
vector<vector<vector<double> > > ya_vec; // structure of complex2
vector<vector<char> >seqx_vec; // sequence of complex1
vector<vector<char> >seqy_vec; // sequence of complex2
vector<vector<char> >secx_vec; // secondary structure of complex1
vector<vector<char> >secy_vec; // secondary structure of complex2
vector<int> mol_vec1; // molecule type of complex1, RNA if >0
vector<int> mol_vec2; // molecule type of complex2, RNA if >0
vector<string> chainID_list1; // list of chainID1
vector<string> chainID_list2; // list of chainID2
vector<int> xlen_vec; // length of complex1
vector<int> ylen_vec; // length of complex2
int i,j; // chain index
int xlen, ylen; // chain length
double **xa, **ya; // structure of single chain
char *seqx, *seqy; // for the protein sequence
char *secx, *secy; // for the secondary structure
int xlen_aa,ylen_aa; // total length of protein
int xlen_na,ylen_na; // total length of RNA/DNA
vector<string> resi_vec1; // residue index for chain1
vector<string> resi_vec2; // residue index for chain2
/* parse complex */
parse_chain_list(chain1_list, xa_vec, seqx_vec, secx_vec, mol_vec1,
xlen_vec, chainID_list1, ter_opt, split_opt, mol_opt, infmt1_opt,
atom_opt, autojustify, mirror_opt, het_opt, xlen_aa, xlen_na, o_opt,
resi_vec1);
if (xa_vec.size()==0) PrintErrorAndQuit("ERROR! 0 chain in complex 1");
parse_chain_list(chain2_list, ya_vec, seqy_vec, secy_vec, mol_vec2,
ylen_vec, chainID_list2, ter_opt, split_opt, mol_opt, infmt2_opt,
atom_opt, autojustify, 0, het_opt, ylen_aa, ylen_na, o_opt, resi_vec2);
if (ya_vec.size()==0) PrintErrorAndQuit("ERROR! 0 chain in complex 2");
int len_aa=getmin(xlen_aa,ylen_aa);
int len_na=getmin(xlen_na,ylen_na);
if (a_opt)
{
len_aa=(xlen_aa+ylen_aa)/2;
len_na=(xlen_na+ylen_na)/2;
}
int i_opt=0;
if (byresi_opt) i_opt=3;
map<int,int> chainmap;
if (chainmapfile.size())
{
string line;
int chainidx1,chainidx2;
vector<string> line_vec;
ifstream fin;
bool fromStdin=(chainmapfile=="-");
if (!fromStdin) fin.open(chainmapfile.c_str());
while (fromStdin?cin.good():fin.good())
{
if (fromStdin) getline(cin,line);
else getline(fin,line);
if (line.size()==0 || line[0]=='#') continue;
split(line,line_vec,'\t');
if (line_vec.size()==2)
{
chainidx1=-1;
chainidx2=-1;
for (i=0;i<chainID_list1.size();i++)
{
if (line_vec[0]==chainID_list1[i] ||
":"+line_vec[0]==chainID_list1[i] ||
":1,"+line_vec[0]==chainID_list1[i])
{
chainidx1=i;
break;
}
}
for (i=0;i<chainID_list2.size();i++)
{
if (line_vec[1]==chainID_list2[i] ||
":"+line_vec[1]==chainID_list2[i] ||
":1,"+line_vec[1]==chainID_list2[i])
{
chainidx2=i;
break;
}
}
if (chainidx1>=0 && chainidx2>=0)
{
if (chainmap.count(chainidx1))
cerr<<"ERROR! "<<line_vec[0]<<" already mapped"<<endl;
chainmap[chainidx1]=chainidx2;
}
else cerr<<"ERROR! Cannot map "<<line<<endl;
}
else cerr<<"ERROR! Cannot map "<<line<<endl;
for (i=0;i<line_vec.size();i++) line_vec[i].clear(); line_vec.clear();
}
if (!fromStdin) fin.close();
if (chainmap.size()==0)
cerr<<"ERROR! cannot map any chain pair from "<<chainmapfile<<endl;
}
/* perform monomer alignment if there is only one chain */
if (xa_vec.size()==1 && ya_vec.size()==1)
{
xlen = xlen_vec[0];
ylen = ylen_vec[0];
seqx = new char[xlen+1];
seqy = new char[ylen+1];
secx = new char[xlen+1];
secy = new char[ylen+1];
NewArray(&xa, xlen, 3);
NewArray(&ya, ylen, 3);
copy_chain_data(xa_vec[0],seqx_vec[0],secx_vec[0], xlen,xa,seqx,secx);
copy_chain_data(ya_vec[0],seqy_vec[0],secy_vec[0], ylen,ya,seqy,secy);
/* declare variable specific to this pair of TMalign */
double t0[3], u0[3][3];
double TM1, TM2;
double TM3, TM4, TM5; // for a_opt, u_opt, d_opt
double d0_0, TM_0;
double d0A, d0B, d0u, d0a;
double d0_out=5.0;
string seqM, seqxA, seqyA;// for output alignment
double rmsd0 = 0.0;
int L_ali; // Aligned length in standard_TMscore
double Liden=0;
double TM_ali, rmsd_ali; // TMscore and rmsd in standard_TMscore
int n_ali=0;
int n_ali8=0;
if (byresi_opt) extract_aln_from_resi(sequence,
seqx,seqy,resi_vec1,resi_vec2,byresi_opt);
/* entry function for structure alignment */
TMalign_main(xa, ya, seqx, seqy, secx, secy,
t0, u0, TM1, TM2, TM3, TM4, TM5,
d0_0, TM_0, d0A, d0B, d0u, d0a, d0_out,
seqM, seqxA, seqyA,
rmsd0, L_ali, Liden, TM_ali, rmsd_ali, n_ali, n_ali8,
xlen, ylen, sequence, 0, d0_scale,
i_opt, a_opt, false, d_opt, fast_opt,
mol_vec1[0]+mol_vec2[0],TMcut);
/* print result */
output_results(
xname.substr(dir1_opt.size()),
yname.substr(dir2_opt.size()),
chainID_list1[0], chainID_list2[0],
xlen, ylen, t0, u0, TM1, TM2, TM3, TM4, TM5, rmsd0, d0_out,
seqM.c_str(), seqxA.c_str(), seqyA.c_str(), Liden,
n_ali8, L_ali, TM_ali, rmsd_ali, TM_0, d0_0, d0A, d0B,
0, d0_scale, d0a, d0u, (m_opt?fname_matrix:"").c_str(),
outfmt_opt, ter_opt, true, split_opt, o_opt, fname_super,
0, a_opt, false, d_opt, mirror_opt, resi_vec1, resi_vec2);
/* clean up */
seqM.clear();
seqxA.clear();
seqyA.clear();
delete[]seqx;
delete[]seqy;
delete[]secx;
delete[]secy;
DeleteArray(&xa,xlen);
DeleteArray(&ya,ylen);
vector<vector<vector<double> > >().swap(xa_vec); // structure of complex1
vector<vector<vector<double> > >().swap(ya_vec); // structure of complex2
vector<vector<char> >().swap(seqx_vec); // sequence of complex1
vector<vector<char> >().swap(seqy_vec); // sequence of complex2
vector<vector<char> >().swap(secx_vec); // secondary structure of complex1
vector<vector<char> >().swap(secy_vec); // secondary structure of complex2
mol_vec1.clear(); // molecule type of complex1, RNA if >0
mol_vec2.clear(); // molecule type of complex2, RNA if >0
chainID_list1.clear(); // list of chainID1
chainID_list2.clear(); // list of chainID2
xlen_vec.clear(); // length of complex1
ylen_vec.clear(); // length of complex2
return 0;
}
/* declare TM-score tables */
int chain1_num=xa_vec.size();
int chain2_num=ya_vec.size();
vector<string> tmp_str_vec(chain2_num,"");
double **TMave_mat;
double **ut_mat; // rotation matrices for all-against-all alignment
int ui,uj,ut_idx;
NewArray(&TMave_mat,chain1_num,chain2_num);
NewArray(&ut_mat,chain1_num*chain2_num,4*3);
vector<vector<string> >seqxA_mat(chain1_num,tmp_str_vec);
vector<vector<string> > seqM_mat(chain1_num,tmp_str_vec);
vector<vector<string> >seqyA_mat(chain1_num,tmp_str_vec);
double maxTMmono=-1;
int maxTMmono_i,maxTMmono_j;
/* get all-against-all alignment */
if (len_aa+len_na>500) fast_opt=true;
for (i=0;i<chain1_num;i++)
{
xlen=xlen_vec[i];
if (xlen<3)
{
for (j=0;j<chain2_num;j++) TMave_mat[i][j]=-1;
continue;
}
seqx = new char[xlen+1];
secx = new char[xlen+1];
NewArray(&xa, xlen, 3);
copy_chain_data(xa_vec[i],seqx_vec[i],secx_vec[i],
xlen,xa,seqx,secx);
for (j=0;j<chain2_num;j++)
{
ut_idx=i*chain2_num+j;
for (ui=0;ui<4;ui++)
for (uj=0;uj<3;uj++) ut_mat[ut_idx][ui*3+uj]=0;
ut_mat[ut_idx][0]=1;
ut_mat[ut_idx][4]=1;
ut_mat[ut_idx][8]=1;
if (mol_vec1[i]*mol_vec2[j]<0) //no protein-RNA alignment
{
TMave_mat[i][j]=-1;
continue;
}
if (chainmap.size()>i && chainmap[i]!=j)
{
TMave_mat[i][j]=-1;
continue;
}
ylen=ylen_vec[j];
if (ylen<3)
{
TMave_mat[i][j]=-1;
continue;
}
seqy = new char[ylen+1];
secy = new char[ylen+1];
NewArray(&ya, ylen, 3);
copy_chain_data(ya_vec[j],seqy_vec[j],secy_vec[j],
ylen,ya,seqy,secy);
/* declare variable specific to this pair of TMalign */
double t0[3], u0[3][3];
double TM1, TM2;
double TM3, TM4, TM5; // for a_opt, u_opt, d_opt
double d0_0, TM_0;
double d0A, d0B, d0u, d0a;
double d0_out=5.0;
string seqM, seqxA, seqyA;// for output alignment
double rmsd0 = 0.0;
int L_ali; // Aligned length in standard_TMscore
double Liden=0;
double TM_ali, rmsd_ali; // TMscore and rmsd in standard_TMscore
int n_ali=0;
int n_ali8=0;
int Lnorm_tmp=len_aa;
if (mol_vec1[i]+mol_vec2[j]>0) Lnorm_tmp=len_na;
if (byresi_opt)
{
int total_aln=extract_aln_from_resi(sequence, seqx,seqy,
resi_vec1,resi_vec2,xlen_vec,ylen_vec, i, j, byresi_opt);
seqxA_mat[i][j]=sequence[0];
seqyA_mat[i][j]=sequence[1];
if (total_aln>xlen+ylen-3)
{
for (ui=0;ui<3;ui++) for (uj=0;uj<3;uj++)
ut_mat[ut_idx][ui*3+uj]=(ui==uj)?1:0;
for (uj=0;uj<3;uj++) ut_mat[ut_idx][9+uj]=0;
TMave_mat[i][j]=0;
seqM.clear();
seqxA.clear();
seqyA.clear();
delete[]seqy;
delete[]secy;
DeleteArray(&ya,ylen);
continue;
}
}
/* entry function for structure alignment */
TMalign_main(xa, ya, seqx, seqy, secx, secy,
t0, u0, TM1, TM2, TM3, TM4, TM5,
d0_0, TM_0, d0A, d0B, d0u, d0a, d0_out,
seqM, seqxA, seqyA,
rmsd0, L_ali, Liden, TM_ali, rmsd_ali, n_ali, n_ali8,
xlen, ylen, sequence, Lnorm_tmp, d0_scale,
i_opt, false, true, false, fast_opt,
mol_vec1[i]+mol_vec2[j],TMcut);
/* store result */
for (ui=0;ui<3;ui++)
for (uj=0;uj<3;uj++) ut_mat[ut_idx][ui*3+uj]=u0[ui][uj];
for (uj=0;uj<3;uj++) ut_mat[ut_idx][9+uj]=t0[uj];
seqxA_mat[i][j]=seqxA;
seqyA_mat[i][j]=seqyA;
TMave_mat[i][j]=TM4*Lnorm_tmp;
if (TMave_mat[i][j]>maxTMmono)
{
maxTMmono=TMave_mat[i][j];
maxTMmono_i=i;
maxTMmono_j=j;
}
/* clean up */
seqM.clear();
seqxA.clear();
seqyA.clear();
delete[]seqy;
delete[]secy;
DeleteArray(&ya,ylen);
}
delete[]seqx;
delete[]secx;
DeleteArray(&xa,xlen);
}
/* calculate initial chain-chain assignment */
int *assign1_list; // value is index of assigned chain2
int *assign2_list; // value is index of assigned chain1
assign1_list=new int[chain1_num];
assign2_list=new int[chain2_num];
double total_score=enhanced_greedy_search(TMave_mat, assign1_list,
assign2_list, chain1_num, chain2_num);
if (total_score<=0) PrintErrorAndQuit("ERROR! No assignable chain");
/* refine alignment for large oligomers */
int aln_chain_num=count_assign_pair(assign1_list,chain1_num);
bool is_oligomer=(aln_chain_num>=3);
if (aln_chain_num==2 && chainmap.size()==0) // dimer alignment
{
int na_chain_num1,na_chain_num2,aa_chain_num1,aa_chain_num2;
count_na_aa_chain_num(na_chain_num1,aa_chain_num1,mol_vec1);
count_na_aa_chain_num(na_chain_num2,aa_chain_num2,mol_vec2);
/* align protein-RNA hybrid dimer to another hybrid dimer */
if (na_chain_num1==1 && na_chain_num2==1 &&
aa_chain_num1==1 && aa_chain_num2==1) is_oligomer=false;
/* align pure protein dimer or pure RNA dimer */
else if ((getmin(na_chain_num1,na_chain_num2)==0 &&
aa_chain_num1==2 && aa_chain_num2==2) ||
(getmin(aa_chain_num1,aa_chain_num2)==0 &&
na_chain_num1==2 && na_chain_num2==2))
{
adjust_dimer_assignment(xa_vec,ya_vec,xlen_vec,ylen_vec,mol_vec1,
mol_vec2,assign1_list,assign2_list,seqxA_mat,seqyA_mat);
is_oligomer=false; // cannot refiner further
}
else is_oligomer=true; /* align oligomers to dimer */
}
if ((aln_chain_num>=3 || is_oligomer) && chainmap.size()==0) // oligomer alignment
{
/* extract centroid coordinates */
double **xcentroids;
double **ycentroids;
NewArray(&xcentroids, chain1_num, 3);
NewArray(&ycentroids, chain2_num, 3);
double d0MM=getmin(
calculate_centroids(xa_vec, chain1_num, xcentroids),
calculate_centroids(ya_vec, chain2_num, ycentroids));
/* refine enhanced greedy search with centroid superposition */
//double het_deg=check_heterooligomer(TMave_mat, chain1_num, chain2_num);
homo_refined_greedy_search(TMave_mat, assign1_list,
assign2_list, chain1_num, chain2_num, xcentroids,
ycentroids, d0MM, len_aa+len_na, ut_mat);
hetero_refined_greedy_search(TMave_mat, assign1_list,
assign2_list, chain1_num, chain2_num, xcentroids,
ycentroids, d0MM, len_aa+len_na);
/* clean up */
DeleteArray(&xcentroids, chain1_num);
DeleteArray(&ycentroids, chain2_num);
}
/* store initial assignment */
int init_pair_num=count_assign_pair(assign1_list,chain1_num);
int *assign1_init, *assign2_init;
assign1_init=new int[chain1_num];
assign2_init=new int[chain2_num];
double **TMave_init;
NewArray(&TMave_init,chain1_num,chain2_num);
vector<vector<string> >seqxA_init(chain1_num,tmp_str_vec);
vector<vector<string> >seqyA_init(chain1_num,tmp_str_vec);
vector<string> sequence_init;
copy_chain_assign_data(chain1_num, chain2_num, sequence_init,
seqxA_mat, seqyA_mat, assign1_list, assign2_list, TMave_mat,
seqxA_init, seqyA_init, assign1_init, assign2_init, TMave_init);
/* perform iterative alignment */
double max_total_score=0; // ignore old total_score because previous
// score was from monomeric chain superpositions
int max_iter=5-(int)((len_aa+len_na)/200);
if (max_iter<2) max_iter=2;
if (byresi_opt==0) MMalign_iter(max_total_score, max_iter, xa_vec, ya_vec,
seqx_vec, seqy_vec, secx_vec, secy_vec, mol_vec1, mol_vec2, xlen_vec,
ylen_vec, xa, ya, seqx, seqy, secx, secy, len_aa, len_na, chain1_num,
chain2_num, TMave_mat, seqxA_mat, seqyA_mat, assign1_list, assign2_list,
sequence, d0_scale, fast_opt);
if (byresi_opt && aln_chain_num>=4 && is_oligomer && chainmap.size()==0) // oligomer alignment
{
MMalign_final(xname.substr(dir1_opt.size()), yname.substr(dir2_opt.size()),
chainID_list1, chainID_list2,
fname_super, fname_lign, fname_matrix,
xa_vec, ya_vec, seqx_vec, seqy_vec,
secx_vec, secy_vec, mol_vec1, mol_vec2, xlen_vec, ylen_vec,
xa, ya, seqx, seqy, secx, secy, len_aa, len_na,
chain1_num, chain2_num, TMave_mat,
seqxA_mat, seqM_mat, seqyA_mat, assign1_list, assign2_list, sequence,
d0_scale, 1, 0, 5, ter_opt, split_opt,
0, 0, true, true, mirror_opt, resi_vec1, resi_vec2);
/* extract centroid coordinates */
double **xcentroids;
double **ycentroids;
NewArray(&xcentroids, chain1_num, 3);
NewArray(&ycentroids, chain2_num, 3);
double d0MM=getmin(
calculate_centroids(xa_vec, chain1_num, xcentroids),
calculate_centroids(ya_vec, chain2_num, ycentroids));
/* refine enhanced greedy search with centroid superposition */
//double het_deg=check_heterooligomer(TMave_mat, chain1_num, chain2_num);
homo_refined_greedy_search(TMave_mat, assign1_list,
assign2_list, chain1_num, chain2_num, xcentroids,
ycentroids, d0MM, len_aa+len_na, ut_mat);
hetero_refined_greedy_search(TMave_mat, assign1_list,
assign2_list, chain1_num, chain2_num, xcentroids,
ycentroids, d0MM, len_aa+len_na);
/* clean up */
DeleteArray(&xcentroids, chain1_num);
DeleteArray(&ycentroids, chain2_num);
}
/* sometime MMalign_iter is even worse than monomer alignment */
if (byresi_opt==0 && max_total_score<maxTMmono)
{
copy_chain_assign_data(chain1_num, chain2_num, sequence,
seqxA_init, seqyA_init, assign1_init, assign2_init, TMave_init,
seqxA_mat, seqyA_mat, assign1_list, assign2_list, TMave_mat);
for (i=0;i<chain1_num;i++)
{
if (i!=maxTMmono_i) assign1_list[i]=-1;
else assign1_list[i]=maxTMmono_j;
}
for (j=0;j<chain2_num;j++)
{
if (j!=maxTMmono_j) assign2_list[j]=-1;
else assign2_list[j]=maxTMmono_i;
}
sequence[0]=seqxA_mat[maxTMmono_i][maxTMmono_j];
sequence[1]=seqyA_mat[maxTMmono_i][maxTMmono_j];
max_total_score=maxTMmono;
MMalign_iter(max_total_score, max_iter, xa_vec, ya_vec, seqx_vec, seqy_vec,
secx_vec, secy_vec, mol_vec1, mol_vec2, xlen_vec, ylen_vec,
xa, ya, seqx, seqy, secx, secy, len_aa, len_na, chain1_num, chain2_num,
TMave_mat, seqxA_mat, seqyA_mat, assign1_list, assign2_list, sequence,
d0_scale, fast_opt);
}
/* perform cross chain alignment
* in some cases, this leads to dramatic improvement, esp for homodimer */
int iter_pair_num=count_assign_pair(assign1_list,chain1_num);
if (iter_pair_num>=init_pair_num) copy_chain_assign_data(
chain1_num, chain2_num, sequence_init,
seqxA_mat, seqyA_mat, assign1_list, assign2_list, TMave_mat,
seqxA_init, seqyA_init, assign1_init, assign2_init, TMave_init);
double max_total_score_cross=max_total_score;
if (byresi_opt==0 && len_aa+len_na<10000)
{