Abstract

Although the pairwise protein three-dimensional (3D) structure alignment is vital in structural bioinformatics, its complexity is categorized as non-deterministic polynomial-time hard (NP-hard). Hence, researchers strive to develop algorithms to overcome the heavy computation complexity. Most of their attempts tend to achieve more accurate alignment results regardless of the computational execution time. Therefore, finding a fast alignment algorithm with accurate results is still an outstanding task. Recently, General Purpose Graphical Processing Units (GPGPUs) can execute the many time-consuming algorithms faster than the CPUs can. This paper proposes the GPU-based implementation of the MatAlign algorithm which is based on the two-level alignment of protein. This GPU implementation yields about 11 increase in speed over its CPU-based, single-core implementation on GPU GeForce GTX 860M (640 cores, 2GB RAM) and Intel Core i7-4710HQ (2.50GHz, 8GB RAM, 8 cores) CPU. In order to achieve more accurate results, PTM-MatAlign is implemented to use the Template Modeling Score (TM-score) instead of the MatAlign regular score function.

References

• Morange, M. 1999. A History of Molecular Biology. BioScience, 49(11), 929-931.
• Burkowski, F.J. 2009. Structural bioinformatics: an algorithmic approach (Vol. 20): Chapman & Hall/CRC.
• Liisa , H., and S. Chris. 1993. Protein Structure Comparison by Alignment of Distance Matrices. Journal of Molecular Biology, 233(11), 123–138.
• Orengo, C.A., and W.R. Taylor. 1996. SSAP: sequential structure alignment program for protein structure comparison. Methods Enzymol, 266, 617-635.
• Zhang, Y., and J. Skolnick. 2005. TM-align: a protein structure alignment algorithm based on the TM-score. Nucleic Acids Research, 33(7), 2302-2309.
• Jianhua, Z., and W. Zhiping. 2004. FAST: A novel protein structure alignment algorithm. Proteins: Structure, Function, and Bioinformatics, 58(3), 618-627.
• Zeyar, A., and T. Kian-Lee. 2006. MatAlign: PRECISE PROTEIN STRUCTURE COMPARISON BY MATRIX ALIGNMENT. Journal of Bioinformatics and Computational Biology, 4(6), 1197-1216.
• Nicolas, B., and M. Pierre-Francois. 2012. LNA: Fast Protein Structural Comparison Using a Laplacian Characterization of Tertiary Structure. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 9(5), 1451-1458.
• Inken , W., M.-D. Noel , and A. Rumen 2012. CSA: comprehensive comparison of pairwise protein structure alignments. Nucleic Acids Research, 303-309.
• Genki, T., and T.-S. Mayuko. 2015. CAB-Align: A Flexible Protein Structure Alignment Method Based on the Residue-Residue Contact Area. PLoS ONE, 10(10).
• Jean-Francois, G., M. Thomas, and H.B. Stephen. 1996. Surprising similarities in structure comparison. Current Opinion in Structural Biology, 6(3), 377-385.
• Shindyalov, I.N., and P.E. Bourne. 1998. Protein structure alignment by incremental combinatorial extension (CE) of the optimal path. Protein Eng, 11(9), 739-747.
• Yuzhen, Y., and G. Adam. 2003. Flexible structure alignment by chaining aligned fragment pairs allowing twists. Bioinformatics, 19(2), 246-255.
• Maxim, S., N. Ruth, and J.W. Haim. 2004. FlexProt: Alignment of Flexible Protein Structures Without a Predefinition of Hinge Regions. Journal of Computational Biology, 11(1), 83-106.
• Mathilde, C., B. Sophie, and P. Joël. 2005. YAKUSA: A fast structural database scanning method. Proteins: Structure, Function, and Bioinformatics, 61, 137-151.
• Matthias, H., and F. Dmitrij. 2004. STRIDE: a web server for secondary structure assignment from known atomic coordinates of proteins. Nucleic Acids Research, 32, 500-502.
• Zheng, W. 2008. CLePAPS: Fast Pair Alignment of Protein Structures Based on Conformational Letters. Journal of Bioinformatics and Computational Biology, 6(2), 347-366.
• Potestio, R., et al. 2010. ALADYN: a web server for aligning proteins by matching their large-scale motion. Nucleic Acids Research, 38(2), 41-45.
• Paweł, D., and L. Bogdan. 2011. A novel method to compare protein structures using local descriptors. BMC Bioinformatics, 12(344).
• Shintaro, M., S. Kengo, and C. George. 2013. MICAN: a protein structure alignment algorithm that can handle multiple-chains, inverse alignments, Ca only models, alternative alignments, and non-sequential alignments. BMC Bioinformatics, 14(24).
• Silvia, C., et al. 2013. ASSIST: a fast versatile local structural comparison tool. Bioinformatics, 30(7).
• Noel, M.-D., and P. Natasa. 2014. GR-Align: fast and flexible alignment of protein 3D structures using graphlet degree similarity. Bioinformatics, 30(9), 1259-1265.
• Shanshan, C., Z. Yang, and B. Charles. 2015. PCalign: a method to quantify physicochemical similarity of protein-protein interfaces. BMC Bioinformatics, 16(33).
• Wohlers, I., F.S. Domingues, and W.K. Gunnar 2010. Towards optimal alignment of protein structure distance matrices. Bioinformatics, 26, 2273-2280.
• Linial, K. 20004. Approximate Protein Structural Alignment in Polynomial Time. Proceedings of the National Academy of Sciences of the United States of America(101), 12201–12206.
• Peter, A.J., P.R. Andrew, and G.M. Helen. 1994. A Graph-theoretic Approach to the Identification of Three-dimensional Patterns of Amino Acid Side-chains in Protein Structures. Journal of Molecular Biology, 243(2), 327–344.
• Andrew , W.C., B. Neera , and T. Janet 1997. TESS: a geometric hashing algorithm for deriving 3D coordinate templates for searching structural databases. Application to enzyme active sites. Protein Science, 6(11), 2308-2323.
• Nathaniel, L., N. Ruth , and W.J. Haim 2001. MUSTA - A General, Efficient, Automated Method for Multiple Structure Alignment and Detection of Common Motifs: Application to Proteins. Journal of Computational Biology, 8(2), 93-121.
• Jonathan, B.A., and T.M. Janet 2003. An algorithm for constraint-based structural template matching: application to 3D templates with statistical analysis. Bioinformatics, 19(13), 1644-1649.
• Pramod , W.P., et al. 2003. Functional Sites in Protein Families Uncovered via an Objective and Automated Graph Theoretic Approach. Journal of Molecular Biology, 326(3), 955–978.
• Alexander , S., and R.B. Robert. 2003. Annotation in three dimensions. PINTS: Patterns in Non-homologous Tertiary Structures. Nucleic Acids Research, 31(13), 3341-3344.
• Nurcan, T., et al. 2011. Predicting protein-protein interactions on a proteome scale by matching evolutionary and structural similarities at interfaces using PRISM. Nat. Protocols, 6(9), 1341-1354.
• Kundrotas, P.J., Z. Zhengwei, and J. Joël. 2012. Templates are available to model nearly all complexes of structurally characterized proteins. Proceedings of the National Academy of Sciences of the United States of America, 109(24), 9438-9441.
• Kundrotas, P.J., and I.A. Vakser. 2013. Global and local structural similarity in protein–protein complexes: Implications for template-based docking. Proteins, 81(12), 2137-2142.
• Bagley, S.C., and R.B. Altman. 1995. Characterizing the microenvironment surrounding protein sites. Protein Science, 4(4), 622-635.
• Binkowski, A.T., L. Adamian, and J. Liang. 2003. Inferring Functional Relationships of Proteins from Local Sequence and Spatial Surface Patterns. Journal of Molecular Biology, 332(2), 505–526.
• Glaser, F., et al. 2006. A method for localizing ligand binding pockets in protein structures. Proteins: Structure, Function, and Bioinformatics, 62(2), 479–488.
• Xie, L., and P.E. Bourne. 2008. Detecting evolutionary relationships across existing fold space, using sequence order-independent profile–profile alignments. Proceedings of the National Academy of Sciences of the United States of America, 105(14), 5441-5446.
• La, D., et al. 2009. 3D-SURFER: software for high-throughput protein surface comparison and analysis. Bioinformatics, 25(21), 2843-2844.
• Mernberger, M., G. Klebe, and E. Hullermeier. 2011. SEGA: Semiglobal Graph Alignment for Structure-Based Protein Comparison. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(5), 1330-1343.
• Hu, B., et al. 2014. PL-PatchSurfer: A Novel Molecular Local Surface-Based Method for Exploring Protein-Ligand Interactions. International Journal of Molecular Sciences, 15(9), 15122-15145.
• Karampudi, N.B.R., and R.P. Bahadur. 2015. Layers: A molecular surface peeling algorithm and its applications to analyze protein structures. Scientific Reports, 5.
• Alex , S.D., P.J. Stuckey, and A.I. Wirth. 2010. Fast and accurate protein substructure searching with simulated annealing and GPUs. BMC Bioinformatics, 11, 446.
• Bin, P., et al. 2012. Accelerating large-scale protein structure alignments with graphics processing units. BMC Research Notes, 5(1), 116.
• Mrozek, D., M. Brożek, and B. Małysiak-Mrozek. 2014. Parallel implementation of 3D protein structure similarity searches using a GPU and the CUDA. Journal of Molecular Biology, 20(2), 2067.
• Saul, N.B., and W.D. Christian. 1970. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3), 443-453.
• Rachel, K., K. Patrice, and L. Michael. 2005. Comprehensive Evaluation of Protein Structure Alignment Methods: Scoring by Geometric Measures. Journal of Molecular Biology, 346, 1173-1188.
• Alexandrov, N.N., and D. Fischer. 1996. Analysis of topological and nontopological structural similarities in the PDB: new examples with old structures. Proteins, 25(3), 354-365.
• Kabsch, W. 1978. A discussion of the solution for the best rotation to relate two sets of vectors. Acta Crystallographica, 34, 827-828.
• Skolnick, J. 2004. Scoring function for automated assessment of protein structure template quality. Proteins, 57, 702-710.
• Michael, L., and G. Mark. 1998. A unified statistical framework for sequence comparison and structure comparison. Proceedings of the National Academy of Sciences of the United States of America, 95(11), 5913-5920.
• Dhraief, A., R. Issaoui, and A. Belghith. 2011. Parallel Computing the Longest Common Subsequence (LCS) on GPUs: Efficiency and Language Suitability. INFOCOMP.
• Fischer, D., et al. 1996. Assessing the performance of fold recognition methods by means of a comprehensive benchmark. Pacific Symposium on Biocomputing, 300-318.
• Cheng, H., B.H. Kim, and N.V. Grishin. 2008. MALISAM: A Database of Structurally Analogous Motifs in Proteins. Nucleic Acids Research, 36, 211-217.
• Murzin, A.G., S.E. Brenner, and T. Hubbard. 1995. SCOP: a structural classification of proteins database for the investigation of sequences and structures. J Mol Biol(247), 536–540.