{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T00:45:02Z","timestamp":1740185102810,"version":"3.37.3"},"reference-count":42,"publisher":"Oxford University Press (OUP)","issue":"14","license":[{"start":{"date-parts":[[2019,7,8]],"date-time":"2019-07-08T00:00:00Z","timestamp":1562544000000},"content-version":"vor","delay-in-days":7,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP150100894"],"award-info":[{"award-number":["DP150100894"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,7,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title\/><jats:p>The information criterion of minimum message length (MML) provides a powerful statistical framework for inductive reasoning from observed data. We apply MML to the problem of protein sequence comparison using finite state models with Dirichlet distributions. The resulting framework allows us to supersede the ad hoc cost functions commonly used in the field, by systematically addressing the problem of arbitrariness in alignment parameters, and the disconnect between substitution scores and gap costs. Furthermore, our framework enables the generation of marginal probability landscapes over all possible alignment hypotheses, with potential to facilitate the users to simultaneously rationalize and assess competing alignment relationships between protein sequences, beyond simply reporting a single (best) alignment. We demonstrate the performance of our program on benchmarks containing distantly related protein sequences.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>The open-source program supporting this work is available from: http:\/\/lcb.infotech.monash.edu.au\/seqmmligner.<\/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\/btz368","type":"journal-article","created":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T11:32:12Z","timestamp":1557487932000},"page":"i360-i369","source":"Crossref","is-referenced-by-count":5,"title":["Statistical compression of protein sequences and inference of marginal probability landscapes over competing alignments using finite state models and Dirichlet priors"],"prefix":"10.1093","volume":"35","author":[{"given":"Dinithi","family":"Sumanaweera","sequence":"first","affiliation":[{"name":"Faculty of Information Technology, Monash University, Clayton, VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lloyd","family":"Allison","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Monash University, Clayton, VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arun S","family":"Konagurthu","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Monash University, Clayton, VIC, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,7,5]]},"reference":[{"key":"2023062712352676700_btz368-B1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-76433-7","volume-title":"Coding Ockham\u2019s Razor","author":"Allison","year":"2018"},{"key":"2023062712352676700_btz368-B2","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":"2023062712352676700_btz368-B3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/comjnl\/42.1.1","article-title":"Compression and approximate matching","volume":"42","author":"Allison","year":"1999","journal-title":"Comput. J"},{"key":"2023062712352676700_btz368-B4","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":"2023062712352676700_btz368-B5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1098\/rstl.1763.0044","article-title":"A letter from the late Reverend Mr. Thomas Bayes, FRS to John Canton, MA and FRS","volume":"53","author":"Bayes","year":"1763","journal-title":"Philos. Trans"},{"key":"2023062712352676700_btz368-B6","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":"2023062712352676700_btz368-B7","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1006\/jmbi.2001.4495","article-title":"Pairwise sequence alignment below the twilight zone1","volume":"307","author":"Blake","year":"2001","journal-title":"J. Mol. Biol"},{"key":"2023062712352676700_btz368-B8","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":"2023062712352676700_btz368-B9","first-page":"345","volume-title":"Atlas of Protein Sequence and Structure","author":"Dayhoff","year":"1978"},{"key":"2023062712352676700_btz368-B10","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":"2023062712352676700_btz368-B11","first-page":"160","volume-title":"Annual International Conference on Research in Computational Molecular Biology, Venice, Italy","author":"Do","year":"2006"},{"volume-title":"Of URFs and ORFs: A Primer on How to Analyze Derived Amino Acid Sequences","year":"1986","author":"Doolittle","key":"2023062712352676700_btz368-B12"},{"key":"2023062712352676700_btz368-B13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"Durbin","year":"1998"},{"key":"2023062712352676700_btz368-B14","doi-asserted-by":"crossref","first-page":"1792","DOI":"10.1093\/nar\/gkh340","article-title":"MUSCLE: multiple sequence alignment with high accuracy and high throughput","volume":"32","author":"Edgar","year":"2004","journal-title":"Nucleic Acids Res"},{"key":"2023062712352676700_btz368-B15","doi-asserted-by":"crossref","first-page":"1382","DOI":"10.1073\/pnas.80.5.1382","article-title":"Optimal sequence alignments","volume":"80","author":"Fitch","year":"1983","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023062712352676700_btz368-B16","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":"2023062712352676700_btz368-B17","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":"2023062712352676700_btz368-B18","doi-asserted-by":"crossref","first-page":"772","DOI":"10.1093\/molbev\/mst010","article-title":"Mafft multiple sequence alignment software version 7: improvements in performance and usability","volume":"30","author":"Katoh","year":"2013","journal-title":"Mol. Biol. Evol"},{"key":"2023062712352676700_btz368-B19","first-page":"369","article-title":"On tables of random numbers","volume":"25","author":"Kolmogorov","year":"1963","journal-title":"Sankhy\u0101"},{"key":"2023062712352676700_btz368-B20","doi-asserted-by":"crossref","first-page":"2947","DOI":"10.1093\/bioinformatics\/btm404","article-title":"Clustal W and Clustal X version 2.0","volume":"23","author":"Larkin","year":"2007","journal-title":"Bioinformatics"},{"key":"2023062712352676700_btz368-B21","doi-asserted-by":"crossref","first-page":"298.","DOI":"10.1186\/1471-2105-6-298","article-title":"KAlign\u2014an accurate and fast multiple sequence alignment algorithm","volume":"6","author":"Lassmann","year":"2005","journal-title":"BMC Bioinformatics"},{"key":"2023062712352676700_btz368-B22","doi-asserted-by":"crossref","DOI":"10.1093\/hesc\/9780198754831.001.0001","volume-title":"Introduction to Genomics","author":"Lesk","year":"2017"},{"key":"2023062712352676700_btz368-B23","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1093\/sysbio\/syy059","article-title":"A simulation-based approach to statistical alignment","volume":"68","author":"Levy Karin","year":"2019","journal-title":"Syst. Biol"},{"key":"2023062712352676700_btz368-B24","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":"2023062712352676700_btz368-B25","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":"2023062712352676700_btz368-B26","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","article-title":"T-coffee: a novel method for fast and accurate multiple sequence alignment1","volume":"302","author":"Notredame","year":"2000","journal-title":"J. Mol. Biol"},{"key":"2023062712352676700_btz368-B27","first-page":"203","volume-title":"Australian Conference on Artificial Intelligence","author":"Powell","year":"2004"},{"key":"2023062712352676700_btz368-B28","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1080\/10635150590947041","article-title":"Joint bayesian estimation of alignment and phylogeny","volume":"54","author":"Redelings","year":"2005","journal-title":"Syst. Biol"},{"key":"2023062712352676700_btz368-B29","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":"2023062712352676700_btz368-B30","doi-asserted-by":"crossref","DOI":"10.1525\/9780520943742","volume-title":"Sequence Alignment: Methods, Models, Concepts, and Strategies.","author":"Rosenberg","year":"2009"},{"key":"2023062712352676700_btz368-B31","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":"2023062712352676700_btz368-B32","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1109\/DCC.2018.00026","volume-title":"2018 Data Compression Conference, Snowbird, USA","author":"Sumanaweera","year":"2018"},{"key":"2023062712352676700_btz368-B33","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2012-13-2-r12","article-title":"Iterative orthology prediction uncovers new mitochondrial proteins and identifies c12orf62 as the human ortholog of cox14, a protein involved in the assembly of cytochrome c oxidase","volume":"13","author":"Szklarczyk","year":"2012","journal-title":"Genome Biol"},{"key":"2023062712352676700_btz368-B34","doi-asserted-by":"crossref","DOI":"10.1525\/9780520347533","volume-title":"Statistical Astronomy","author":"Trumpler","year":"1953"},{"key":"2023062712352676700_btz368-B35","doi-asserted-by":"crossref","first-page":"D158","DOI":"10.1093\/nar\/gkw1099","article-title":"UniProt: the universal protein knowledgebase","volume":"45","year":"2017","journal-title":"Nucleic Acids Res"},{"key":"2023062712352676700_btz368-B36","doi-asserted-by":"crossref","first-page":"1267","DOI":"10.1093\/bioinformatics\/bth493","article-title":"Sabmark-a benchmark for sequence alignment that covers the entire known fold space","volume":"21","author":"Van Walle","year":"2005","journal-title":"Bioinformatics"},{"key":"2023062712352676700_btz368-B37","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"},{"volume-title":"Statistical and Inductive Inference by Minimum Message Length","year":"2005","author":"Wallace","key":"2023062712352676700_btz368-B38"},{"key":"2023062712352676700_btz368-B39","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":"2023062712352676700_btz368-B40","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. Series B Methodol"},{"key":"2023062712352676700_btz368-B41","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1022646101185","article-title":"Coding decision trees","volume":"11","author":"Wallace","year":"1993","journal-title":"Machine Learning"},{"key":"2023062712352676700_btz368-B42","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1093\/bioinformatics\/14.1.25","article-title":"Bayesian adaptive sequence alignment algorithms","volume":"14","author":"Zhu","year":"1998","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/14\/i360\/50721218\/bioinformatics_35_14_i360.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/14\/i360\/50721218\/bioinformatics_35_14_i360.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,17]],"date-time":"2024-07-17T22:08:37Z","timestamp":1721254117000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/14\/i360\/5529258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":42,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2019,7,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz368","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2019,7]]},"published":{"date-parts":[[2019,7]]}}}