{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:36Z","timestamp":1740144516977,"version":"3.37.3"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T00:00:00Z","timestamp":1652659200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T00:00:00Z","timestamp":1652659200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SFB 1423 \/ 421152132"],"award-info":[{"award-number":["SFB 1423 \/ 421152132"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100008678","name":"Universit\u00e4t Leipzig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008678","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Commonly, sequence and structure elements are assumed to evolve congruently, such that homologous sequence positions correspond to homologous structural features. Assuming <jats:italic>congruent<\/jats:italic> evolution, alignments based on sequence <jats:italic>and<\/jats:italic> structure similarity can therefore optimize both similarities at the same time in a single alignment. To model <jats:italic>incongruent<\/jats:italic> evolution, where sequence and structural features diverge positionally, we recently introduced <jats:italic>bi-alignments<\/jats:italic>. This generalization of sequence and structure-based alignments is best understood as alignments of two distinct pairwise alignments of the same entities: one modeling sequence similarity, the other structural similarity.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>Optimal bi-alignments with affine gap costs (or affine shift cost) for two constituent alignments can be computed exactly in quartic space and time. Even bi-alignments with affine shift and gap cost, as well as bi-alignment with sub-additive gap cost are optimized efficiently. Affine gap-cost bi-alignment of large proteins (<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\sim 930$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mo>\u223c<\/mml:mo>\n                      <mml:mn>930<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula> aa) can be computed.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>Affine cost bi-alignments are of practical interest to study shifts of protein sequences and protein structures relative to each other.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Availability<\/jats:title>\n                <jats:p>The affine cost bi-alignment algorithm has been implemented in Python 3 and Cython. It is available as free software from <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/s-will\/BiAlign\/releases\/tag\/v0.3\">https:\/\/github.com\/s-will\/BiAlign\/releases\/tag\/v0.3<\/jats:ext-link> and as bioconda package .<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-022-00219-7","type":"journal-article","created":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T11:05:41Z","timestamp":1652699141000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Bi-alignments with affine gaps costs"],"prefix":"10.1186","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5016-5191","authenticated-orcid":false,"given":"Peter F.","family":"Stadler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Will","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,16]]},"reference":[{"key":"219_CR1","doi-asserted-by":"publisher","DOI":"10.23943\/princeton\/9780691156460.001.0001","volume-title":"Homology, genes, and evolutionary innovation","author":"GP Wagner","year":"2014","unstructured":"Wagner GP. Homology, genes, and evolutionary innovation. Princeton: Princeton Univ. Press; 2014."},{"key":"219_CR2","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1016\/S0022-2836(02)00308-X","volume":"319","author":"IL Hofacker","year":"2002","unstructured":"Hofacker IL, Fekete M, Stadler PF. Secondary structure prediction for aligned RNA sequences. J Mol Biol. 2002;319:1059\u201366. https:\/\/doi.org\/10.1016\/S0022-2836(02)00308-X.","journal-title":"J Mol Biol"},{"key":"219_CR3","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1038\/nbt.2419","volume":"30","author":"DS Marks","year":"2012","unstructured":"Marks DS, Hopf TA, Sander C. Protein structure prediction from sequence variation. Nat Biotechnol. 2012;30:1072\u201380. https:\/\/doi.org\/10.1038\/nbt.2419.","journal-title":"Nat Biotechnol"},{"key":"219_CR4","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1101\/gr.1759004","volume":"14","author":"MA Chapman","year":"2004","unstructured":"Chapman MA, Donaldson IJ, Gilbert J, Grafham D, Rogers J, Green AR, G\u00f6ttgens B. Analysis of multiple genomic sequence alignments: a web resource, online tools, and lessons learned from analysis of mammalian SCL loci. Genome Res. 2004;14:313\u20138. https:\/\/doi.org\/10.1101\/gr.1759004.","journal-title":"Genome Res"},{"key":"219_CR5","doi-asserted-by":"publisher","first-page":"1289","DOI":"10.1101\/gr.090050.108","volume":"19","author":"M Hiller","year":"2009","unstructured":"Hiller M, Findei\u00df S, Lein S, Marz M, Nickel C, Rose D, Schulz C, Backofen R, Prohaska SJ, Reuter G, Stadler PF. Conserved introns reveal novel transcripts in Drosophila melanogaster. Genome Res. 2009;19:1289\u2013300. https:\/\/doi.org\/10.1101\/gr.090050.108.","journal-title":"Genome Res"},{"key":"219_CR6","doi-asserted-by":"publisher","first-page":"10739","DOI":"10.1073\/pnas.94.20.10739","volume":"94","author":"A Stoltzfus","year":"1997","unstructured":"Stoltzfus A, Logsdon JM Jr, Palmer JD, Ford DW. Intron \u201csliding\u2019\u2019 and the diversity of intron positions. Proc Natl Acad Sci USA. 1997;94:10739\u201344. https:\/\/doi.org\/10.1073\/pnas.94.20.10739.","journal-title":"Proc Natl Acad Sci USA"},{"key":"219_CR7","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1186\/1471-2148-10-156","volume":"10","author":"J Lehmann","year":"2010","unstructured":"Lehmann J, Eisenhardt C, Stadler PF, Krauss V. Some novel intron positions in conserved Drosophila genes are caused by intron sliding or tandem duplications. BMC Evol Biol. 2010;10:156. https:\/\/doi.org\/10.1186\/1471-2148-10-156.","journal-title":"BMC Evol Biol"},{"key":"219_CR8","doi-asserted-by":"publisher","first-page":"2340","DOI":"10.1093\/gbe\/evw157","volume":"8","author":"S Bocco","year":"2016","unstructured":"Bocco S, Cs\u0171r\u00f6s M. Splice sites seldom slide: intron evolution in oomycetes. Genome Biol Evol. 2016;8:2340\u201350. https:\/\/doi.org\/10.1093\/gbe\/evw157.","journal-title":"Genome Biol Evol"},{"key":"219_CR9","doi-asserted-by":"publisher","first-page":"9085","DOI":"10.1093\/nar\/gkx520","volume":"45","author":"E Fekete","year":"2017","unstructured":"Fekete E, Flipphi M, \u00c1g N, Kavalecz N, Cerqueira G, Scazzocchio C, Karaffa L. A mechanism for a single nucleotide intron shift. Nucleic Acids Res. 2017;45:9085\u201392. https:\/\/doi.org\/10.1093\/nar\/gkx520.","journal-title":"Nucleic Acids Res"},{"key":"219_CR10","doi-asserted-by":"publisher","first-page":"1000106","DOI":"10.1371\/journal.pgen.1000106","volume":"4","author":"EE Hare","year":"2008","unstructured":"Hare EE, Peterson BK, Iyer VN, Meier R, Eisen MB. Sepsid even-skipped enhancers are functionally conserved in Drosophila despite lack of sequence conservation. PLoS Genet. 2008;4:1000106. https:\/\/doi.org\/10.1371\/journal.pgen.1000106.","journal-title":"PLoS Genet"},{"key":"219_CR11","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1017\/s1355838200992161","volume":"6","author":"C Flamm","year":"2000","unstructured":"Flamm C, Fontana W, Hofacker I, Schuster P. RNA folding kinetics at elementary step resolution. RNA. 2000;6:325\u201338. https:\/\/doi.org\/10.1017\/s1355838200992161.","journal-title":"RNA"},{"key":"219_CR12","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/978-3-030-63061-4_15","volume-title":"Computational intelligence methods for bioinformatics and biostatistics (CIBB 2019)q","author":"M Waldl","year":"2020","unstructured":"Waldl M, Will S, Wolfinger MT, Hofacker IL, Stadler PF. Bi-alignments as models of incongruent evolution of RNA sequence and secondary structure. In: Cazzaniga P, Besozzi D, Merelli I, Manzoni L, editors. Computational intelligence methods for bioinformatics and biostatistics (CIBB 2019)q, vol. 12313. Lecture notes in computer science. Cham: Springer; 2020. p. 159\u201370. https:\/\/doi.org\/10.1007\/978-3-030-63061-4_15."},{"key":"219_CR13","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1021\/bi00699a002","volume":"13","author":"PY Chou","year":"1974","unstructured":"Chou PY, Fasman GD. Prediction of protein conformation. Biochemistry. 1974;13:222\u201345. https:\/\/doi.org\/10.1021\/bi00699a002.","journal-title":"Biochemistry"},{"key":"219_CR14","doi-asserted-by":"publisher","first-page":"15","DOI":"10.5281\/zenodo.50733","volume":"1","author":"T Ashok Kumar","year":"2013","unstructured":"Ashok Kumar T. CFSSP: Chou and Fasman secondary structure prediction server. Wide Spectr Res J. 2013;1:15\u20139. https:\/\/doi.org\/10.5281\/zenodo.50733.","journal-title":"Wide Spectr Res J"},{"key":"219_CR15","doi-asserted-by":"publisher","first-page":"5640","DOI":"10.1074\/jbc.RA119.010727","volume":"295","author":"AG Bart","year":"2020","unstructured":"Bart AG, Harris KL, Gillam EMJ, Scott EE. Structure of an ancestral mammalian family 1B1 cytochrome P450 with increased thermostability. J Biol Chem. 2020;295:5640\u201353. https:\/\/doi.org\/10.1074\/jbc.RA119.010727.","journal-title":"J Biol Chem"},{"key":"219_CR16","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/S0005-2736(98)00032-7","volume":"1371","author":"M Dong","year":"1998","unstructured":"Dong M, Ladavi\u00e8re L, Penin F, Del\u00e9age G, Baggetto LG. Secondary structure of P-glycoprotein investigated by circular dichroism and amino acid sequence analysis. Biochim Biophys Acta Biomembr. 1998;1371:317\u201334. https:\/\/doi.org\/10.1016\/S0005-2736(98)00032-7.","journal-title":"Biochim Biophys Acta Biomembr"},{"key":"219_CR17","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1098\/rspb.1994.0040","volume":"255","author":"P Schuster","year":"1994","unstructured":"Schuster P, Fontana W, Stadler PF, Hofacker IL. From sequences to shapes and back: a case study in RNA secondary structures. Proc R Soc Lond B. 1994;255:279\u201384. https:\/\/doi.org\/10.1098\/rspb.1994.0040.","journal-title":"Proc R Soc Lond B"},{"key":"219_CR18","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/S1359-0278(97)00037-0","volume":"2","author":"A Babajide","year":"1997","unstructured":"Babajide A, Hofacker IL, Sippl MJ, Stadler PF. Neutral networks in protein space: a computational study based on knowledge-based potentials of mean force. Fold Des. 1997;2:261\u20139. https:\/\/doi.org\/10.1016\/S1359-0278(97)00037-0.","journal-title":"Fold Des"},{"key":"219_CR19","doi-asserted-by":"publisher","first-page":"2393","DOI":"10.1016\/S0006-3495(97)78268-7","volume":"73","author":"E Bornberg-Bauer","year":"1997","unstructured":"Bornberg-Bauer E. How are model protein structures distributed in sequence space? Biophys J. 1997;73:2393\u2013403. https:\/\/doi.org\/10.1016\/S0006-3495(97)78268-7.","journal-title":"Biophys J"},{"key":"219_CR20","doi-asserted-by":"publisher","first-page":"1075","DOI":"10.1073\/pnas.81.4.1075","volume":"81","author":"W Kabsch","year":"1984","unstructured":"Kabsch W, Sander C. On the use of sequence homologies to predict protein structure: identical pentapeptides can have completely different conformations. Proc Natl Acad Sci USA. 1984;81:1075\u20138. https:\/\/doi.org\/10.1073\/pnas.81.4.1075.","journal-title":"Proc Natl Acad Sci USA"},{"issue":"5478","key":"219_CR21","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1126\/science.289.5478.448","volume":"289","author":"EA Schultes","year":"2000","unstructured":"Schultes EA, Bartel DP. One sequence, two ribozymes: implications for the emergence of new ribozyme folds. Science. 2000;289(5478):448\u201352. https:\/\/doi.org\/10.1126\/science.289.5478.448.","journal-title":"Science"},{"key":"219_CR22","doi-asserted-by":"publisher","first-page":"21149","DOI":"10.1073\/pnas.0906408106","volume":"106","author":"PA Alexander","year":"2009","unstructured":"Alexander PA, He Y, Chen Y, Orban J, Bryan PN. A minimal sequence code for switching protein structure and function. Proc Natl Acad Sci USA. 2009;106:21149\u201354. https:\/\/doi.org\/10.1073\/pnas.0906408106.","journal-title":"Proc Natl Acad Sci USA"},{"key":"219_CR23","doi-asserted-by":"publisher","unstructured":"Waldl M, Will S, Wolfinger ML, Hofacker IL, Stadler PF. Bi-alignments as models of incongruent evolution and RNA sequence and structure. In: Cazzaniga P, Besozzi D, Merelli I, editors. CIBB\u201919 proceedings. 2019. p. 6. https:\/\/doi.org\/10.1101\/631606.","DOI":"10.1101\/631606"},{"key":"219_CR24","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1137\/0128004","volume":"28","author":"D Sankoff","year":"1975","unstructured":"Sankoff D. Minimal mutation trees of sequences. SIAM J Appl Math. 1975;28:35\u201342. https:\/\/doi.org\/10.1137\/0128004.","journal-title":"SIAM J Appl Math"},{"key":"219_CR25","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1093\/bioinformatics\/16.1.41","volume":"16","author":"D Sankoff","year":"2000","unstructured":"Sankoff D. The early introduction of dynamic programming into computational biology. Bioinformatics. 2000;16:41\u20137. https:\/\/doi.org\/10.1093\/bioinformatics\/16.1.41.","journal-title":"Bioinformatics"},{"key":"219_CR26","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1109\/TCBB.2014.2326155","volume":"12","author":"C H\u00f6ner zu Siederdissen","year":"2015","unstructured":"H\u00f6ner zu Siederdissen C, Hofacker IL, Stadler PF. Product grammars for alignment and folding. IEEE\/ACM Trans Comp Biol Bioinf. 2015;12:507\u201319. https:\/\/doi.org\/10.1109\/TCBB.2014.2326155.","journal-title":"IEEE\/ACM Trans Comp Biol Bioinf"},{"key":"219_CR27","volume-title":"Introduction to computational molecular biology","author":"JC Setubal","year":"1997","unstructured":"Setubal JC, Meidanis J. Introduction to computational molecular biology. Boston: PWS Publishing Co.; 1997."},{"key":"219_CR28","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s11786-018-0338-4","volume":"12","author":"N Retzlaff","year":"2018","unstructured":"Retzlaff N, Stadler PF. Partially local multi-way alignments. Math Comp Sci. 2018;12:207\u201334. https:\/\/doi.org\/10.1007\/s11786-018-0338-4.","journal-title":"Math Comp Sci"},{"key":"219_CR29","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"SB Needleman","year":"1970","unstructured":"Needleman SB, Wunsch CD. A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol. 1970;48:443\u201353. https:\/\/doi.org\/10.1016\/0022-2836(70)90057-4.","journal-title":"J Mol Biol"},{"key":"219_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0022-2836(05)80006-3","volume":"235","author":"M Vingron","year":"1994","unstructured":"Vingron M, Waterman MS. Sequence alignment and penalty choice: review of concepts, case studies and implications. J Mol Biol. 1994;235:1\u201312. https:\/\/doi.org\/10.1016\/S0022-2836(05)80006-3.","journal-title":"J Mol Biol"},{"key":"219_CR31","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0001-8708(76)90202-4","volume":"20","author":"MS Waterman","year":"1976","unstructured":"Waterman MS, Smith TF, Beyer WA. Some biological sequence metrics. Adv Math. 1976;20:367\u201387. https:\/\/doi.org\/10.1016\/0001-8708(76)90202-4.","journal-title":"Adv Math"},{"key":"219_CR32","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1089\/106652701300312931","volume":"8","author":"TG Dewey","year":"2001","unstructured":"Dewey TG. A sequence alignment algorithm with an arbitrary gap penalty function. J Comp Biol. 2001;8:177\u201390. https:\/\/doi.org\/10.1089\/106652701300312931.","journal-title":"J Comp Biol"},{"key":"219_CR33","doi-asserted-by":"publisher","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","volume":"162","author":"O Gotoh","year":"1982","unstructured":"Gotoh O. An improved algorithm for matching biological sequences. J Mol Biol. 1982;162:705\u20138. https:\/\/doi.org\/10.1016\/0022-2836(82)90398-9.","journal-title":"J Mol Biol"},{"key":"219_CR34","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/0148063","volume":"48","author":"H Carrillo","year":"1988","unstructured":"Carrillo H, Lipman D. The multiple sequence alignment problem in biology. SIAM J Appl Math. 1988;48:1073\u201382. https:\/\/doi.org\/10.1137\/0148063.","journal-title":"SIAM J Appl Math"},{"key":"219_CR35","doi-asserted-by":"publisher","first-page":"4412","DOI":"10.1073\/pnas.86.12.4412","volume":"86","author":"DJ Lipman","year":"1989","unstructured":"Lipman DJ, Altschul SF, Kececioglu JD. A tool for multiple sequence alignment. Proc Natl Acad Sci USA. 1989;86:4412\u20135. https:\/\/doi.org\/10.1073\/pnas.86.12.4412.","journal-title":"Proc Natl Acad Sci USA"},{"key":"219_CR36","doi-asserted-by":"publisher","unstructured":"Kececioglu J, Starrett D. Aligning alignments exactly. In: Bourne PE, Gusfield D, editors. Proceedings of the 8th ACM conference on research in computational molecular biology (RECOMB). New York: ACM; 2004. p. 85\u201396. https:\/\/doi.org\/10.1145\/974614.974626.","DOI":"10.1145\/974614.974626"},{"key":"219_CR37","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0022-5193(86)80112-6","volume":"121","author":"O Gotoh","year":"1986","unstructured":"Gotoh O. Alignment of three biological sequences with an efficient traceback procedure. J Theor Biol. 1986;121:327\u201337. https:\/\/doi.org\/10.1016\/S0022-5193(86)80112-6.","journal-title":"J Theor Biol"},{"key":"219_CR38","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1142\/S0219720004000831","volume":"2","author":"AS Konagurthu","year":"2004","unstructured":"Konagurthu AS, Whisstock J, Stuckey PJ. Progressive multiple alignment using sequence triplet optimization and three-residue exchange costs. J Bioinf Comp Biol. 2004;2:719\u201345. https:\/\/doi.org\/10.1142\/S0219720004000831.","journal-title":"J Bioinf Comp Biol"},{"key":"219_CR39","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1186\/1471-2105-8-254","volume":"8","author":"M Kruspe","year":"2007","unstructured":"Kruspe M, Stadler PF. Progressive multiple sequence alignments from triplets. BMC Bioinform. 2007;8:254. https:\/\/doi.org\/10.1186\/1471-2105-8-254.","journal-title":"BMC Bioinform"},{"key":"219_CR40","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/s11786-020-00496-8","volume":"15","author":"SJ Berkemer","year":"2021","unstructured":"Berkemer SJ, H\u00f6ner zu Siederdissen C, Stadler PF. Compositional properties of alignments. Math Comp Sci. 2021;15:609\u201330. https:\/\/doi.org\/10.1007\/s11786-020-00496-8.","journal-title":"Math Comp Sci"},{"key":"219_CR41","doi-asserted-by":"publisher","first-page":"1443","DOI":"10.1126\/science.1604319","volume":"256","author":"GH Gonnet","year":"1992","unstructured":"Gonnet GH, Cohen MA, Benner SA. Exhaustive matching of the entire protein sequence database. Science. 1992;256:1443\u20135. https:\/\/doi.org\/10.1126\/science.1604319.","journal-title":"Science"},{"key":"219_CR42","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1186\/1471-2105-7-527","volume":"7","author":"RA Cartwright","year":"2006","unstructured":"Cartwright RA. Logarithmic gap costs decrease alignment accuracy. BMC Bioinform. 2006;7:527. https:\/\/doi.org\/10.1186\/1471-2105-7-527.","journal-title":"BMC Bioinform"},{"key":"219_CR43","doi-asserted-by":"publisher","first-page":"1035","DOI":"10.1038\/nbt0804-1035","volume":"22","author":"SR Eddy","year":"2004","unstructured":"Eddy SR. Where did the BLOSUM62 alignment score matrix come from? Nat Biotechnol. 2004;22:1035\u20136. https:\/\/doi.org\/10.1038\/nbt0804-1035.","journal-title":"Nat Biotechnol"},{"key":"219_CR44","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1038\/nbt0308-274","volume":"26","author":"MP Styczynski","year":"2008","unstructured":"Styczynski MP, Jensen KL, Rigoutsos I, Stephanopoulos G. BLOSUM62 miscalculations improve search performance. Nat Biotechnol. 2008;26:274\u20135. https:\/\/doi.org\/10.1038\/nbt0308-274.","journal-title":"Nat Biotechnol"},{"key":"219_CR45","doi-asserted-by":"publisher","first-page":"20200066","DOI":"10.1098\/rsfs.2020.0066","volume":"11","author":"PF Stadler","year":"2021","unstructured":"Stadler PF. Alignments of biomolecular contact maps. Interface Focus. 2021;11:20200066. https:\/\/doi.org\/10.1098\/rsfs.2020.0066.","journal-title":"Interface Focus"},{"key":"219_CR46","doi-asserted-by":"publisher","first-page":"2751","DOI":"10.1093\/bioinformatics\/btp530","volume":"25","author":"A Poleksic","year":"2009","unstructured":"Poleksic A. Algorithms for optimal protein structure alignment. Bioinformatics. 2009;25:2751\u20136. https:\/\/doi.org\/10.1093\/bioinformatics\/btp530.","journal-title":"Bioinformatics"},{"key":"219_CR47","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1748-7188-8-1","volume":"8","author":"SC Li","year":"2013","unstructured":"Li SC. The difficulty of protein structure alignment under the RMSD. Algorithms Mol Biol. 2013;8:1. https:\/\/doi.org\/10.1186\/1748-7188-8-1.","journal-title":"Algorithms Mol Biol"},{"key":"219_CR48","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-021-03819-2","author":"J Jumper","year":"2021","unstructured":"...Jumper J, Evans R, Pritzel A, Green T, Figurnov M, Ronneberger O, Tunyasuvunakool K, Bates R, \u017d\u00eddek A, Potapenko A, Bridgland A, Meyer C, Kohl SAA, Ballard AJ, Cowie A, Romera-Paredes B, Nikolov S, Jain R, Adler J, Beck T, Petersen S, Reimann D, Clancy E, Zielinski M, Steinegger M, Pacholska M, Berghammer T, Bodenstein S, Silver D, Vinyals O, Senior AW, Kavukcuoglu K, Kohli P, Hassabis D. Highly accurate protein structure prediction with AlphaFold. Nature. 2021. https:\/\/doi.org\/10.1038\/s41586-021-03819-2.","journal-title":"Nature"},{"key":"219_CR49","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1126\/science.abj8754","volume":"373","author":"M Baek","year":"2021","unstructured":"...Baek M, DiMaio F, Anishchenko I, Dauparas J, Ovchinnikov S, Lee GR, Wang J, Cong QC, Kinch LN, Schaeffer RD, Mill\u00e1n C, Park HP, Adams C, Glassman CR, DeGiovanni A, Pereira JH, Rodrigues AV, van Dijk AA, Ebrecht AC, Opperman DJ, Sagmeister T, Buhlheller C, Pavkov-Keller T, Rathinaswamy MK, Dalwadi U, Yip CKY, Burke JE, Garcia KC, Grishin NV, Adams PD, Read RJ, Baker D. Accurate prediction of protein structures and interactions using a three-track neural network. Science. 2021;373:871\u20136. https:\/\/doi.org\/10.1126\/science.abj8754.","journal-title":"Science"},{"key":"219_CR50","doi-asserted-by":"publisher","first-page":"2577","DOI":"10.1002\/bip.360221211","volume":"22","author":"W Kabsch","year":"1983","unstructured":"Kabsch W, Sander C. Dictionary of protein secondary structure: pattern recognition of hydrogen-bonded and geometrical features. Biopolymers. 1983;22:2577\u2013637. https:\/\/doi.org\/10.1002\/bip.360221211.","journal-title":"Biopolymers"},{"key":"219_CR51","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/978-3-642-28554-7_17","volume":"1","author":"P Daniluk","year":"2014","unstructured":"Daniluk P, Lesyng B. Theoretical and computational aspects of protein structural alignment. 2014;1:557\u201398. https:\/\/doi.org\/10.1007\/978-3-642-28554-7_17.","journal-title":"Theoretical and computational aspects of protein structural alignment"},{"key":"219_CR52","doi-asserted-by":"publisher","first-page":"1059","DOI":"10.1093\/protein\/7.9.1059","volume":"7","author":"RH Lathrop","year":"1994","unstructured":"Lathrop RH. The protein threading problem with sequence amino acid interaction preferences is NP-complete. Protein Eng Des Sel. 1994;7:1059\u201368. https:\/\/doi.org\/10.1093\/protein\/7.9.1059.","journal-title":"Protein Eng Des Sel"},{"key":"219_CR53","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1137\/0145048","volume":"45","author":"D Sankoff","year":"1985","unstructured":"Sankoff D. Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM J Appl Math. 1985;45:810\u201325. https:\/\/doi.org\/10.1137\/0145048.","journal-title":"SIAM J Appl Math"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00219-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-022-00219-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00219-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,16]],"date-time":"2022-05-16T11:06:43Z","timestamp":1652699203000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-022-00219-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,16]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["219"],"URL":"https:\/\/doi.org\/10.1186\/s13015-022-00219-7","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2022,5,16]]},"assertion":[{"value":"18 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"10"}}