{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T22:47:09Z","timestamp":1775861229847,"version":"3.50.1"},"reference-count":69,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001779","name":"Monash University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001779","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Australian Research Council\u2019s Discovery Project","award":["DP150100894"],"award-info":[{"award-number":["DP150100894"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,24]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Summary<\/jats:title><jats:p>Sequences of proteins evolve by accumulating substitutions together with insertions and deletions (indels) of amino acids. However, it remains a common practice to disconnect substitutions and indels, and infer approximate models for each of them separately, to quantify sequence relationships. Although this approach brings with it computational convenience (which remains its primary motivation), there is a dearth of attempts to unify and model them systematically and together. To overcome this gap, this article demonstrates how a complete statistical model quantifying the evolution of pairs of aligned proteins can be constructed using a time-parameterized substitution matrix and a time-parameterized alignment state machine. Methods to derive all parameters of such a model from any benchmark collection of aligned protein sequences are described here. This has not only allowed us to generate a unified statistical model for each of the nine widely used substitution matrices (PAM, JTT, BLOSUM, JO, WAG, VTML, LG, MIQS and PFASUM), but also resulted in a new unified model, MMLSUM. Our underlying methodology measures the Shannon information content using each model to explain losslessly any given collection of alignments, which has allowed us to quantify the performance of all the above models on six comprehensive alignment benchmarks. Our results show that MMLSUM results in a new and clear overall best performance, followed by PFASUM, VTML, BLOSUM and MIQS, respectively, amongst the top five. We further analyze the statistical properties of MMLSUM model and contrast it with others.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac246","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T11:10:15Z","timestamp":1649934615000},"page":"i229-i237","source":"Crossref","is-referenced-by-count":2,"title":["Bridging the gaps in statistical models of protein alignment"],"prefix":"10.1093","volume":"38","author":[{"given":"Dinithi","family":"Sumanaweera","sequence":"first","affiliation":[{"name":"Department of Data Science and Artificial Intelligence, Faculty of Information Technology, Monash University , Clayton, VIC 3800, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lloyd","family":"Allison","sequence":"additional","affiliation":[{"name":"Department of Data Science and Artificial Intelligence, Faculty of Information Technology, Monash University , Clayton, VIC 3800, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arun S","family":"Konagurthu","sequence":"additional","affiliation":[{"name":"Department of Data Science and Artificial Intelligence, Faculty of Information Technology, Monash University , Clayton, VIC 3800, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.plrev.2004.01.002","article-title":"Information theory in molecular biology","volume":"1","author":"Adami","year":"2004","journal-title":"Phys. Life Rev"},{"key":"2023041407524597400_","first-page":"10","author":"Adjeroh","year":"2006"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-76433-7","volume-title":"Coding Ockham\u2019s Razor","author":"Allison","year":"2018"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"418","DOI":"10.1007\/BF00160274","article-title":"The posterior probability distribution of alignments and its application to parameter estimation of evolutionary trees and to optimization of multiple alignments","volume":"39","author":"Allison","year":"1994","journal-title":"J. Mol. Evol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/S0092-8240(05)80219-8","article-title":"Minimum message length encoding and the comparison of macromolecules","volume":"52","author":"Allison","year":"1990","journal-title":"Bull. Math. Biol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF00160262","article-title":"Finite-state models in the alignment of macromolecules","volume":"35","author":"Allison","year":"1992","journal-title":"J. Mol. Evol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"D376","DOI":"10.1093\/nar\/gkz1064","article-title":"The SCOP database in 2020: expanded classification of representative family and superfamily domains of known protein structures","volume":"48","author":"Andreeva","year":"2020","journal-title":"Nucleic Acids Res"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"D115","DOI":"10.1093\/nar\/gkh131","article-title":"Uniprot: the universal protein knowledgebase","volume":"32","author":"Apweiler","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1093\/protein\/1.2.89","article-title":"Evaluation and improvements in the automatic alignment of protein sequences","volume":"1","author":"Barton","year":"1987","journal-title":"Protein Eng"},{"key":"2023041407524597400_","first-page":"370","article-title":"LII. An essay towards solving a problem in the doctrine of chances. By the late rev. Mr. Bayes, FRS communicated by Mr. Price, in a letter to John Canton, AMFR S","author":"Bayes","year":"1763","journal-title":"Philos. Trans. R. Soc. Lond"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1065","DOI":"10.1006\/jmbi.1993.1105","article-title":"Empirical and structural models for insertions and deletions in the divergent evolution of proteins","volume":"229","author":"Benner","year":"1993","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1006\/jmbi.2001.4495","article-title":"Pairwise sequence alignment below the twilight zone","volume":"307","author":"Blake","year":"2001","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","first-page":"47","article-title":"Using dirichlet mixture priors to derive hidden markov models for protein families","volume":"1","author":"Brown","year":"1993","journal-title":"Proc. Int. Conf. Intell. Syst. Mol. Biol"},{"key":"2023041407524597400_","first-page":"43","author":"Cao","year":"2007"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1186\/1471-2105-7-527","article-title":"Logarithmic gap costs decrease alignment accuracy","volume":"7","author":"Cartwright","year":"2006","journal-title":"BMC Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1016\/j.jmb.2004.05.045","article-title":"Empirical analysis of protein insertions and deletions determining parameters for the correct placement of gaps in protein sequence alignments","volume":"341","author":"Chang","year":"2004","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1005","DOI":"10.1093\/bioinformatics\/btw757","article-title":"Statistical inference of protein structural alignments using information and compression","volume":"33","author":"Collier","year":"2017","journal-title":"Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0605031","article-title":"On the voronoi regions of certain lattices","volume":"5","author":"Conway","year":"1984","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1109\/TCBB.2011.70","article-title":"Touring protein space with matt","volume":"9","author":"Daniels","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023041407524597400_","first-page":"345","author":"Dayhoff","year":"1978"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"330","DOI":"10.1101\/gr.2821705","article-title":"Probcons: probabilistic consistency-based multiple sequence alignment","volume":"15","author":"Do","year":"2005","journal-title":"Genome Res"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1093\/bioinformatics\/14.9.755","article-title":"Profile hidden Markov models","volume":"14","author":"Eddy","year":"1998","journal-title":"Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF02300754","article-title":"What is a conservative substitution?","volume":"19","author":"French","year":"1983","journal-title":"J. Mol. Evol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1443","DOI":"10.1126\/science.1604319","article-title":"Exhaustive matching of the entire protein sequence database","volume":"256","author":"Gonnet","year":"1992","journal-title":"Science"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/0022-2836(82)90398-9","article-title":"An improved algorithm for matching biological sequences","volume":"162","author":"Gotoh","year":"1982","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","first-page":"192","author":"Hategan","year":"2004"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"10915","DOI":"10.1073\/pnas.89.22.10915","article-title":"Amino acid substitution matrices from protein blocks","volume":"89","author":"Henikoff","year":"1992","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1006\/jmbi.1993.1489","article-title":"Protein structure comparison by alignment of distance matrices","volume":"233","author":"Holm","year":"1993","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","author":"Holmes","year":"1998"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12859-017-1665-1","article-title":"Solving the master equation for indels","volume":"18","author":"Holmes","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1006\/jmbi.1993.1548","article-title":"A structural basis for sequence comparisons: an evaluation of scoring methodologies","volume":"233","author":"Johnson","year":"1993","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","first-page":"275","article-title":"The rapid generation of mutation data matrices from protein sequences","volume":"8","author":"Jones","year":"1992","journal-title":"Comput. Appl. Biosci"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1186\/s12859-017-1703-z","article-title":"Pfasum: a substitution matrix from PFAM structural alignments","volume":"18","author":"Keul","year":"2017","journal-title":"BMC Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02109483","article-title":"Maximum likelihood inference of protein phylogeny and the origin of chloroplasts","volume":"31","author":"Kishino","year":"1990","journal-title":"J. Mol. Evol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1093\/molbev\/msi005","article-title":"Different versions of the dayhoff rate matrix","volume":"22","author":"Kosiol","year":"2005","journal-title":"Mol. Biol. Evol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1307","DOI":"10.1093\/molbev\/msn067","article-title":"An improved general amino acid replacement matrix","volume":"25","author":"Le","year":"2008","journal-title":"Mol. Biol. Evol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"D413","DOI":"10.1093\/nar\/gku1056","article-title":"IMGT\u00ae, the international ImMunoGeneTics information system 25 years on","volume":"43","author":"Lefranc","year":"2015","journal-title":"Nucleic Acids Res"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","DOI":"10.1093\/hesc\/9780198716846.001.0001","volume-title":"Introduction to Protein Science: Architecture, Function, and Genomics","author":"Lesk","year":"2016"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1632","DOI":"10.1126\/science.1158395","article-title":"Phylogeny-aware gap placement prevents errors in sequence alignment and evolutionary analysis","volume":"320","author":"L\u00f6ytynoja","year":"2008","journal-title":"Science"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1087","DOI":"10.1063\/1.1699114","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"J. Chem. Phys"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"2469","DOI":"10.1002\/pro.5560071126","article-title":"HOMSTRAD: a database of protein structure alignments for homologous families","volume":"7","author":"Mizuguchi","year":"1998","journal-title":"Protein Sci"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1093\/oxfordjournals.molbev.a003985","article-title":"Estimating amino acid substitution models: a comparison of dayhoff\u2019s estimator, the resolvent approach and a maximum likelihood method","volume":"19","author":"M\u00fcller","year":"2002","journal-title":"Mol. Biol. Evol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"536","DOI":"10.1016\/S0022-2836(05)80134-2","article-title":"SCOP: a structural classification of proteins database for the investigation of sequences and structures","volume":"247","author":"Murzin","year":"1995","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1089\/cmb.2012.0244","article-title":"Dirichlet mixtures, the dirichlet process, and the structure of protein space","volume":"20","author":"Nguyen","year":"2013","journal-title":"J. Comput. Biol"},{"key":"2023041407524597400_","volume-title":"Markov Chains","author":"Norris","year":"1998"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1186\/1471-2105-6-236","article-title":"Simprot: using an empirically determined indel distribution in simulations of protein evolution","volume":"6","author":"Pang","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/0022-2836(92)91008-D","article-title":"Analysis of insertions\/deletions in protein structures","volume":"224","author":"Pascarella","year":"1992","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","first-page":"203","volume-title":"Australian Conference on Artificial Intelligence","author":"Powell","year":"2004"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","DOI":"10.1093\/bioinformatics\/btac247","article-title":"On the reliability and the limits of inference of amino acid sequence alignments","author":"Rajapaksa","year":"2022","journal-title":"Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1186\/1471-2105-6-63","article-title":"Evolutionary models for insertions and deletions in a probabilistic modeling framework","volume":"6","author":"Rivas","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1186\/s12859-015-0832-5","article-title":"Parameterizing sequence alignment with an explicit evolutionary model","volume":"16","author":"Rivas","year":"2015","journal-title":"BMC Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1093\/protein\/12.2.85","article-title":"Twilight zone of protein sequence alignments","volume":"12","author":"Rost","year":"1999","journal-title":"Protein Eng"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"Bell Syst. Tech. J"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/S0006-3495(96)79210-X","article-title":"The Shannon information entropy of protein sequences","volume":"71","author":"Strait","year":"1996","journal-title":"Biophys. J"},{"key":"2023041407524597400_","first-page":"177","author":"Sumanaweera","year":"2018"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"i360","DOI":"10.1093\/bioinformatics\/btz368","article-title":"Statistical compression of protein sequences and inference of marginal probability landscapes over competing alignments using finite state models and dirichlet priors","volume":"35","author":"Sumanaweera","year":"2019","journal-title":"Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0092-8240(84)80018-X","article-title":"A unifying concept for the amino acid code","volume":"46","author":"Swanson","year":"1984","journal-title":"Bull. Math. Biol"},{"key":"2023041407524597400_","first-page":"2579","article-title":"Visualizing data using t-SNE","volume":"9","author":"van der Maaten","year":"2008","journal-title":"J. Mach. Learn. Res"},{"key":"2023041407524597400_","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":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1089\/106652703322756195","article-title":"A transition probability model for amino acid substitutions from blocks","volume":"10","author":"Veerassamy","year":"2003","journal-title":"J. Comput. Biol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0022-2836(05)80006-3","article-title":"Sequence alignment and penalty choice: review of concepts, case studies and implications","volume":"235","author":"Vingron","year":"1994","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1006\/jmbi.1995.0340","article-title":"An assessment of amino acid exchange matrices in aligning protein sequences: the twilight zone revisited","volume":"249","author":"Vogt","year":"1995","journal-title":"J. Mol. Biol"},{"key":"2023041407524597400_","volume-title":"Statistical and Inductive Inference by Minimum Message Length. Science & Business Media","author":"Wallace","year":"2005"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1093\/comjnl\/11.2.185","article-title":"An information measure for classification","volume":"11","author":"Wallace","year":"1968","journal-title":"Comput. J"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1111\/j.2517-6161.1987.tb01695.x","article-title":"Estimation and inference by compact coding","volume":"49","author":"Wallace","year":"1987","journal-title":"J. R. Stat. Soc. Ser. B (Methodological)"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1093\/oxfordjournals.molbev.a003851","article-title":"A general empirical model of protein evolution derived from multiple protein families using a maximum-likelihood approach","volume":"18","author":"Whelan","year":"2001","journal-title":"Mol. Biol. Evol"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1093\/bioinformatics\/btt694","article-title":"Revisiting amino acid substitution matrices for identifying distantly related proteins","volume":"30","author":"Yamada","year":"2014","journal-title":"Bioinformatics"},{"key":"2023041407524597400_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/bioinformatics\/9.1.1","article-title":"Reconstruction of strings past","volume":"9","author":"Yee","year":"1993","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i229\/49886437\/btac246.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i229\/49886437\/btac246.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T06:56:04Z","timestamp":1726988164000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/Supplement_1\/i229\/6617522"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":69,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2022,6,24]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac246","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,7,1]]},"published":{"date-parts":[[2022,6,24]]}}}