Application of Structural
Alignment in Immunology
Daron Standley & John Rozewicki

Research Institute for Microbial Diseases
Department of Genome Informatics
Osaka University

Sequence and Structure
PDB/mmCIFATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM
ATOM

65
66
67
68
69
70
71
72
73
74

N
CACO
N
CAC
O
CB
OG

GLY A
GLY A
GLY A
GLY A
SER A
SER A
SER A
SER A
SER A
SER A

313131
31
32
32
32
32
32
32

-51.397 -9.757-51.023 -9.667-51.645 -10.743-50.969 -11.318-52.926 -11.040-53.596 -12.031-52.979 -13.389-52.770 -14.157-55.098 -12.110-55.727 -10.876

12.36013.75814.62015.46514.40715.25315.01015.95314.97515.2531.00 22.01
1.00 24.83
1.00 23.60
1.00 29.16
1.00 20.88
1.00 20.22
1.00 24.23
1.00 23.99
1.00 20.43
1.00 31.32

FASTA>3V33_A
GGGTPKAPNLEPPLPEEEKEGSDLRPVVIDGSNVAMSHGNKEVFSCRGILLAVNWFLERGHTDITVFVPSWRKEQPRPDVPITDQHILRELEKKKILVFTPSRRVGGKRVVCYDDRFIVKLAYESDGIVVSNDTYRDLQGERQEWKRFIEERLLMYSFVNDKFMPPDDPLGRHGPSLDNFLRKKPLTLEHRKQPCPYGRKCTYGIKCRFFHPERPSCPQRSVAExample: Regnase-1

Multiple Sequence Alignment (MSA)
Sequences were aligned using MAFFT

Importance of MSAs
Sequence identity between the consensus of 2019-nCoV and representative betacoronavirus genomes

Structural Alignment
DASH Web Service◆ 3D structures canalso be aligned in
3D space◆ Corresponding
residues can bescored/calculated

DASH:

Database ofAligned
Structural
Homologs

Rozewicki, et. al.
Nucleic Acids Research2019◆ ASH structure alignment database◆ Tracking:◆ ~60 million chain alignments◆ ~100 million domain alignments◆ Integrated with MAFFT through public
REST interface◆ Conceived in 2003 at IPR◆ Development started in 2008
◆ Released to public in 2019

Why structural alignments?
Most common use: Protein Function Prediction
Zc3h12a: Unknown Function
MSGPCGEKPVLEASPTMSLWEFEDSHSRQGTPRPGQELAAEEASALELQMKVDFFRKLGYSSTEIHSVLQKLGVQADTNTVLGELVKHGTATERERQTSPDPCPQLPLVPRGGGTPKAPNLEPPLPEEEKEGSDLRPVVIDGSNVAMSHGNKEVFSCRGILLAVNWFLERGHTDITVFVPSWRKEQPRPDVPITDQHILRELEKKKILVFTPSRRVGGKRVVCYDDRFIVKLAYESDGIVVSNDTYRDLQGERQEWKRFIEERLLMYSFVNDKFMPPDDPLGRHGPSLDNFLRKKPLTLEHRKQPCPYGRKCTYGIKCRFFHPERPSCPQRSVADELRANALLSPPRAPSKDKNGRRPSPSSQSSSLLTESEQCSLDGKKLGAQASPGSRQEGLTQTYAPSGRSLAPSGGSGSSFGPTDWLPQTLDSLPYVSQDCLDSGIGSLESQMSELWGVRGGGPGEPGPPRAPYTGYSPYGSELPATAAFSAFGRAMGAGHFSVPADYPPAPPAFPPREYWSEPYPLPPPTSVLQEPPVQSPGAGRSPWGRAGSLAKEQASVYTKLCGVFPPHLVEAVMGRFPQLLDPQQLAAEILSYKSQHPSE

Zc3h12a Model
Template (2QIP)
2QIP Function Unknown
Protein 3000 Target

TaqPolymerase
ASH

Zc3h12a->Regnase-1

Matsushita, et. al.; Nature 2009
Other refs

Why multiple alignments?
MAFFT andMAFFT-DASH
MSAs of Regnase,
Taq polymerase
and 2QIPPDB & PDBj in 2003
◆ Only 24,000 entries in the PDB◆ Structural Genomics was starting to take off◆ National goal for Japanese labs to solve 3000
protein structures in 3 years◆ Good structural alignment tools were becomingmore and more necessaryStructure Resources
Annotation DB'sStructure Aligners◆ Domain parsing◆ Biological hierarchies◆ Structure neighbors◆ Structural comparison◆ Superimposing◆ Scoring

Examples: CATH, SCOP

