{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T09:10:12Z","timestamp":1759396212354,"version":"build-2065373602"},"reference-count":90,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T00:00:00Z","timestamp":1759363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T00:00:00Z","timestamp":1759363200000},"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":["MI439\/14-2"],"award-info":[{"award-number":["MI439\/14-2"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Orthologous genes, which arise through speciation, play a key role in comparative genomics and functional inference. In particular, graph-based methods allow for the inference of orthology estimates without prior knowledge of the underlying gene or species trees. This results in orthology graphs, where each vertex represents a gene, and an edge exists between two vertices if the corresponding genes are estimated to be orthologs. Orthology graphs inferred under a tree-like evolutionary model must be cographs. However, real-world data often deviate from this property, either due to noise in the data, errors in inference methods or, simply, because evolution follows a network-like rather than a tree-like process. The latter, in particular, raises the question of whether and how orthology graphs can be derived from or, equivalently, are <jats:italic>explained by<\/jats:italic> phylogenetic networks. In this work, we study the constraints imposed on orthology graphs when the underlying evolutionary history follows a phylogenetic network instead of a tree. We show that any orthology graph can be represented by a sufficiently complex level-k network. However, such networks lack biologically meaningful constraints. In contrast, level-1 networks provide a simpler explanation, and we establish characterizations for level-1 explainable orthology graphs, i.e., those derived from level-1 evolutionary histories. To this end, we employ modular decomposition, a classical technique for studying graph structures. Specifically, an arbitrary graph is level-1 explainable if and only if each primitive subgraph is a near-cograph (a graph in which the removal of a single vertex results in a cograph). Additionally, we present a linear-time algorithm to recognize level-1 explainable orthology graphs and to construct a level-1 network that explains them, if such a network exists. Finally, we demonstrate the close relationship of level-1 explainable orthology graphs to the substitution operation, weakly chordal and perfect graphs, as well as graphs with twin-width at most 2.<\/jats:p>","DOI":"10.1186\/s13015-025-00285-7","type":"journal-article","created":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T08:40:26Z","timestamp":1759394426000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Orthology and near-cographs in the context of phylogenetic networks"],"prefix":"10.1186","volume":"20","author":[{"given":"Anna","family":"Lindeberg","sequence":"first","affiliation":[]},{"given":"Guillaume E.","family":"Scholz","sequence":"additional","affiliation":[]},{"given":"Nicolas","family":"Wieseke","sequence":"additional","affiliation":[]},{"given":"Marc","family":"Hellmuth","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,2]]},"reference":[{"key":"285_CR1","doi-asserted-by":"publisher","first-page":"99","DOI":"10.2307\/2412448","volume":"19","author":"WM Fitch","year":"1970","unstructured":"Fitch WM. Distinguishing homologous from analogous proteins. Syst Zool. 1970;19:99\u2013113. https:\/\/doi.org\/10.2307\/2412448.","journal-title":"Syst Zool"},{"key":"285_CR2","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1016\/S0168-9525(00)02005-9","volume":"16","author":"WM Fitch","year":"2000","unstructured":"Fitch WM. Homology: a personal view on some of the problems. Trends Genet. 2000;16:227\u201331. https:\/\/doi.org\/10.1016\/S0168-9525(00)02005-9.","journal-title":"Trends Genet"},{"key":"285_CR3","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1093\/oxfordjournals.molbev.a040298","volume":"1","author":"GS Gray","year":"1983","unstructured":"Gray GS, Fitch WM. Evolution of antibiotic resistance genes: the DNA sequence of a kanamycin resistance gene from Staphylococcus aureus. Mol Biol Evol. 1983;1:57\u201366. https:\/\/doi.org\/10.1093\/oxfordjournals.molbev.a040298.","journal-title":"Mol Biol Evol"},{"issue":"6","key":"285_CR4","doi-asserted-by":"publisher","first-page":"1306","DOI":"10.1002\/pro.143","volume":"18","author":"ME Peterson","year":"2009","unstructured":"Peterson ME, Chen F, Saven JG, Roos DS, Babbitt PC, Sali A. Evolutionary constraints on structural similarity in orthologs and paralogs. Protein Sci. 2009;18(6):1306\u201315.","journal-title":"Protein Sci"},{"issue":"5","key":"285_CR5","doi-asserted-by":"publisher","first-page":"1002514","DOI":"10.1371\/journal.pcbi.1002514","volume":"8","author":"AM Altenhoff","year":"2012","unstructured":"Altenhoff AM, Studer RA, Robinson-Rechavi M, Dessimoz C. Resolving the ortholog conjecture: orthologs tend to be weakly, but significantly, more similar in function than paralogs. PLoS Comput Biol. 2012;8(5):1002514.","journal-title":"PLoS Comput Biol"},{"issue":"3","key":"285_CR6","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1101\/gr.8.3.163","volume":"8","author":"JA Eisen","year":"1998","unstructured":"Eisen JA. Phylogenomics: improving functional predictions for uncharacterized genes by evolutionary analysis. Genome Res. 1998;8(3):163\u20137. https:\/\/doi.org\/10.1101\/gr.8.3.163.","journal-title":"Genome Res"},{"issue":"5","key":"285_CR7","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1093\/bib\/bbr024","volume":"12","author":"K Forslund","year":"2011","unstructured":"Forslund K, Schreiber F, Thanintorn N, Sonnhammer EL. Orthodisease: tracking disease gene orthologs across 100 species. Brief Bioinform. 2011;12(5):463\u201373. https:\/\/doi.org\/10.1093\/bib\/bbr024.","journal-title":"Brief Bioinform"},{"issue":"5","key":"285_CR8","doi-asserted-by":"publisher","first-page":"872","DOI":"10.15252\/msb.20156777","volume":"12","author":"S Chandrasekaran","year":"2016","unstructured":"Chandrasekaran S, Cokol-Cakmak M, Sahin N, Yilancioglu K, Kazan H, Collins JJ, Cokol M. Chemogenomics and orthology-based design of antibiotic combination therapies. Mol Syst Biol. 2016;12(5):872. https:\/\/doi.org\/10.15252\/msb.20156777.","journal-title":"Mol Syst Biol"},{"issue":"11","key":"285_CR9","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/j.tig.2008.08.009","volume":"24","author":"A Kuzniar","year":"2008","unstructured":"Kuzniar A, Ham RCHJ, Pongor S, Leunissen JAM. The quest for orthologs: finding the corresponding gene across genomes. Trends Genet. 2008;24(11):539\u201351. https:\/\/doi.org\/10.1016\/j.tig.2008.08.009.","journal-title":"Trends Genet"},{"issue":"5","key":"285_CR10","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1093\/bib\/bbr030","volume":"12","author":"DM Kristensen","year":"2011","unstructured":"Kristensen DM, Wolf YI, Mushegian AR, Koonin EV. Computational methods for gene orthology inference. Brief Bioinform. 2011;12(5):379\u201391. https:\/\/doi.org\/10.1093\/bib\/bbr030.","journal-title":"Brief Bioinform"},{"key":"285_CR11","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-1-4939-9074-0_5","volume-title":"Inferring orthology and paralogy","author":"AM Altenhoff","year":"2019","unstructured":"Altenhoff AM, Glover NM, Dessimoz C. Inferring orthology and paralogy. New York: Springer; 2019. p. 149\u201375. https:\/\/doi.org\/10.1007\/978-1-4939-9074-0_5."},{"key":"285_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-12-S1-S15","volume":"12","author":"P G\u00f3recki","year":"2011","unstructured":"G\u00f3recki P, Burleigh GJ, Eulenstein O. Maximum likelihood models and algorithms for gene tree evolution with duplications and losses. BMC Bioinform. 2011;12:1\u20139. https:\/\/doi.org\/10.1186\/1471-2105-12-S1-S15.","journal-title":"BMC Bioinform"},{"issue":"3","key":"285_CR13","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1093\/sysbio\/syu007","volume":"63","author":"J Sj\u00f6strand","year":"2014","unstructured":"Sj\u00f6strand J, Tofigh A, Daubin V, Arvestad L, Sennblad B, Lagergren J. A Bayesian method for analyzing lateral gene transfer. Syst Biol. 2014;63(3):409\u201320. https:\/\/doi.org\/10.1093\/sysbio\/syu007.","journal-title":"Syst Biol"},{"issue":"11","key":"285_CR14","doi-asserted-by":"publisher","first-page":"1010621","DOI":"10.1371\/journal.pcbi.1010621","volume":"18","author":"H Menet","year":"2022","unstructured":"Menet H, Daubin V, Tannier E. Phylogenetic reconciliation. PLoS Comput Biol. 2022;18(11):1010621. https:\/\/doi.org\/10.1371\/journal.pcbi.1010621.","journal-title":"PLoS Comput Biol"},{"issue":"2","key":"285_CR15","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1109\/TCBB.2010.14","volume":"8","author":"A Tofigh","year":"2010","unstructured":"Tofigh A, Hallett M, Lagergren J. Simultaneous identification of duplications and lateral gene transfers. IEEE\/ACM Trans Comput Biol Bioinf. 2010;8(2):517\u201335. https:\/\/doi.org\/10.1109\/TCBB.2010.14.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"285_CR16","doi-asserted-by":"publisher","first-page":"2178","DOI":"10.1101\/gr.1224503","volume":"13","author":"L Li","year":"2003","unstructured":"Li L, Stoeckert CJ Jr, Roos DS. OrthoMCL: identification of ortholog groups for eukaryotic genomes. Genome Res. 2003;13:2178\u201389. https:\/\/doi.org\/10.1101\/gr.1224503.","journal-title":"Genome Res"},{"key":"285_CR17","doi-asserted-by":"publisher","DOI":"10.3389\/fbinf.2023.1322477","author":"P Klemm","year":"2023","unstructured":"Klemm P, Stadler PF, Lechner M. Proteinrtho6: pseudo-reciprocal best alignment heuristic for graph-based detection of (co-)orthologs. Front Bioinform. 2023. https:\/\/doi.org\/10.3389\/fbinf.2023.1322477.","journal-title":"Front Bioinform"},{"issue":"1","key":"285_CR18","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1186\/1471-2105-12-124","volume":"12","author":"M Lechner","year":"2011","unstructured":"Lechner M, Findei\u00df S, Steiner L, Marz M, Stadler PF, Prohaska SJ. Proteinortho: Detection of (co-)orthologs in large-scale analysis. BMC Bioinform. 2011;12(1):124. https:\/\/doi.org\/10.1186\/1471-2105-12-124.","journal-title":"BMC Bioinform"},{"key":"285_CR19","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1186\/1471-2105-9-518","volume":"9","author":"ACJ Roth","year":"2008","unstructured":"Roth ACJ, Gonnet GH, Dessimoz C. Algorithm of OMA for large-scale orthology inference. BMC Bioinform. 2008;9:518. https:\/\/doi.org\/10.1186\/1471-2105-9-518.","journal-title":"BMC Bioinform"},{"key":"285_CR20","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1093\/nar\/gkm796","volume":"36","author":"LJ Jensen","year":"2008","unstructured":"Jensen LJ, Julien P, Kuhn M, Mering C, Muller J, Doerks T, Bork P. eggNOG: automated construction and annotation of orthologous groups of genes. Nucleic Acids Res. 2008;36:250\u20132504. https:\/\/doi.org\/10.1093\/nar\/gkm796.","journal-title":"Nucleic Acids Res"},{"key":"285_CR21","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1038\/nmeth.3830","volume":"13","author":"AM Altenhoff","year":"2016","unstructured":"...Altenhoff AM, Boeckmann B, Capella-Gutierrez S, Dalquen DA, De Luca T, Forslund K, Huerta-Cepas J, Linard B, Pereira C, Pryszcz LP, Schreiber F, Silva A, Szklarczyk D, Train CM, Bork P, Lecompte O, Mering C, Xenarios I, Sj\u00f6lander K, Juhl Jensen L, Martin MJ, Muffato M, Gabald\u00f3n T, Lewis SE, Thomas PD, Sonnhammer E, Dessimoz C, Quest for Orthologs consortium. Standardized benchmarking in the quest for orthologs. Nat Methods. 2016;13:425\u201330. https:\/\/doi.org\/10.1038\/nmeth.3830.","journal-title":"Nat Methods"},{"key":"285_CR22","doi-asserted-by":"publisher","first-page":"165","DOI":"10.3389\/fgene.2017.00165","volume":"8","author":"BTL Nichio","year":"2017","unstructured":"Nichio BTL, Marchaukoski JN, Raittz RT. New tools in orthology analysis: a brief review of promising perspectives. Front Genet. 2017;8:165. https:\/\/doi.org\/10.3389\/fgene.2017.00165.","journal-title":"Front Genet"},{"key":"285_CR23","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1093\/bioinformatics\/18.1.92","volume":"18","author":"CE Storm","year":"2002","unstructured":"Storm CE, Sonnhammer EL. Automated ortholog inference from phylogenetic trees and calculation of orthology reliability. Bioinformatics. 2002;18:92\u20139. https:\/\/doi.org\/10.1093\/bioinformatics\/18.1.92.","journal-title":"Bioinformatics"},{"key":"285_CR24","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1093\/nar\/gkp373","volume":"37","author":"RS Datta","year":"2009","unstructured":"Datta RS, Meacham C, Samad B, Neyer C, Sj\u00f6lander K. Berkeley PHOG: PhyloFacts orthology group prediction web server. Nucleic Acids Res. 2009;37:84\u20139. https:\/\/doi.org\/10.1093\/nar\/gkp373.","journal-title":"Nucleic Acids Res"},{"key":"285_CR25","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1101\/gr.073585.107","volume":"19","author":"AJ Vilella","year":"2009","unstructured":"Vilella AJ, Severin J, Ureta-Vidal A, Heng L, Durbin R, Birney E. EnsemblCompara GeneTrees: complete, duplication-aware phylogenetic trees in vertebrates. Genome Res. 2009;19:327\u201335. https:\/\/doi.org\/10.1101\/gr.073585.107.","journal-title":"Genome Res"},{"key":"285_CR26","doi-asserted-by":"publisher","first-page":"2596","DOI":"10.1093\/bioinformatics\/bti325","volume":"21","author":"JF Dufayard","year":"2005","unstructured":"Dufayard JF, Duret L, Penel S, Gouy M, Rechenmann F, Perriere G. Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases. Bioinformatics. 2005;21:2596\u2013603. https:\/\/doi.org\/10.1093\/bioinformatics\/bti325.","journal-title":"Bioinformatics"},{"issue":"5338","key":"285_CR27","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1126\/science.278.5338.631","volume":"278","author":"RL Tatusov","year":"1997","unstructured":"Tatusov RL, Koonin EV, Lipman DJ. A genomic perspective on protein families. Science. 1997;278(5338):631\u20137. https:\/\/doi.org\/10.1126\/science.278.5338.631.","journal-title":"Science"},{"key":"285_CR28","doi-asserted-by":"publisher","unstructured":"Dessimoz C, Cannarozzi G, Gil M, Margadant D, Roth A, Schneider A, Gonnet GH. Oma, a comprehensive, automated project for the identification of orthologs from complete genome data: introduction and first achievements. In: Comparative genomics: RECOMB 2005 international workshop, RCG 2005, Dublin, Ireland, September 18\u201320, 2005. Proceedings 3; 2005. p. 61\u201372. https:\/\/doi.org\/10.1007\/11554714_6 . Springer","DOI":"10.1007\/11554714_6"},{"issue":"1\u20132","key":"285_CR29","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00285-012-0525-x","volume":"66","author":"M Hellmuth","year":"2013","unstructured":"Hellmuth M, Hernandez-Rosales M, Huber KT, Moulton V, Stadler PF, Wieseke N. Orthology relations, symbolic ultrametrics, and cographs. J Math Biol. 2013;66(1\u20132):399\u2013420. https:\/\/doi.org\/10.1007\/s00285-012-0525-x.","journal-title":"J Math Biol"},{"issue":"7","key":"285_CR30","doi-asserted-by":"publisher","first-page":"2058","DOI":"10.1073\/pnas.1412770112","volume":"112","author":"M Hellmuth","year":"2015","unstructured":"Hellmuth M, Wieseke N, Lechner M, Lenhof HP, Middendorf M, Stadler PF. Phylogenomics with paralogs. PNAS. 2015;112(7):2058\u201363. https:\/\/doi.org\/10.1073\/pnas.1412770112.","journal-title":"PNAS"},{"key":"285_CR31","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1016\/j.procs.2017.05.047","volume":"108","author":"R Dondi","year":"2017","unstructured":"Dondi R, Mauri G, Zoppis I. Orthology correction for gene tree reconstruction: theoretical and experimental results. Procedia Comput Sci. 2017;108:1115\u201324. https:\/\/doi.org\/10.1016\/j.procs.2017.05.047.","journal-title":"Procedia Comput Sci"},{"issue":"7005","key":"285_CR32","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1038\/nature02848","volume":"431","author":"MC Rivera","year":"2004","unstructured":"Rivera MC, Lake JA. The ring of life provides evidence for a genome fusion origin of eukaryotes. Nature. 2004;431(7005):152\u20135. https:\/\/doi.org\/10.1038\/nature02848.","journal-title":"Nature"},{"issue":"1","key":"285_CR33","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.tig.2004.11.007","volume":"21","author":"SK Kummerfeld","year":"2005","unstructured":"Kummerfeld SK, Teichmann SA. Relative rates of gene fusion and fission in multi-domain proteins. Trends Genet. 2005;21(1):25\u201330. https:\/\/doi.org\/10.1016\/j.tig.2004.11.007.","journal-title":"Trends Genet"},{"key":"285_CR34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974076","volume-title":"Phylogenetic networks: concepts, algorithms and applications","author":"DH Huson","year":"2010","unstructured":"Huson DH, Rupp R, Scornavacca C. Phylogenetic networks: concepts, algorithms and applications. Cambridge: Cambridge University Press; 2010."},{"issue":"6","key":"285_CR35","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00285-022-01746-y","volume":"84","author":"S Kong","year":"2022","unstructured":"Kong S, Pons JC, Kubatko L, Wicke K. Classes of explicit phylogenetic networks and their biological and mathematical significance. J Math Biol. 2022;84(6):47. https:\/\/doi.org\/10.1007\/s00285-022-01746-y.","journal-title":"J Math Biol"},{"issue":"4","key":"285_CR36","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s12064-023-00398-w","volume":"142","author":"M Hellmuth","year":"2023","unstructured":"Hellmuth M, Schaller D, Stadler PF. Clustering systems of phylogenetic networks. Theory Biosci. 2023;142(4):301\u201358. https:\/\/doi.org\/10.1007\/s12064-023-00398-w.","journal-title":"Theory Biosci"},{"key":"285_CR37","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.dam.2022.06.042","volume":"321","author":"M Hellmuth","year":"2022","unstructured":"Hellmuth M, Scholz GE. From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats. Discret Appl Math. 2022;321:179\u2013219. https:\/\/doi.org\/10.1016\/j.dam.2022.06.042.","journal-title":"Discret Appl Math"},{"key":"285_CR38","doi-asserted-by":"crossref","unstructured":"Lindeberg A, Scholz GE, Hellmuth M. Network representation and modular decomposition of combinatorial structures: a galled-tree perspective. Vietnam Journal of Mathematics 2024; Special Issue dedicated to the memory of Andreas Dress (to appear, preprint arXiv:2406.18713)","DOI":"10.1007\/s10013-025-00747-w"},{"key":"285_CR39","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.dam.2023.09.034","volume":"343","author":"M Hellmuth","year":"2024","unstructured":"Hellmuth M, Scholz GE. Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs. Discret Appl Math. 2024;343:25\u201343. https:\/\/doi.org\/10.1016\/j.dam.2023.09.034.","journal-title":"Discret Appl Math"},{"issue":"1","key":"285_CR40","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00453-016-0241-9","volume":"80","author":"KT Huber","year":"2018","unstructured":"Huber KT, Scholz GE. Beyond representing orthology relations by trees. Algorithmica. 2018;80(1):73\u2013103. https:\/\/doi.org\/10.1007\/s00453-016-0241-9.","journal-title":"Algorithmica"},{"key":"285_CR41","doi-asserted-by":"publisher","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A. Polynomial algorithms for perfect graphs. In: Berge, C., Chv\u00e1tal, V. (eds.) Topics on perfect graphs. North-Holland Mathematics Studies, vol 88; 1984. p. 325\u201356. North-Holland, Netherlands . https:\/\/doi.org\/10.1016\/S0304-0208(08)72943-8","DOI":"10.1016\/S0304-0208(08)72943-8"},{"issue":"5","key":"285_CR42","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/21M142188X","volume":"53","author":"E Bonnet","year":"2024","unstructured":"Bonnet E, Geniet C, Kim EJ, Thomass\u00e9 S, Watrigant R. Twin-width III: max independent set, min dominating set, and coloring. SIAM J Comput. 2024;53(5):1602\u201340. https:\/\/doi.org\/10.1137\/21M142188X.","journal-title":"SIAM J Comput"},{"issue":"1","key":"285_CR43","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/3486655","volume":"69","author":"E Bonnet","year":"2021","unstructured":"Bonnet E, Kim EJ, Thomass\u00e9 S, Watrigant R. Twin-width I: tractable FO model checking. J ACM. 2021;69(1):46. https:\/\/doi.org\/10.1145\/3486655.","journal-title":"J ACM"},{"key":"285_CR44","doi-asserted-by":"publisher","unstructured":"Lindeberg A, Hellmuth M. Simplifying and characterizing DAGs and phylogenetic networks via least common ancestor constraints. Bulletin of Mathematical Biology; 2024. https:\/\/doi.org\/10.1007\/s11538-025-01419-z . (to appear, preprint arXiv:2411.00708","DOI":"10.1007\/s11538-025-01419-z"},{"key":"285_CR45","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-031-52213-0_11","volume-title":"Algorithms and discrete applied mathematics","author":"AV Shanavas","year":"2024","unstructured":"Shanavas AV, Changat M, Hellmuth M, Stadler PF. Unique least common ancestors and clusters in directed acyclic graphs. In: Kalyanasundaram S, Maheshwari A, editors. Algorithms and discrete applied mathematics. Cham: Springer; 2024. p. 148\u201361. https:\/\/doi.org\/10.1007\/978-3-031-52213-0_11."},{"key":"285_CR46","volume-title":"Phylogenetics. Oxford lecture series in mathematics and its applications","author":"C Semple","year":"2003","unstructured":"Semple C, Steel M. Phylogenetics. Oxford lecture series in mathematics and its applications, vol. 24. Oxford: Oxford University Press; 2003."},{"key":"285_CR47","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00026-004-0228-0","volume":"8","author":"M Baroni","year":"2005","unstructured":"Baroni M, Semple C, Steel M. A framework for representing reticulate evolution. Ann Comb. 2005;8:391\u2013408. https:\/\/doi.org\/10.1007\/s00026-004-0228-0.","journal-title":"Ann Comb"},{"issue":"4","key":"285_CR48","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil DG, Perl Y, Stewart LK. A linear recognition algorithm for cographs. SIAM J Comput. 1985;14(4):926\u201334. https:\/\/doi.org\/10.1137\/0214065.","journal-title":"SIAM J Comput"},{"issue":"3","key":"285_CR49","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil DG, Lerchs H, Burlingham LS. Complement reducible graphs. Discret Appl Math. 1981;3(3):163\u201374. https:\/\/doi.org\/10.1016\/0166-218X(81)90013-5.","journal-title":"Discret Appl Math"},{"issue":"4","key":"285_CR50","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1017\/S1446788700029232","volume":"18","author":"DP Sumner","year":"1974","unstructured":"Sumner DP. Dacey graphs. J Aust Math Soc. 1974;18(4):492\u2013502. https:\/\/doi.org\/10.1017\/S1446788700029232.","journal-title":"J Aust Math Soc"},{"issue":"2","key":"285_CR51","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D Seinsche","year":"1974","unstructured":"Seinsche D. On a property of the class of n-colorable graphs. J Combinat Theory Ser B. 1974;16(2):191\u20133. https:\/\/doi.org\/10.1016\/0095-8956(74)90063-X.","journal-title":"J Combinat Theory Ser B"},{"key":"285_CR52","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2021.12.017","volume":"310","author":"C Bruckmann","year":"2022","unstructured":"Bruckmann C, Stadler PF, Hellmuth M. From modular decomposition trees to rooted median graphs. Discret Appl Math. 2022;310:1\u20139. https:\/\/doi.org\/10.1016\/j.dam.2021.12.017.","journal-title":"Discret Appl Math"},{"key":"285_CR53","unstructured":"Hellmuth M, Lindeberg A. Characterizing and transforming DAGs within the I-LCA framework; 2024. https:\/\/arxiv.org\/abs\/2411.14057"},{"issue":"2","key":"285_CR54","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0022-0000(80)90060-4","volume":"20","author":"JM Lewis","year":"1980","unstructured":"Lewis JM, Yannakakis M. The node-deletion problem for hereditary properties is NP-complete. J Comput Syst Sci. 1980;20(2):219\u201330. https:\/\/doi.org\/10.1016\/0022-0000(80)90060-4.","journal-title":"J Comput Syst Sci"},{"issue":"3","key":"285_CR55","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0012-365X(73)90100-3","volume":"6","author":"DP Sumner","year":"1973","unstructured":"Sumner DP. Graphs indecomposable with respect to the X-join. Discret Math. 1973;6(3):281\u201398. https:\/\/doi.org\/10.1016\/0012-365X(73)90100-3.","journal-title":"Discret Math"},{"issue":"1","key":"285_CR56","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M Habib","year":"2010","unstructured":"Habib M, Paul C. A survey of the algorithmic aspects of modular decomposition. Comput Sci Rev. 2010;4(1):41\u201359. https:\/\/doi.org\/10.1016\/j.cosrev.2010.01.001.","journal-title":"Comput Sci Rev"},{"key":"285_CR57","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-94-009-5315-4_1","volume-title":"Graphs and order: the role of graphs in the theory of ordered sets and its applications","author":"D Kelly","year":"1985","unstructured":"Kelly D. Comparability graphs. In: Rival I, editor. Graphs and order: the role of graphs in the theory of ordered sets and its applications. Springer: Dordrecht; 1985. p. 3\u201340. https:\/\/doi.org\/10.1007\/978-94-009-5315-4_1."},{"issue":"1","key":"285_CR58","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BF02020961","volume":"18","author":"T Gallai","year":"1967","unstructured":"Gallai T. Transitiv orientierbare Graphen. Acta Mathematica Academiae Scientiarum Hungarica. 1967;18(1):25\u201366. https:\/\/doi.org\/10.1007\/BF02020961.","journal-title":"Acta Mathematica Academiae Scientiarum Hungarica"},{"issue":"1","key":"285_CR59","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1090\/S0002-9939-1976-0505776-7","volume":"54","author":"M Aschbacher","year":"1976","unstructured":"Aschbacher M. A homomorphism theorem for finite graphs. Proc Am Math Soc. 1976;54(1):468\u201370. https:\/\/doi.org\/10.1090\/S0002-9939-1976-0505776-7.","journal-title":"Proc Am Math Soc"},{"issue":"1","key":"285_CR60","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/jgt.3190020104","volume":"2","author":"A Blass","year":"1978","unstructured":"Blass A. Graphs with unique maximal clumpings. J Graph Theory. 1978;2(1):19\u201324. https:\/\/doi.org\/10.1002\/jgt.3190020104.","journal-title":"J Graph Theory"},{"key":"285_CR61","doi-asserted-by":"publisher","unstructured":"M\u00f6hring RH, Radermacher FJ. Substitution decomposition for discrete structures and connections with combinatorial optimization. In: Burkard RE, Cuninghame-Green RA, Zimmermann U, editors. Algebraic and combinatorial methods in operations research. North-Holland Mathematics Studies, vol. 95, pp. 257\u2013355. North-Holland, Netherlands; 1984. https:\/\/doi.org\/10.1016\/S0304-0208(08)72966-9","DOI":"10.1016\/S0304-0208(08)72966-9"},{"issue":"1","key":"285_CR62","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/BF02022041","volume":"4","author":"RH M\u00f6hring","year":"1985","unstructured":"M\u00f6hring RH. Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions. Ann Oper Res. 1985;4(1):195\u2013225. https:\/\/doi.org\/10.1007\/BF02022041.","journal-title":"Ann Oper Res"},{"issue":"3","key":"285_CR63","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(90)90129-6","volume":"70","author":"A Ehrenfeucht","year":"1990","unstructured":"Ehrenfeucht A, Rozenberg G. Theory of 2-structures, part I: clans, basic subclasses, and morphisms. Theoret Comput Sci. 1990;70(3):277\u2013303. https:\/\/doi.org\/10.1016\/0304-3975(90)90129-6.","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"285_CR64","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(90)90130-A","volume":"70","author":"A Ehrenfeucht","year":"1990","unstructured":"Ehrenfeucht A, Rozenberg G. Theory of 2-structures, part II: representation through labeled tree families. Theoret Comput Sci. 1990;70(3):305\u201342. https:\/\/doi.org\/10.1016\/0304-3975(90)90130-A.","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"285_CR65","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/0304-3975(90)90131-Z","volume":"70","author":"A Ehrenfeucht","year":"1990","unstructured":"Ehrenfeucht A, Rozenberg G. Primitivity is hereditary for 2-structures. Theoret Comput Sci. 1990;70(3):343\u201358. https:\/\/doi.org\/10.1016\/0304-3975(90)90131-Z.","journal-title":"Theoret Comput Sci"},{"issue":"2","key":"285_CR66","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1006\/jagm.1994.1013","volume":"16","author":"A Ehrenfeucht","year":"1994","unstructured":"Ehrenfeucht A, Gabow HN, Mcconnell RM, Sullivan SJ. An O($$n^2$$) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs. J Algorithms. 1994;16(2):283\u201394. https:\/\/doi.org\/10.1006\/jagm.1994.1013.","journal-title":"J Algorithms"},{"key":"285_CR67","doi-asserted-by":"publisher","unstructured":"Cournier A, Habib M. A new linear algorithm for modular decomposition. In: Tison, S. (ed.) Trees in algebra and programming\u2014CAAP\u201994. Lecture notes in computer science, vol 787. Berlin: Springer; 1994. p. 68\u201384. https:\/\/doi.org\/10.1007\/BFb0017474","DOI":"10.1007\/BFb0017474"},{"issue":"1","key":"285_CR68","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0012-365X(97)00077-0","volume":"183","author":"A Cournier","year":"1998","unstructured":"Cournier A, Ille P. Minimal indecomposable graphs. Discret Math. 1998;183(1):61\u201380. https:\/\/doi.org\/10.1016\/S0012-365X(97)00077-0.","journal-title":"Discret Math"},{"issue":"1","key":"285_CR69","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/S0012-365X(96)00097-0","volume":"173","author":"P Ille","year":"1997","unstructured":"Ille P. Indecomposable graphs. Discret Math. 1997;173(1):71\u20138. https:\/\/doi.org\/10.1016\/S0012-365X(96)00097-0.","journal-title":"Discret Math"},{"issue":"1","key":"285_CR70","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0012-365X(93)90516-V","volume":"113","author":"JH Schmerl","year":"1993","unstructured":"Schmerl JH, Trotter WT. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures. Discret Math. 1993;113(1):191\u2013205. https:\/\/doi.org\/10.1016\/0012-365X(93)90516-V.","journal-title":"Discret Math"},{"key":"285_CR71","doi-asserted-by":"publisher","DOI":"10.26493\/2590-9770.1252.e71","author":"A Fritz","year":"2020","unstructured":"Fritz A, Hellmuth M, Stadler PF, Wieseke N. Cograph editing: merging modules is equivalent to editing $$P_4$$s. Art Discr Appl Math. 2020. https:\/\/doi.org\/10.26493\/2590-9770.1252.e71.","journal-title":"Art Discr Appl Math"},{"issue":"2","key":"285_CR72","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0304-3975(94)00272-X","volume":"154","author":"J Engelfriet","year":"1996","unstructured":"Engelfriet J, Harju T, Proskurowski A, Rozenberg G. Characterization and complexity of uniformly nonprimitive labeled 2-structures. Theoret Comput Sci. 1996;154(2):247\u201382. https:\/\/doi.org\/10.1016\/0304-3975(94)00272-X.","journal-title":"Theoret Comput Sci"},{"key":"285_CR73","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.dam.2020.12.018","volume":"291","author":"G Ducoffe","year":"2021","unstructured":"Ducoffe G, Popa A. The use of a pruned modular decomposition for maximum matching algorithms on some graph classes. Discret Appl Math. 2021;291:201\u201322. https:\/\/doi.org\/10.1016\/j.dam.2020.12.018.","journal-title":"Discret Appl Math"},{"key":"285_CR74","unstructured":"Capelle C, Cournier A, Habib M. Cograph recognition algorithm revisited and online induced $$P_4$$ search. LIRMM, Universite Montpellier, rapport de recherche. 1994;94073"},{"issue":"3","key":"285_CR75","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/0012-365X(72)90006-4","volume":"2","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz L. Normal hypergraphs and the perfect graph conjecture. Discret Math. 1972;2(3):253\u201367. https:\/\/doi.org\/10.1016\/0012-365X(72)90006-4.","journal-title":"Discret Math"},{"issue":"2","key":"285_CR76","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0095-8956(72)90045-7","volume":"13","author":"L Lov\u00e1sz","year":"1972","unstructured":"Lov\u00e1sz L. A characterization of perfect graphs. J Combin Theory Ser B. 1972;13(2):95\u20138. https:\/\/doi.org\/10.1016\/0095-8956(72)90045-7.","journal-title":"J Combin Theory Ser B"},{"issue":"8","key":"285_CR77","doi-asserted-by":"publisher","first-page":"1317","DOI":"10.1016\/j.ejc.2011.05.001","volume":"32","author":"E Drgas-Burchardt","year":"2011","unstructured":"Drgas-Burchardt E. On prime inductive classes of graphs. Eur J Comb. 2011;32(8):1317\u201328. https:\/\/doi.org\/10.1016\/j.ejc.2011.05.001.","journal-title":"Eur J Comb"},{"issue":"1","key":"285_CR78","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1016\/j.tcs.2006.10.024","volume":"370","author":"V Giakoumakis","year":"2007","unstructured":"Giakoumakis V, Olariu S. All minimal prime extensions of hereditary classes of graphs. Theoret Comput Sci. 2007;370(1):74\u201393. https:\/\/doi.org\/10.1016\/j.tcs.2006.10.024.","journal-title":"Theoret Comput Sci"},{"key":"285_CR79","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.dam.2018.10.030","volume":"257","author":"R Brignall","year":"2019","unstructured":"Brignall R, Choi H, Jeong J, Oum S-I. Deciding whether there are infinitely many prime graphs with forbidden induced subgraphs. Discr Appl Math. 2019;257:60\u20136. https:\/\/doi.org\/10.1016\/j.dam.2018.10.030.","journal-title":"Discr Appl Math"},{"issue":"2","key":"285_CR80","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/S0166-218X(02)00507-3","volume":"128","author":"I Zverovich","year":"2003","unstructured":"Zverovich I. Extension of hereditary classes with substitutions. Discret Appl Math. 2003;128(2):487\u2013509. https:\/\/doi.org\/10.1016\/S0166-218X(02)00507-3.","journal-title":"Discret Appl Math"},{"issue":"3","key":"285_CR81","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/0095-8956(85)90050-4","volume":"39","author":"RB Hayward","year":"1985","unstructured":"Hayward RB. Weakly triangulated graphs. J Combin Theory Ser B. 1985;39(3):200\u20138. https:\/\/doi.org\/10.1016\/0095-8956(85)90050-4.","journal-title":"J Combin Theory Ser B"},{"key":"285_CR82","doi-asserted-by":"publisher","unstructured":"Schidler A, Szeider S. A SAT approach to twin-width. In: 2022 proceedings of the symposium on algorithm engineering and experiments (ALENEX). SIAM, Philadelphia, PA; 2022. p. 67\u201377. https:\/\/doi.org\/10.1137\/1.9781611977042.6","DOI":"10.1137\/1.9781611977042.6"},{"issue":"2","key":"285_CR83","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0166-218X(84)90016-7","volume":"9","author":"MC Golumbic","year":"1984","unstructured":"Golumbic MC, Monma CL, Trotter WT. Tolerance graphs. Discret Appl Math. 1984;9(2):157\u201370. https:\/\/doi.org\/10.1016\/0166-218X(84)90016-7.","journal-title":"Discret Appl Math"},{"issue":"3","key":"285_CR84","doi-asserted-by":"publisher","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B Dushnik","year":"1941","unstructured":"Dushnik B, Miller EW. Partially ordered sets. Am J Math. 1941;63(3):600\u201310. https:\/\/doi.org\/10.2307\/2371374.","journal-title":"Am J Math"},{"key":"285_CR85","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph classes: a survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt A, Le VB, Spinrad JP. Graph classes: a survey. Philadelphia: SIAM; 1999. https:\/\/doi.org\/10.1137\/1.9780898719796."},{"key":"285_CR86","unstructured":"Ahn J, Jacob H, K\u00f6hler N, Paul C, Reinald A, Wiederrecht S. Twin-width one; 2025. https:\/\/arxiv.org\/abs\/2501.00991"},{"key":"285_CR87","doi-asserted-by":"publisher","first-page":"2015","DOI":"10.1007\/s00285-019-01332-9","volume":"78","author":"M Gei\u00df","year":"2019","unstructured":"Gei\u00df M, Ch\u00e1vez E, Gonz\u00e1lez Laffitte M, L\u00f3pez S\u00e1nchez A, Stadler BMR, Valdivia DI, Hellmuth M, Hern\u00e1ndez Rosales M, Stadler PF. Best match graphs. J Math Biol. 2019;78:2015\u201357. https:\/\/doi.org\/10.1007\/s00285-019-01332-9.","journal-title":"J Math Biol"},{"key":"285_CR88","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/s00285-021-01601-6","volume":"82","author":"D Schaller","year":"2021","unstructured":"Schaller D, Gei\u00df M, Ch\u00e1vez E, Gonz\u00e1lez Laffitte M, L\u00f3pez S\u00e1nchez A, Stadler BMR, Valdivia DI, Hellmuth M, Hern\u00e1ndez Rosales M, Stadler PF. Corrigendum to \u201cBest Match Graphs\u2019\u2019. J Math Biol. 2021;82:47. https:\/\/doi.org\/10.1007\/s00285-021-01601-6.","journal-title":"J Math Biol"},{"issue":"5","key":"285_CR89","doi-asserted-by":"publisher","first-page":"1459","DOI":"10.1007\/s00285-020-01469-y","volume":"80","author":"M Gei\u00df","year":"2020","unstructured":"Gei\u00df M, Laffitte MEG, S\u00e1nchez AL, Valdivia DI, Hellmuth M, Rosales MH, Stadler PF. Best match graphs and reconciliation of gene trees with species trees. J Math Biol. 2020;80(5):1459\u201395. https:\/\/doi.org\/10.1007\/s00285-020-01469-y.","journal-title":"J Math Biol"},{"key":"285_CR90","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00285-021-01564-8","volume":"82","author":"D Schaller","year":"2021","unstructured":"Schaller D, Gei\u00df M, Stadler PF, Hellmuth M. Complete characterization of incorrect orthology assignments in best match graphs. J Math Biol. 2021;82:20. https:\/\/doi.org\/10.1007\/s00285-021-01564-8.","journal-title":"J Math Biol"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00285-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00285-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00285-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T08:40:27Z","timestamp":1759394427000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-025-00285-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,2]]},"references-count":90,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["285"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00285-7","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,2]]},"assertion":[{"value":"10 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"19"}}