A new memetic algorithm for multiple graph alignment - Ngoc Ha, Tran; Hien, Le Nhu; Huan, Hoang Xuan (VNU Journal of Science: Computer Science and Communication Engineering; Vol 34 No 1 (2018), 2018)
One of the main tasks of structural biology is comparing the structure of proteins. Comparisons of protein structure can determine their functional similarities. Multigraph alignment is a useful tool for identifying functional similarities based on structural analysis. This article proposes a new algorithm for aligning protein binding sites called ACOTS-MGA. This algorithm is based on the memetic scheme. It uses the ACO method to construct a set of solutions, then selects the best solution for implementing Tabu Search to improve the solution quality. Experimental results have shown that ACOTS-MGA outperforms state-of-the-art algorithms while producing alignments of better quality. Keywords Multiple Graph Alignment, Tabu Search, Ant Colony Optimization, local search, memetic algorithm, SMMAS pheromone update rule, protein active sites References E. Todd, C. A. Orengo, and J. M. Thornton, â€œEvolution of function in protein superfamilies, from a structural perspective,â€ J. Mol. Biol. , vol. 307, no. 4, pp. 1113â€“1143, Apr. 2001. S. F. Altschul et al. , â€œGapped BLAST and PSI-BLAST: a new generation of protein database search programs,â€ Nucleic Acids Res. , vol. 25, pp. 3389â€“3402, 1997. R. C. Edgar, â€œMUSCLE: multiple sequence alignment with high accuracy and high throughput,â€ Nucleic Acids Res. , vol. 32, no. 5, pp. 1792â€“1797, Mar. 2004. J. D. Thompson, D. G. Higgins, and T. J. Gibson, â€œCLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice,â€ Nucleic Acids Res. , vol. 22, no. 22, pp. 4673â€“4680, Nov. 1994. M. Larkin, G. Blackshields, N. Brown, â€¦ R. C.-, and  undefined 2007, â€œClustal W and Clustal X version 2.0,â€ academic.oup.com . C. Notredame, D. G. Higgins, and J. Heringa, â€œT-coffee: a novel method for fast and accurate multiple sequence alignment,â€ J. Mol. Biol. , vol. 302, no. 1, pp. 205â€“217, Sep. 2000. K. Sjolander, â€œPhylogenomic inference of protein molecular function: advances and challenges,â€ Bioinformatics , vol. 20, no. 2, pp. 170â€“179, Jan. 2004. T. Fober, M. Mernberger, G. Klebe, and E. HÃ¼llermeier, â€œEvolutionary construction of multiple graph alignments for the structural analysis of biomolecules,â€ Bioinformatics , vol. 25, no. 16, pp. 2110â€“2117, 2009. M. Mernberger, G. Klebe, and E. Hullermeier, â€œSEGA: Semiglobal Graph Alignment for Structure-Based Protein Comparison,â€ IEEE/ACM Trans. Comput. Biol. Bioinforma. , vol. 8, no. 5, pp. 1330â€“1343, Sep. 2011. D. Shasha, J. T. L. Wang, and R. Giugno, â€œAlgorithmics and applications of tree and graph searching,â€ in Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems  - PODS â€™02 , 2002, p. 39. R. V. Spriggs, P. J. Artymiuk, and P. Willett, â€œSearching for Patterns of Amino Acids in 3D Protein Structures,â€ J. Chem. Inf. Comput. Sci. , vol. 43, no. 2, pp. 412â€“421, Mar. 2003. D. Conte, P. Foggia, C. Sansone, And M. Vento, â€œThirty years of graph matching in pattern recognition,â€ Int. J. Pattern Recognit. Artif. Intell. , vol. 18, no. 3, pp. 265â€“298, May 2004. K. Kinoshita and H. Nakamura, â€œIdentification of the ligand binding sites on the molecular surface of proteins,â€ Protein Sci. , vol. 14, no. 3, pp. 711â€“718, Mar. 2005. O. Kuchaiev and N. PrÅ¾ulj, â€œIntegrative network alignment reveals large regions of global network similarity in yeast and human,â€ Bioinformatics , vol. 27, 2011. Xifeng Yan, Feida Zhu, Jiawei Han, and P. S. Yu, â€œSearching Substructures with Superimposed Distance,â€ in 22nd International Conference on Data Engineering (ICDEâ€™06) , 2006, pp. 88â€“88. X. Yan, P. S. Yu, and J. Han, â€œSubstructure similarity search in graph databases,â€ in Proceedings of the 2005 ACM SIGMOD international conference on Management of data  - SIGMOD â€™05 , 2005, p. 766. S. Zhang, M. Hu, and J. Yang, â€œTreePi: A Novel Graph Indexing Method,â€ in 2007 IEEE 23rd International Conference on Data Engineering , 2007, pp. 966â€“975. A. E. Aladag and C. Erten, â€œSPINAL: scalable protein interaction network alignment,â€ Bioinformatics , vol. 29, pp. 917â€“924, 2013. S. Schmitt, D. Kuhn, and G. Klebe, â€œA New Method to Detect Related Function Among Proteins Independent of Sequence and Fold Homology,â€ J. Mol. Biol. , vol. 323, no. 2, pp. 387â€“406, Oct. 2002. M. Hendlich, A. Bergner, J. GÃ¼nther, and G. Klebe, â€œRelibase: Design and Development of a Database for Comprehensive Analysis of Proteinâ€“Ligand Interactions,â€ J. Mol. Biol. , vol. 326, no. 2, pp. 607â€“620, Feb. 2003. N. Weskamp, E. HÃ¼llermeier, D. Kuhn, and G. Klebe, â€œMultiple graph alignment for the structural analysis of protein active sites,â€ IEEE/ACM Trans. Comput. Biol. Bioinforma. , vol. 4, no. 2, pp. 310â€“320, 2007. T. N. Ha, D. D. Dong, and H. X. Huan, â€œAn efficient ant colony optimization algorithm for Multiple Graph Alignment,â€ in 2013 International Conference on Computing, Management and Telecommunications (ComManTel) , 2013, pp. 386â€“391. F. Neri, Handbook of memetic algorithms , vol. 379. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. M. Gong, Z. Peng, L. Ma, and J. Huang, â€œGlobal Biological Network Alignment by Using Efficient Memetic Algorithm,â€ IEEE/ACM Trans. Comput. Biol. Bioinforma. , vol. 13, no. 6, pp. 1117â€“1129, Nov. 2016. J. M. Caldonazzo Garbelini, A. Y. Kashiwabara, and D. S. Sanches, â€œSequence motif finder using memetic algorithm,â€ BMC Bioinformatics , vol. 19, 2018. L. Correa, B. Borguesan, C. Farfan, M. Inostroza-Ponta, and M. Dorn, â€œA Memetic Algorithm for 3-D Protein Structure Prediction Problem,â€ IEEE/ACM Trans. Comput. Biol. Bioinforma. , pp. 1â€“1, 2016. H. Tran Ngoc, D. Do Duc, and H. Hoang Xuan, â€œA novel ant based algorithm for multiple graph alignment,â€ in 2014 International Conference on Advanced Technologies for Communications (ATC 2014) , 2014, pp. 181â€“186. H. X. Huan, N. Linh-Trung, H.-T. Huynh, and others, â€œSolving the Traveling Salesman Problem with Ant Colony Optimization: A Revisit and New Efficient Algorithms,â€ REV J. Electron. Commun. , vol. 2, no. 3â€“4, 2013. D. Do Duc, H. Q. Dinh, and H. Hoang Xuan, â€œOn the Pheromone Update Rules of Ant Colony Optimization Approaches for the Job Shop Scheduling Problem,â€ 2008, pp. 153-160.