{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,10]],"date-time":"2025-09-10T22:28:03Z","timestamp":1757543283310,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031369100"},{"type":"electronic","value":"9783031369117"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,13]],"date-time":"2023-07-13T00:00:00Z","timestamp":1689206400000},"content-version":"vor","delay-in-days":193,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a proof of principle for a new kind of stepwise algorithm for unrooted binary gene-order phylogenies. This method incorporates a simple look-ahead inspired by Dollo\u2019s law, while simultaneously reconstructing each ancestor (sometimes referred to as hypothetical taxonomic units \u201cHTU\u201d). We first present a generic version of the algorithm illustrating a necessary consequence of Dollo characters. In a concrete application we use generalized oriented gene adjacencies and maximum weight matching (MWM) to reconstruct fragments of monoploid ancestral genomes as HTUs. This is applied to three flowering plant orders while estimating phylogenies for these orders in the process. We discuss how to improve on the extensive computing times that would be necessary for this method to handle larger trees.<\/jats:p>","DOI":"10.1007\/978-3-031-36911-7_7","type":"book-chapter","created":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T15:02:19Z","timestamp":1689174139000},"page":"100-111","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Gene Order Phylogeny via\u00a0Ancestral Genome Reconstruction Under Dollo"],"prefix":"10.1007","author":[{"given":"Qiaoji","family":"Xu","sequence":"first","affiliation":[]},{"given":"David","family":"Sankoff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,7,13]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-030-79290-9_9","volume-title":"Computational Advances in Bio and Medical Sciences","author":"Q Xu","year":"2021","unstructured":"Xu, Q., Jin, L., Zheng, C., Leebens Mack, J.H., Sankoff, D.: RACCROCHE: ancestral flowering plant chromosomes and gene orders based on generalized adjacencies and chromosomal gene co-occurrences. In: Jha, S.K., M\u0103ndoiu, I., Rajasekaran, S., Skums, P., Zelikovsky, A. (eds.) ICCABS 2020. LNCS, vol. 12686, pp. 97\u2013115. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-79290-9_9"},{"issue":"6","key":"7_CR2","doi-asserted-by":"publisher","first-page":"160","DOI":"10.3390\/a14060160","volume":"14","author":"Q Xu","year":"2021","unstructured":"Xu, Q., Jin, L., Leebens-Mack, J.H., Sankoff, D.: Validation of automated chromosome recovery in the reconstruction of ancestral gene order. Algorithms 14(6), 160 (2021)","journal-title":"Algorithms"},{"key":"7_CR3","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1038\/s41467-022-28312-w","volume":"13","author":"AS Chanderbali","year":"2022","unstructured":"Chanderbali, A.S., Jin, L., Xu, Q., et al.: Buxus and Tetracentron genomes help resolve eudicot genome history. Nat. Communun. 13, 643 (2022). https:\/\/doi.org\/10.1038\/s41467-022-28312-w","journal-title":"Nat. Communun."},{"issue":"11","key":"7_CR4","doi-asserted-by":"publisher","first-page":"1156","DOI":"10.1089\/cmb.2021.0340","volume":"28","author":"Q Xu","year":"2021","unstructured":"Xu, Q., et al.: Ancestral flowering plant chromosomes and gene orders based on generalized adjacencies and chromosomal gene co-occurrences. J. Comput. Biol. 28(11), 1156\u201379 (2021)","journal-title":"J. Comput. Biol."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Xu, Q., Jin, L., Zheng, C., Zhang, X., Leebens-Mack, J., Sankoff, D.: From comparative gene content and gene order to ancestral contigs, chromosomes and karyotypes. Sci. Rep. 13, 6095 (2023)","DOI":"10.1038\/s41598-023-33029-x"},{"key":"7_CR6","unstructured":"van Rantwijk, J.: Maximum Weighted Matching (2008). http:\/\/jorisvr.nl\/article\/maximum-matching"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/6462.6502","volume":"18","author":"Z Galil","year":"1986","unstructured":"Galil, Z.: Efficient algorithms for finding maximum matching in graphs. ACM Comput. Surv. 18, 23\u201338 (1986)","journal-title":"ACM Comput. Surv."},{"key":"7_CR8","doi-asserted-by":"publisher","first-page":"449","DOI":"10.4153\/CJM-1965-045-4","volume":"17","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 449\u201367 (1965)","journal-title":"Can. J. Math."},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1111\/j.1365-313X.2007.03326.x","volume":"53","author":"E Lyons","year":"2008","unstructured":"Lyons, E., Freeling, M.: How to usefully compare homologous plant genes and chromosomes as DNA sequences. Plant J. 53, 661\u2013673 (2008)","journal-title":"Plant J."},{"key":"7_CR10","doi-asserted-by":"publisher","first-page":"1772","DOI":"10.1104\/pp.108.124867","volume":"148","author":"E Lyons","year":"2008","unstructured":"Lyons, E., et al.: Finding and comparing syntenic regions among Arabidopsis and the outgroups papaya, poplar and grape: CoGe with rosids. Plant Physiol. 148, 1772\u20131781 (2008)","journal-title":"Plant Physiol."},{"key":"7_CR11","unstructured":"Published Plant Genomes. Usadel lab, Forschungszentrum J\u00fclich, Heinrich Heine University., D\u00fcsseldorf (2022). https:\/\/www.plabipd.de\/"},{"key":"7_CR12","unstructured":"Stevens, P.F.: Angiosperm Phylogeny Website. Version 14 (2017). http:\/\/www.mobot.org\/MOBOT\/research\/APweb\/"},{"key":"7_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1111\/boj.12385","volume":"181","author":"MW Chase","year":"2016","unstructured":"Chase, M.W., et al.: An update of the Angiosperm Phylogeny Group classification for the orders and families of flowering plants: APG IV. Bot. J. Linn. Soc. 181, 1\u201320 (2016)","journal-title":"Bot. J. Linn. Soc."},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"6575","DOI":"10.1073\/pnas.89.14.6575","volume":"15","author":"D Sankoff","year":"1992","unstructured":"Sankoff, D., Leduc, G., Antoine, N., Paquin, B., Lang, B.F., Cedergren, R.: Gene order comparisons for phylogenetic inference: evolution of the mitochondrial genome. Proc. Natl. Acad. Sci. 15, 6575\u20139 (1992)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1016\/S0076-6879(05)95035-0","volume":"395","author":"BM Moret","year":"2005","unstructured":"Moret, B.M., Warnow, T.: Advances in phylogeny reconstruction from gene order and content data. Methods Enzymol. 395, 673\u2013700 (2005)","journal-title":"Methods Enzymol."},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s12859-014-0354-6","volume":"15","author":"F Hu","year":"2014","unstructured":"Hu, F., Lin, Y., Tang, J.: MLGO: phylogeny reconstruction and ancestral inference from gene-order data. BMC Bioinf. 15, 1\u20136 (2014)","journal-title":"BMC Bioinf."},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Perrin, A., Varr\u00e9, J.S., Blanquart, S., Ouangraoua, A.: ProCARs: progressive reconstruction of ancestral gene orders BMC genomics 16 S5:S6 (2015)","DOI":"10.1186\/1471-2164-16-S5-S6"}],"container-title":["Lecture Notes in Computer Science","Comparative Genomics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-36911-7_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T15:03:48Z","timestamp":1689174228000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-36911-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031369100","9783031369117"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-36911-7_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"13 July 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"RECOMB-CG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"RECOMB International Workshop on Comparative Genomics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Istanbul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"T\u00fcrkiye","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 April 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 April 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"rcg2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb-cg.org","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}