{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,4]],"date-time":"2026-07-04T00:48:05Z","timestamp":1783126085083,"version":"3.54.6"},"reference-count":43,"publisher":"Frontiers Media SA","license":[{"start":{"date-parts":[[2023,12,13]],"date-time":"2023-12-13T00:00:00Z","timestamp":1702425600000},"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","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["frontiersin.org"],"crossmark-restriction":true},"short-container-title":["Front. Bioinform."],"abstract":"<jats:p><jats:monospace>Proteinortho<\/jats:monospace> is a widely used tool to predict (co)-orthologous groups of genes for any set of species. It finds application in comparative and functional genomics, phylogenomics, and evolutionary reconstructions. With a rapidly increasing number of available genomes, the demand for large-scale predictions is also growing. In this contribution, we evaluate and implement major algorithmic improvements that significantly enhance the speed of the analysis without reducing precision. Graph-based detection of (co-)orthologs is typically based on a reciprocal best alignment heuristic that requires an all vs. all comparison of proteins from all species under study. The initial identification of similar proteins is accelerated by introducing an alternative search tool along with a revised search strategy\u2014the pseudo-reciprocal best alignment heuristic\u2014that reduces the number of required sequence comparisons by one-half. The clustering algorithm was reworked to efficiently decompose very large clusters and accelerate processing. <jats:monospace>Proteinortho6<\/jats:monospace> reduces the overall processing time by an order of magnitude compared to its predecessor while maintaining its small memory footprint and good predictive quality.<\/jats:p>","DOI":"10.3389\/fbinf.2023.1322477","type":"journal-article","created":{"date-parts":[[2023,12,13]],"date-time":"2023-12-13T05:04:59Z","timestamp":1702443899000},"update-policy":"https:\/\/doi.org\/10.3389\/crossmark-policy","source":"Crossref","is-referenced-by-count":47,"title":["Proteinortho6: pseudo-reciprocal best alignment heuristic for graph-based detection of (co-)orthologs"],"prefix":"10.3389","volume":"3","author":[{"given":"Paul","family":"Klemm","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marcus","family":"Lechner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1965","published-online":{"date-parts":[[2023,12,13]]},"reference":[{"key":"B1","unstructured":"benchmark-webservice\n            AltenhoffA.\n          2023"},{"key":"B2","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1038\/nmeth.3830","article-title":"Standardized benchmarking in the quest for orthologs","volume":"13","author":"Altenhoff","year":"2016","journal-title":"Nat. methods"},{"key":"B3","doi-asserted-by":"publisher","first-page":"e1000262","DOI":"10.1371\/journal.pcbi.1000262","article-title":"Phylogenetic and functional assessment of orthologs inference projects and methods","volume":"5","author":"Altenhoff","year":"2009","journal-title":"PLoS Comput. Biol."},{"key":"B4","doi-asserted-by":"publisher","first-page":"1152","DOI":"10.1101\/gr.243212.118","article-title":"Oma standalone: orthology inference among public and custom genomes and transcriptomes","volume":"29","author":"Altenhoff","year":"2019","journal-title":"Genome Res."},{"key":"B5","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719604","volume-title":"LAPACK Users\u2019 guide","author":"Anderson","year":"1999"},{"key":"B6","doi-asserted-by":"publisher","first-page":"D970","DOI":"10.1093\/nar\/gkab1005","article-title":"Echinobase: leveraging an extant model organism database to build a knowledgebase supporting research on the genomics and biology of echinoderms","volume":"50","author":"Arshinoff","year":"2022","journal-title":"Nucleic acids Res."},{"key":"B7","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1137\/030601107","article-title":"A parallel eigensolver for dense symmetric matrices based on multiple relatively robust representations","volume":"27","author":"Bientinesi","year":"2005","journal-title":"SIAM J. Sci. Comput."},{"key":"B8","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1006\/jmbi.1998.2144","article-title":"Predicting function: from genes to genomes and back 1 1Edited by P. E. Wright","volume":"283","author":"Bork","year":"1998","journal-title":"J. Mol. Biol."},{"key":"B9","doi-asserted-by":"publisher","first-page":"40","DOI":"10.48550\/arXiv.1311.2854","article-title":"Spectral clustering via the power method-provably","author":"Boutsidis","year":"2015","journal-title":"Int. Conf. Mach. Learn."},{"key":"B10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1038\/nmeth.3176","article-title":"Fast and sensitive protein alignment using DIAMOND","volume":"12","author":"Buchfink","year":"2015","journal-title":"Nat. methods"},{"key":"B11","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1186\/1471-2105-10-421","article-title":"Blast+: architecture and applications","volume":"10","author":"Camacho","year":"2009","journal-title":"BMC Bioinforma."},{"key":"B12","volume-title":"Participant dataset submitted by Sonicparanoid-sens","author":"Consentino","year":"2021"},{"key":"B13","first-page":"2023","volume-title":"Sonicparanoid2: fast, accurate, and comprehensive orthology inference with machine learning and language models","author":"Cosentino","year":"2023"},{"key":"B14","doi-asserted-by":"publisher","first-page":"2460","DOI":"10.1093\/bioinformatics\/btq461","article-title":"Search and clustering orders of magnitude faster than BLAST","volume":"26","author":"Edgar","year":"2010","journal-title":"Bioinforma. Oxf. Engl."},{"key":"B15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-019-1832-y","article-title":"Orthofinder: phylogenetic orthology inference for comparative genomics","volume":"20","author":"Emms","year":"2019","journal-title":"Genome Biol."},{"key":"B16","doi-asserted-by":"publisher","first-page":"619","DOI":"10.21136\/CMJ.1975.101357","article-title":"A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory","volume":"25","author":"Fiedler","year":"1975","journal-title":"Czechoslov. Math. J."},{"key":"B17","doi-asserted-by":"publisher","first-page":"99","DOI":"10.2307\/2412448","article-title":"Distinguishing homologous from analogous proteins","volume":"19","author":"Fitch","year":"1970","journal-title":"Syst. Zool."},{"key":"B18","volume-title":"Participant dataset submitted by OrthoMCL","author":"Hickman","year":"2021"},{"key":"B19","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","article-title":"Comparing partitions","volume":"2","author":"Hubert","year":"1985","journal-title":"J. Classif."},{"key":"B20","volume-title":"Reciprocal best hits are not a logically sufficient condition for orthology","author":"Johnson","year":"2007"},{"key":"B21","doi-asserted-by":"publisher","first-page":"1139","DOI":"10.1126\/science.aaa4788","article-title":"Genomic signatures of evolutionary transitions from solitary to group living","volume":"348","author":"Kapheim","year":"2015","journal-title":"Science"},{"key":"B22","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1101\/gr.229202","article-title":"Blat\u2013the BLAST-like alignment tool","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res."},{"key":"B23","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1101\/gr.113985.110","article-title":"Adaptive seeds tame genomic sequence comparison","volume":"21","author":"Kie\u0142basa","year":"2011","journal-title":"Genome Res."},{"key":"B24","doi-asserted-by":"publisher","first-page":"1034708","DOI":"10.3389\/fpls.2022.1034708","article-title":"Evolutionary reconstruction, nomenclature and functional meta-analysis of the Kiwellin protein family","volume":"13","author":"Klemm","year":"2022","journal-title":"Front. plant Sci."},{"key":"B25","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1146\/annurev.genet.39.073003.114725","article-title":"Orthologs, paralogs, and evolutionary genomics","volume":"39","author":"Koonin","year":"2005","journal-title":"Annu. Rev. Genet."},{"key":"B26","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1038\/nature01256","article-title":"The structure of the protein universe and genome evolution","volume":"420","author":"Koonin","year":"2002","journal-title":"Nature"},{"key":"B27","doi-asserted-by":"publisher","first-page":"i438","DOI":"10.1093\/bioinformatics\/bts417","article-title":"Sans: high-throughput retrieval of protein sequences allowing 50% mismatches","volume":"28","author":"Koskinen","year":"2012","journal-title":"Bioinforma. Oxf. Engl."},{"key":"B28","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1186\/1471-2105-12-124","article-title":"Proteinortho: detection of (co-) orthologs in large-scale analysis","volume":"12","author":"Lechner","year":"2011","journal-title":"BMC Bioinforma."},{"key":"B29","doi-asserted-by":"publisher","first-page":"1151","DOI":"10.1126\/science.290.5494.1151","article-title":"The evolutionary fate and consequences of duplicate genes","volume":"290","author":"Lynch","year":"2000","journal-title":"Science"},{"key":"B30","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1186\/s12859-018-2290-3","article-title":"Topaz: asymmetric suffix array neighbourhood search for massive protein databases","volume":"19","author":"Medlar","year":"2018","journal-title":"BMC Bioinforma."},{"key":"B31","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/978-3-658-21742-6_94","article-title":"The small world problem","author":"Milgram","year":"1967","journal-title":"Psychol. Today"},{"key":"B32","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1006\/scdb.1999.0332","article-title":"Gene duplication and the uniqueness of vertebrate genomes circa 1970-1999","volume":"10","author":"Ohno","year":"1999","journal-title":"Seminars Cell Dev. Biol."},{"key":"B33","volume-title":"Funannotate","author":"Palmer","year":"2023"},{"key":"B34","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0024-3795(99)00262-1","article-title":"Relatively robust representations of symmetric tridiagonals","volume":"309","author":"Parlett","year":"2000","journal-title":"Linear Algebra its Appl."},{"key":"B35","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1038\/s41586-018-0030-5","article-title":"Genome evolution across 1,011 Saccharomyces cerevisiae isolates","volume":"556","author":"Peter","year":"2018","journal-title":"Nature"},{"key":"B36","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1038\/nrmicro3088","article-title":"How to get (a) round: mechanisms controlling growth and division of coccoid bacteria","volume":"11","author":"Pinho","year":"2013","journal-title":"Nat. Rev. Microbiol."},{"key":"B37","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00285-021-01564-8","article-title":"Complete characterization of incorrect orthology assignments in best match graphs","volume":"82","author":"Schaller","year":"2021","journal-title":"J. Math. Biol."},{"key":"B38","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-1-4939-7463-4_1","article-title":"Gene phyologenies and orthologous groups","volume-title":"Comparative genomics","author":"Setubal","year":"2018"},{"key":"B39","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1109\/34.868688","article-title":"Normalized cuts and image segmentation","author":"Shi","year":"2000","journal-title":"Dep. Pap. (CIS)"},{"key":"B40","doi-asserted-by":"publisher","first-page":"1026","DOI":"10.1038\/nbt.3988","article-title":"MMseqs2 enables sensitive protein sequence searching for the analysis of massive data sets","volume":"35","author":"Steinegger","year":"2017","journal-title":"Nat. Biotechnol."},{"key":"B41","doi-asserted-by":"publisher","first-page":"D506","DOI":"10.1093\/nar\/gky1049","article-title":"Uniprot: a worldwide hub of protein knowledge","volume":"47","author":"UniProt-Consortium","year":"2018","journal-title":"Nucleic acids Res."},{"key":"B42","doi-asserted-by":"publisher","first-page":"e101850","DOI":"10.1371\/journal.pone.0101850","article-title":"Quickly finding orthologs as reciprocal best hits with BLAT, LAST, and UBLAST: how much do we miss?","volume":"9","author":"Ward","year":"2014","journal-title":"PloS one"},{"key":"B43","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1093\/bioinformatics\/btr595","article-title":"RAPSearch2: a fast and memory-efficient protein similarity search tool for next-generation sequencing data","volume":"28","author":"Zhao","year":"2012","journal-title":"Bioinforma. Oxf. Engl."}],"container-title":["Frontiers in Bioinformatics"],"original-title":[],"link":[{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fbinf.2023.1322477\/full","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,13]],"date-time":"2023-12-13T05:05:12Z","timestamp":1702443912000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.frontiersin.org\/articles\/10.3389\/fbinf.2023.1322477\/full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,13]]},"references-count":43,"alternative-id":["10.3389\/fbinf.2023.1322477"],"URL":"https:\/\/doi.org\/10.3389\/fbinf.2023.1322477","relation":{},"ISSN":["2673-7647"],"issn-type":[{"value":"2673-7647","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,13]]},"article-number":"1322477"}}