Overview of MADOKA

MADOKA performs one-against-all structure alignment procedure between the query protein and all proteins in the database. The illustrative workflow is shown in Fig. 4. The algorithm of MADOKA is composed of two phases. In the first phase, we represent pairwise protein structures as two strings of secondary structure units, and then conduct initial alignment between the secondary structure sequences by marking the Longest-Common-Subsequence (LCS) by dynamic programming. In the second phase, for each pairwise proteins with initial alignment score larger than a predefined threshold, we run pairwise 3D residue structural alignments by rigid body superposition and modified TM-align rotation matrix to pick up an alignment with highest TM-score (the comprehensive description of these two phases are showed in the following two sections). For versatility, The MADOKA implementation is written in C++ standard syntax and standard concurrency library, and thus supports multiple compilers natively and can run on many operating systems such as Microsoft Windows, macOS and Linux without modification. The program will decide whether to use multi-threading mode depending on the scale of input pairs; if the program is in parallel state, there will be multiple simultaneous executions of the algorithms for different pairs. The MADOKA website is developed using Perl, JavaScript, jQuery(AJAX) and CSS, and calls the MADOKA program for protein structure similarity searching.

Schematic diagram of MADOKA algorithm and the web interface. The algorithm involves two steps: 1) Search for Longest-Common-Subsequence (LCS) for each pairwise secondary structure elements using dynamic programming, and then structure pairs with the length of the LCS below the threshold are removed; 2) Pairwise 3D residue structural rigid body superposition is performed and residue-level alignments are constructed, and the best alignment with the highest TM-score and optimally aligned position for each pair of protein structures is selected