{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T12:05:23Z","timestamp":1767182723682,"version":"build-2065373602"},"reference-count":21,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T00:00:00Z","timestamp":1616976000000},"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":["STA 850\/49-1"],"award-info":[{"award-number":["STA 850\/49-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Best match graphs (BMGs) are vertex-colored digraphs that naturally arise in mathematical phylogenetics to formalize the notion of evolutionary closest genes w.r.t. an a priori unknown phylogenetic tree. BMGs are explained by unique least resolved trees. We prove that the property of a rooted, leaf-colored tree to be least resolved for some BMG is preserved by the contraction of inner edges. For the special case of two-colored BMGs, this leads to a characterization of the least resolved trees (LRTs) of binary-explainable trees and a simple, polynomial-time algorithm for the minimum cardinality completion of the arc set of a BMG to reach a BMG that can be explained by a binary tree.<\/jats:p>","DOI":"10.3390\/a14040110","type":"journal-article","created":{"date-parts":[[2021,3,29]],"date-time":"2021-03-29T16:01:57Z","timestamp":1617033717000},"page":"110","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Arc-Completion of 2-Colored Best Match Graphs to Binary-Explainable Best Match Graphs"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0025-3097","authenticated-orcid":false,"given":"David","family":"Schaller","sequence":"first","affiliation":[{"name":"Max Planck Institute for Mathematics in the Sciences, D-04103 Leipzig, Germany"},{"name":"Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universit\u00e4t Leipzig, D-04107 Leipzig, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4134-6820","authenticated-orcid":false,"given":"Manuela","family":"Gei\u00df","sequence":"additional","affiliation":[{"name":"Software Competence Center Hagenberg GmbH (SCCH), A-4232 Hagenberg, Austria"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1620-5508","authenticated-orcid":false,"given":"Marc","family":"Hellmuth","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Faculty of Science, Stockholm University, SE-10691 Stockholm, Sweden"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5016-5191","authenticated-orcid":false,"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Mathematics in the Sciences, D-04103 Leipzig, Germany"},{"name":"Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, Universit\u00e4t Leipzig, D-04107 Leipzig, Germany"},{"name":"German Centre for Integrative Biodiversity, Research (iDiv) Halle-Jena-Leipzig, Competence Center for Scalable Data Services and Solutions, Leipzig Research Center for Civilization Diseases, and Leipzig Research Center for Civilization Diseases (LIFE), Leipzig University, D-04103 Leipzig, Germany"},{"name":"Institute for Theoretical Chemistry, University of Vienna, A-1090 Wien, Austria"},{"name":"Facultad de Ciencias, Universidad National de Colombia, CO-111321 Bogot\u00e1, Colombia"},{"name":"Santa Fe Institute, Santa Fe, NM 87501, USA"}]}],"member":"1968","published-online":{"date-parts":[[2021,3,29]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"2015","DOI":"10.1007\/s00285-019-01332-9","article-title":"Best Match Graphs","volume":"78","author":"Stadler","year":"2019","journal-title":"J. Math. Biol."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Schaller, D., Gei\u00df, M., Ch\u00e1vez, E., Gonz\u00e1lez Laffitte, M., L\u00f3pez S\u00e1nchez, A., Stadler, B.M.R., Valdivia, D.I., Hellmuth, M., Hern\u00e1ndez Rosales, M., and Stadler, P.F. (2021). Corrigendum to \u201cBest Match Graphs\u201d. J. Math. Biol., in press.","DOI":"10.1007\/s00285-021-01601-6"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Korchmaros, A. (2020). The Structure of 2-Colored Best Match Graphs. arXiv.","DOI":"10.1016\/j.dam.2021.08.007"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Korchmaros, A. (2020). Circles and Paths in 2-Colored Best Match Graphs. arXiv.","DOI":"10.1016\/j.dam.2021.08.007"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"R10","DOI":"10.37236\/1627","article-title":"Generating a random sink-free orientation in quadratic time","volume":"9","author":"Cohn","year":"2002","journal-title":"Electr. J. Comb."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"168","DOI":"10.4169\/002557010X494814","article-title":"The Graph Menagerie: Abstract Algebra and the Mad Veterinarian","volume":"83","author":"Abrams","year":"2010","journal-title":"Math. Mag."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Das, S., Ghosh, P., Ghosh, S., and Sen, S. (2020). Oriented Bipartite Graphs and the Goldbach Graph. arXiv.","DOI":"10.1016\/j.disc.2021.112497"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0166-218X(00)00391-7","article-title":"Complexity Classification of Some Edge Modification Problems","volume":"113","author":"Natanzon","year":"2001","journal-title":"Discr. Appl. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2058","DOI":"10.1073\/pnas.1412770112","article-title":"Phylogenetics from Paralogs","volume":"112","author":"Hellmuth","year":"2015","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.tcs.2021.02.037","article-title":"Complexity of Modification Problems for Best Match Graphs","volume":"865","author":"Schaller","year":"2021","journal-title":"Theor. Comp. Sci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1111\/j.1096-0031.1989.tb00569.x","article-title":"Reconstructing character evolution on polytomous cladograms","volume":"5","author":"Maddison","year":"1989","journal-title":"Cladistics"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0169-5347(94)90034-5","article-title":"Speciation and phylogenetic resolution","volume":"9","author":"DeSalle","year":"1994","journal-title":"Trends Ecol. Evol."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/0169-5347(94)90207-0","article-title":"Patterns of speciation and limits to phylogenetic resolution","volume":"9","author":"Hoelzer","year":"1994","journal-title":"Trends Ecol. Evol."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1006\/mpev.2000.0897","article-title":"Molecular Polytomies","volume":"19","author":"Slowinski","year":"2001","journal-title":"Mol. Phylog. Evol."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Schaller, D., Gei\u00df, M., Hellmuth, M., and Stadler, P.F. (2021). Best Match Graphs with Binary Trees. Proceedings of the 8th International Conference on Algorithms for Computational Biology, Missoula, MO, USA, 8\u201311 November 2021, Springer Nature. in press.","DOI":"10.1007\/978-3-030-74432-8_6"},{"key":"ref_16","doi-asserted-by":"crossref","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":"ref_17","doi-asserted-by":"crossref","unstructured":"Schaller, D., Gei\u00df, M., Hellmuth, M., and Stadler, P.F. (2021). Heuristic Algorithms for Best Match Graph Editing. arXiv.","DOI":"10.1186\/s13015-021-00196-3"},{"key":"ref_18","first-page":"110","article-title":"Cograph Editing: Complexity and Parametrized Algorithms","volume":"Volume 6842","author":"Fu","year":"2011","journal-title":"COCOON 2011"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"2763","DOI":"10.1016\/j.disc.2013.08.017","article-title":"The cluster deletion problem for cographs","volume":"313","author":"Gao","year":"2013","journal-title":"Discret. Math."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Schaller, D., Gei\u00df, M., Hellmuth, M., and Stadler, P.F. (2021). Least resolved trees for two-colored best match graphs. arXiv.","DOI":"10.7155\/jgaa.00564"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1007\/s00285-019-01444-2","article-title":"Reciprocal Best Match Graphs","volume":"80","author":"Stadler","year":"2020","journal-title":"J. Math. Biol."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/110\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:10:22Z","timestamp":1760364622000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/4\/110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,29]]},"references-count":21,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["a14040110"],"URL":"https:\/\/doi.org\/10.3390\/a14040110","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,3,29]]}}}