Examples: Dali, GDTGDT: Global Distance Test◆ Used for CASP
◆ Local alignments generatedwith LGA◆ Weighted sum of the numberof aligned residues within 20
different distance cutoffs(0.5, 1, 1.5…10 Å)ASH:

Alignment ofStructuralHomologs

Standley, Toh, Nakamura
Proteins 57, 2004

◆ Double Dynamic Programming
combines local sampling with globalscoring◆ NER score replaces GDT discrete
distance cutoffs with smooth Gaussian◆ Allows direct optimization ofsuperposition gradient methods

NER = S e-(d/w)

2w

◆ Genetic ASH (GASH)

ASH:

Alignment ofStructuralHomologs◆ Standley, Toh, Nakamura; BMC Bioinformatics
2005◆ Rapid ASH (RASH)◆ Standley, Toh, Nakamura; BMC Bioinformatics
2007◆ SeSAW◆ Standley, Yamashita, Kinjo, Toh, Nakamura;
Bioinformatics 2010

Can we make a database?
Workflow
1) Choose representative structures from the PDB2) Slice representatives into domains
3) Align all domains against all domains
4) Build composite chain-level alignments

Seems simple!

Database Workflow
1) Choose representative structures from the PDB2) Slice representatives into domains
3) Align all domains against all domains
4) Build chain-level alignments
5) Add, remove, and modify as the PDB is updated

Oh, all of these steps are somewhat hard...

PDBIssues◆ Entries added every week…
◆ ... and also removed◆ Chain ID's sometimes change◆ Parsing data is non-trivial◆ Alternate Locations◆ Insertion Codes◆ Sequence/structure mismatch

Very difficult to build
something on top of the PDB.

Structure Navigator
Structure Navigator was an early prototype
of DASH at PDBj

Issues with Structure Navigator◆ Complicated front-end and back-end code
◆ Slow to update◆ Difficult to maintain◆ Not widely used

◆ No clear sense of quality (completeness or accuracy)of the results

How to assess quality?
Multiple sequence alignment might work

MAFFT+ASH◆ ASH residue-wise similarity used asrestraints◆ MSA benchmark sets can be used toevaluate the quality of the alignments◆ PDP-ASH step to map domainalignments back to chain level◆ MAFFTash web service released in2009◆ Tested, but not publishedMAFFTash Issues◆ Required user to manually select PDB templates◆ Slow performance if data wasn't cached◆ Cache problems:◆ Missing data could have multiple meanings◆ Cached output sometimes contained errors◆ Difficult to remove things from cache◆ Many points of failure:◆ Shell scripts (BASH/TCSH), Perl scripts, C code...

2017◆ Hired at RIMD to do computerinfrastructure◆ DASH update failing

Can we fix DASH?

Discoveries◆ DASH is split between 2 different databases◆ Cache for MAFFTash◆ Generic domain alignment DB◆ Weekly update crashes◆ Intertwined with many other databases◆ Empty REST interfaces (cannot be called by other software)

Let's start over!

Database Workflow
1) Choose representative structures from the PDB2) Slice representatives into domains
3) Align all domains against all domains
4) Build chain-level alignments
5) Add, remove, and modify as the PDB is updated

Oh, all of these steps are somewhat hard...

PDBGrowthEntry size is also increasing!

2018
RebuildPlan◆ Use Google Cloud for scaling◆ Keep ASH as the core
◆ Update software◆ Rewrite old workflow code in Go language◆ Version control everythingWhat is “Go?”◆ Static Binaries◆ Informative crashes◆ Large standard library◆ SQL, HTTP requests, Zip, etc.
◆ Built-in support for multi-threading◆ Faster than Python/Perl◆ Safer than C

2018◆ January◆ Google Cloud begins◆ March◆ 5.5 B domaincomparisons calculatedon ~2500 CPU cores◆ June◆ New PDP-ASH is written◆ July◆ First MSA benchmark◆ August◆ Alpha version opened◆ October◆ First comparison withPromals3D◆ December◆ Public beta started

MAFFTDASH
MAFFT andDASH can talkto each otherSequence

X Str. X Str.

MAFFT-DASH Benchmarks◆ 10% overall
improvement◆ >20%
improvementon hardestcases◆ Much fasterthan other
tested methods

Rozewicki, et. al.; NAR 2019

2019 Improvements◆ ASH Rewritten in Go◆ Many bug fixes◆ Multi-core support◆ JSON output◆ Rotation Matrices &Translation Vectors◆ Search by Structure
Rozewicki, et. al.; MIMB 2020

Search by structureWhere does mystructural model
fit in the protein
universe?

Rozewicki, et. al.; MIMB 2020