{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T15:14:06Z","timestamp":1774797246550,"version":"3.50.1"},"reference-count":48,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2021,11,26]],"date-time":"2021-11-26T00:00:00Z","timestamp":1637884800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100002261","name":"Russian Foundation for Basic Research","doi-asserted-by":"publisher","award":["20-07-00970"],"award-info":[{"award-number":["20-07-00970"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002261","name":"Russian Foundation for Basic Research","doi-asserted-by":"publisher","award":["18-29-13060"],"award-info":[{"award-number":["18-29-13060"]}],"id":[{"id":"10.13039\/501100002261","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,1,27]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>With the increasing availability of 3D-data, the focus of comparative bioinformatic analysis is shifting from protein sequence alignments toward more content-rich 3D-alignments. This raises the need for new ways to improve the accuracy of 3D-superimposition.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We proposed guide tree optimization with genetic algorithm (GA) as a universal tool to improve the alignment quality of multiple protein 3D-structures systematically. As a proof of concept, we implemented the suggested GA-based approach in popular Matt and Caretta multiple protein 3D-structure alignment (M3DSA) algorithms, leading to a statistically significant improvement of the TM-score quality indicator by up to 220\u20131523% on \u2018SABmark Superfamilies\u2019 (in 49\u201377% of cases) and \u2018SABmark Twilight\u2019 (in 59\u201380% of cases) datasets. The observed improvement in collections of distant homologies highlights the potentials of GA to optimize 3D-alignments of diverse protein superfamilies as one plausible tool to study the structure\u2013function relationship.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The source codes of patched gaCaretta and gaMatt programs are available open-access at https:\/\/github.com\/n-canter\/gamaps.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btab798","type":"journal-article","created":{"date-parts":[[2021,11,19]],"date-time":"2021-11-19T12:20:58Z","timestamp":1637324458000},"page":"985-989","source":"Crossref","is-referenced-by-count":5,"title":["Guide tree optimization with genetic algorithm to improve multiple protein 3D-structure alignment"],"prefix":"10.1093","volume":"38","author":[{"given":"Maksim V","family":"Shegay","sequence":"first","affiliation":[{"name":"Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Vorobjev Hills , Moscow 119991, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vytas K","family":"\u0160vedas","sequence":"additional","affiliation":[{"name":"Belozersky Institute of Physico-Chemical Biology, Lomonosov Moscow State University, Vorobjev Hills , Moscow 119991, Russia"},{"name":"Faculty of Bioengineering and Bioinformatics, Lomonosov Moscow State University, Vorobjev Hills , Moscow 119991, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir V","family":"Voevodin","sequence":"additional","affiliation":[{"name":"Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Vorobjev Hills , Moscow 119991, Russia"},{"name":"Research Computing Center, Lomonosov Moscow State University, Vorobjev Hills , Moscow 119991, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7054-3487","authenticated-orcid":false,"given":"Dmitry A","family":"Suplatov","sequence":"additional","affiliation":[{"name":"Belozersky Institute of Physico-Chemical Biology, Lomonosov Moscow State University, Vorobjev Hills , Moscow 119991, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nina N","family":"Popova","sequence":"additional","affiliation":[{"name":"Faculty of Computational Mathematics and Cybernetics, Lomonosov Moscow State University, Vorobjev Hills , Moscow 119991, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2021,11,26]]},"reference":[{"key":"2023020108512091600_btab798-B1","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1016\/j.csbj.2020.03.011","article-title":"Caretta\u2013a multiple protein structure alignment and feature extraction suite","volume":"18","author":"Akdel","year":"2020","journal-title":"Comput. Struct. Biotechnol. J"},{"key":"2023020108512091600_btab798-B2","first-page":"B1","article-title":"Handbook of evolutionary computation","volume":"97","author":"B\u00e4ck","year":"1997","journal-title":"Release"},{"key":"2023020108512091600_btab798-B3","doi-asserted-by":"crossref","first-page":"D464","DOI":"10.1093\/nar\/gky1004","article-title":"Rcsb protein data bank: biological macromolecular structures enabling research and education in fundamental biology, biomedicine, biotechnology and energy","volume":"47","author":"Burley","year":"2019","journal-title":"Nucleic Acids Res"},{"key":"2023020108512091600_btab798-B4","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msab293","article-title":"eggnog-mapper v2: functional annotation, orthology assignments, and domain prediction at the metagenomic scale","author":"Cantalapiedra","year":"2021","journal-title":"Mol. Biol. Evol"},{"key":"2023020108512091600_btab798-B5","doi-asserted-by":"crossref","first-page":"3970","DOI":"10.1093\/bioinformatics\/btz236","article-title":"Protein multiple alignments: sequence-based versus structure-based programs","volume":"35","author":"Carpentier","year":"2019","journal-title":"Bioinformatics"},{"key":"2023020108512091600_btab798-B6","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/bib\/bbv045","article-title":"Practical analysis of specificity-determining residues in protein families","volume":"17","author":"Chagoyen","year":"2016","journal-title":"Brief. Bioinform"},{"key":"2023020108512091600_btab798-B7","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/j.ygeno.2017.06.007","article-title":"A review on multiple sequence alignment from the perspective of genetic algorithm","volume":"109","author":"Chowdhury","year":"2017","journal-title":"Genomics"},{"key":"2023020108512091600_btab798-B8","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/j.future.2017.01.012","article-title":"Scientific workflows for computational reproducibility in the life sciences: status, challenges and opportunities","volume":"75","author":"Cohen-Boulakia","year":"2017","journal-title":"Fut. Gener. Comput. Syst"},{"key":"2023020108512091600_btab798-B9","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1038\/nrg3414","article-title":"Emerging methods in protein co-evolution","volume":"14","author":"De Juan","year":"2013","journal-title":"Nat. Rev. Genet"},{"key":"2023020108512091600_btab798-B10","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1038\/nbt.3820","article-title":"Nextflow enables reproducible computational workflows","volume":"35","author":"Di Tommaso","year":"2017","journal-title":"Nat. Biotechnol"},{"key":"2023020108512091600_btab798-B11","doi-asserted-by":"crossref","first-page":"1719","DOI":"10.1093\/bioinformatics\/btx828","article-title":"mtm-align: an algorithm for fast and accurate multiple protein structure alignment","volume":"34","author":"Dong","year":"2018","journal-title":"Bioinformatics"},{"key":"2023020108512091600_btab798-B12","doi-asserted-by":"crossref","first-page":"i718","DOI":"10.1093\/bioinformatics\/btaa839","article-title":"Geometricus represents protein structures as shape-mers derived from moment invariants","volume":"36","author":"Durairaj","year":"2020","journal-title":"Bioinformatics"},{"key":"2023020108512091600_btab798-B13","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1109\/4235.771166","article-title":"Parameter control in evolutionary algorithms","volume":"3","author":"Eiben","year":"1999","journal-title":"IEEE Trans. Evol. Comput"},{"key":"2023020108512091600_btab798-B14","first-page":"27","article-title":"The number of evolutionary trees","volume":"27","author":"Felsenstein","year":"1978","journal-title":"Syst. Biol"},{"key":"2023020108512091600_btab798-B15","first-page":"154","volume-title":"Proceedings of an International Conference on Genetic Algorithms and Their Applications","author":"Goldberg","year":"1985"},{"key":"2023020108512091600_btab798-B16","doi-asserted-by":"crossref","first-page":"eabe9403","DOI":"10.1126\/science.abe9403","article-title":"Comparative host-coronavirus protein interaction networks reveal pan-viral disease mechanisms","volume":"370","author":"Gordon","year":"2020","journal-title":"Science"},{"key":"2023020108512091600_btab798-B17","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/1090.001.0001","volume-title":"Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence","author":"Holland","year":"1992"},{"key":"2023020108512091600_btab798-B18","doi-asserted-by":"crossref","first-page":"3036","DOI":"10.1093\/bioinformatics\/btx350","article-title":"Deepsite: protein-binding site predictor using 3D-convolutional neural networks","volume":"33","author":"Jim\u00e9nez","year":"2017","journal-title":"Bioinformatics"},{"key":"2023020108512091600_btab798-B19","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1093\/bib\/bbq025","article-title":"Critical assessment of structure-based sequence alignment methods at distant relationships","volume":"12","author":"Kalaimathy","year":"2011","journal-title":"Brief. Bioinf"},{"key":"2023020108512091600_btab798-B20","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1110\/ps.03191704","article-title":"Automated selection of positions determining functional specificity of proteins by comparative analysis of orthologous groups in protein families","volume":"13","author":"Kalinina","year":"2004","journal-title":"Protein Sci"},{"key":"2023020108512091600_btab798-B21","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1002\/prot.20921","article-title":"Mustang: a multiple structural alignment algorithm","volume":"64","author":"Konagurthu","year":"2006","journal-title":"Proteins"},{"key":"2023020108512091600_btab798-B22","first-page":"2101","article-title":"3dm: systematic analysis of heterogeneous superfamily data to discover protein functionalities","volume":"78","author":"Kuipers","year":"2010","journal-title":"Proteins"},{"key":"2023020108512091600_btab798-B23","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/j.csbj.2014.09.001","article-title":"3d representations of amino acids\u2014applications to protein sequence comparison and classification","volume":"11","author":"Li","year":"2014","journal-title":"Comput. Struct. Biotechnol. J"},{"key":"2023020108512091600_btab798-B24","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.sbi.2021.01.010","article-title":"Web-based tools for computational enzyme design","volume":"69","author":"Marques","year":"2021","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023020108512091600_btab798-B25","doi-asserted-by":"crossref","first-page":"e10","DOI":"10.1371\/journal.pcbi.0040010","article-title":"Matt: local flexibility aids protein multiple structure alignment","volume":"4","author":"Menke","year":"2008","journal-title":"PLoS Comput. Biol"},{"key":"2023020108512091600_btab798-B26","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1186\/1471-2105-12-353","article-title":"Vertical decomposition with genetic algorithm for multiple sequence alignment","volume":"12","author":"Naznin","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023020108512091600_btab798-B27","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1007\/978-94-024-1069-3_11","volume-title":"From Protein Structure to Function with Bioinformatics","author":"Nilmeier","year":"2017"},{"key":"2023020108512091600_btab798-B28","doi-asserted-by":"crossref","first-page":"1515","DOI":"10.1093\/nar\/24.8.1515","article-title":"Saga: sequence alignment by genetic algorithm","volume":"24","author":"Notredame","year":"1996","journal-title":"Nucleic Acids Res"},{"key":"2023020108512091600_btab798-B29","doi-asserted-by":"crossref","first-page":"2112","DOI":"10.1093\/bioinformatics\/btt360","article-title":"Optimizing multiple sequence alignments using a genetic algorithm based on three objectives: structural information, non-gaps percentage and totally conserved columns","volume":"29","author":"Ortuno","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020108512091600_btab798-B30","doi-asserted-by":"crossref","first-page":"2295","DOI":"10.1093\/nar\/gkn072","article-title":"Promals3d: a tool for multiple protein sequence and structure alignments","volume":"36","author":"Pei","year":"2008","journal-title":"Nucleic Acids Res"},{"key":"2023020108512091600_btab798-B31","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.sbi.2021.05.012","article-title":"Computational approaches to predict protein functional families and functional sites","volume":"70","author":"Rauer","year":"2021","journal-title":"Curr. Opin. Struct. Biol"},{"key":"2023020108512091600_btab798-B32","first-page":"W5","article-title":"Mafft-dash: integrated protein sequence and structural alignment","volume":"47","author":"Rozewicki","year":"2019","journal-title":"Nucleic Acids Res"},{"key":"2023020108512091600_btab798-B33","doi-asserted-by":"crossref","first-page":"bbaa150","DOI":"10.1093\/bib\/bbaa150","article-title":"Recent advances in user-friendly computational tools to engineer protein function","volume":"22","author":"Sequeiros-Borja","year":"2021","journal-title":"Brief. Bioinf"},{"key":"2023020108512091600_btab798-B34","doi-asserted-by":"crossref","first-page":"4456","DOI":"10.1093\/bioinformatics\/btz224","article-title":"parmatt: parallel multiple alignment of protein 3D-structures with translations and twists for distributed-memory systems","volume":"35","author":"Shegay","year":"2019","journal-title":"Bioinformatics"},{"key":"2023020108512091600_btab798-B35","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1186\/1471-2105-15-338","article-title":"Systematic exploration of guide-tree topology effects for small protein alignments","volume":"15","author":"Sievers","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023020108512091600_btab798-B36","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/978-3-642-21551-3_7","volume-title":"Handbook of Computational Statistics","author":"Spall","year":"2012"},{"key":"2023020108512091600_btab798-B37","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1109\/21.286385","article-title":"Adaptive probabilities of crossover and mutation in genetic algorithms","volume":"24","author":"Srinivas","year":"1994","journal-title":"IEEE Trans. Syst. Man Cybern"},{"key":"2023020108512091600_btab798-B38","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1186\/1471-2105-6-221","article-title":"Gash: an improved algorithm for maximizing the number of equivalent residues between two protein structures","volume":"6","author":"Standley","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023020108512091600_btab798-B39","doi-asserted-by":"crossref","first-page":"D203","DOI":"10.1093\/nar\/gkh027","article-title":"Homstrad: recent developments of the homologous protein structure alignment database","volume":"32","author":"Stebbings","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023020108512091600_btab798-B40","doi-asserted-by":"crossref","first-page":"W308","DOI":"10.1093\/nar\/gkz385","article-title":"Yosshi: a web-server for disulfide engineering by bioinformatic analysis of diverse protein families","volume":"47","author":"Suplatov","year":"2019","journal-title":"Nucleic Acids Res"},{"key":"2023020108512091600_btab798-B41","doi-asserted-by":"crossref","first-page":"W65","DOI":"10.1093\/nar\/gkaa276","article-title":"Zebra2: advanced and easy-to-use web-server for bioinformatic analysis of subfamily-specific and conserved positions in diverse protein superfamilies","volume":"48","author":"Suplatov","year":"2020","journal-title":"Nucleic Acids Res"},{"key":"2023020108512091600_btab798-B42","doi-asserted-by":"crossref","first-page":"12382","DOI":"10.1007\/s11227-021-03691-x","article-title":"Co-designing hpc-systems by computing capabilities and management flexibility to accommodate bioinformatic worklows at diferent complexity levels","volume":"77","author":"Suplatov","year":"2021","journal-title":"J. Supercomput"},{"key":"2023020108512091600_btab798-B43","doi-asserted-by":"crossref","first-page":"1583","DOI":"10.1093\/bioinformatics\/btx831","article-title":"Mustguseal: a server for multiple structure-guided sequence alignment of protein families","volume":"34","author":"Suplatov","year":"2018","journal-title":"Bioinformatics"},{"key":"2023020108512091600_btab798-B44","doi-asserted-by":"crossref","first-page":"S10","DOI":"10.1186\/1471-2164-10-S1-S10","article-title":"Rbt-ga: a novel metaheuristic for solving the multiple sequence alignment problem","volume":"10","author":"Taheri","year":"2009","journal-title":"BMC Genomics"},{"key":"2023020108512091600_btab798-B45","doi-asserted-by":"crossref","first-page":"1302","DOI":"10.1016\/j.csbj.2021.02.005","article-title":"Bioinformatic analysis of subfamily-specific regions in 3D-structures of homologs to study functional diversity and conformational plasticity in protein superfamilies","volume":"19","author":"Timonina","year":"2021","journal-title":"Comput. Struct. Biotechnol. J"},{"key":"2023020108512091600_btab798-B46","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1093\/bioinformatics\/bth493","article-title":"Sabmark\u2014a benchmark for sequence alignment that covers the entire known fold space","volume":"21","author":"Van Walle","year":"2005","journal-title":"Bioinformatics"},{"key":"2023020108512091600_btab798-B47","first-page":"4","article-title":"Supercomputer lomonosov-2: large scale, deep monitoring and fine analytics for the user community","volume":"6","author":"Voevodin","year":"2019","journal-title":"Supercomput. Front. Innov"},{"key":"2023020108512091600_btab798-B48","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1002\/prot.20264","article-title":"Scoring function for automated assessment of protein structure template quality","volume":"57","author":"Zhang","year":"2004","journal-title":"Proteins"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btab798\/41537361\/btab798.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/4\/985\/49007746\/btab798.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/4\/985\/49007746\/btab798.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T20:09:56Z","timestamp":1675282196000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/4\/985\/6443087"}},"subtitle":[],"editor":[{"given":"Lenore","family":"Cowen","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2021,11,26]]},"references-count":48,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,1,27]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btab798","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,2,15]]},"published":{"date-parts":[[2021,11,26]]}}}