{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:28:36Z","timestamp":1740144516348,"version":"3.37.3"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T00:00:00Z","timestamp":1652918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T00:00:00Z","timestamp":1652918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2019\/33\/B\/ST6\/00737"],"award-info":[{"award-number":["2019\/33\/B\/ST6\/00737"]}],"id":[{"id":"10.13039\/501100004281","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><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Phylogenetic networks are mathematical models of evolutionary processes involving reticulate events such as hybridization, recombination, or horizontal gene transfer. One of the crucial notions in phylogenetic network modelling is displayed tree, which is obtained from a network by removing a set of reticulation edges. Displayed trees may represent an evolutionary history of a gene family if the evolution is shaped by reticulation events.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>We address the problem of inferring an optimal tree displayed by a network, given a gene tree <jats:italic>G<\/jats:italic> and a tree-child network <jats:italic>N<\/jats:italic>, under the deep coalescence and duplication costs. We propose an <jats:italic>O<\/jats:italic>(<jats:italic>mn<\/jats:italic>)-time dynamic programming algorithm (DP) to compute a lower bound of the optimal displayed tree cost, where <jats:italic>m<\/jats:italic> and <jats:italic>n<\/jats:italic> are the sizes of <jats:italic>G<\/jats:italic> and <jats:italic>N<\/jats:italic>, respectively. In addition, our algorithm can verify whether the solution is exact. Moreover, it provides a set of reticulation edges corresponding to the obtained cost. If the cost is exact, the set induces an optimal displayed tree. Otherwise, the set contains pairs of conflicting edges, i.e., edges sharing a reticulation node. Next, we show a conflict resolution algorithm that requires <jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{r+1}-1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:msup>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mrow>\n                          <mml:mi>r<\/mml:mi>\n                          <mml:mo>+<\/mml:mo>\n                          <mml:mn>1<\/mml:mn>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mo>-<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula> invocations of DP in the worst case, where <jats:italic>r<\/jats:italic> is the number of reticulations. We propose a similar <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(2^kmn)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:msup>\n                      <mml:mi>m<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-time algorithm for level-<jats:italic>k<\/jats:italic> tree-child networks and a branch and bound solution to compute lower and upper bounds of optimal costs. We also extend the algorithms to a broader class of phylogenetic networks. Based on simulated data, the average runtime is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Theta (2^{{0.543}k}mn)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mi>\u0398<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mrow>\n                          <mml:mrow>\n                            <mml:mn>0.543<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:mi>k<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mi>m<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula> under the deep-coalescence cost and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Theta (2^{{0.355}k}mn)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                    <mml:mrow>\n                      <mml:mi>\u0398<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mrow>\n                          <mml:mrow>\n                            <mml:mn>0.355<\/mml:mn>\n                          <\/mml:mrow>\n                          <mml:mi>k<\/mml:mi>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                      <mml:mi>m<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:math><\/jats:alternatives><\/jats:inline-formula> under the duplication cost.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusions<\/jats:title>\n                <jats:p>Despite exponential complexity in the worst case, our algorithms perform significantly well on empirical and simulated datasets, due to the strategy of resolving internal dissimilarities between gene trees and networks. Therefore, the algorithms are efficient alternatives to enumeration strategies commonly proposed in the literature and enable analyses of complex networks with dozens of reticulations.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-022-00218-8","type":"journal-article","created":{"date-parts":[[2022,5,19]],"date-time":"2022-05-19T16:04:57Z","timestamp":1652976297000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Embedding gene trees into phylogenetic networks by conflict resolution algorithms"],"prefix":"10.1186","volume":"17","author":[{"given":"Marcin","family":"Wawerka","sequence":"first","affiliation":[]},{"given":"Dawid","family":"D\u0105bkowski","sequence":"additional","affiliation":[]},{"given":"Natalia","family":"Rutecka","sequence":"additional","affiliation":[]},{"given":"Agnieszka","family":"Mykowiecka","sequence":"additional","affiliation":[]},{"given":"Pawe\u0142","family":"G\u00f3recki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,19]]},"reference":[{"issue":"8","key":"218_CR1","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1016\/j.tig.2013.05.007","volume":"29","author":"E Bapteste","year":"2013","unstructured":"Bapteste E, van Iersel L, Janke A, Kelchner S, Kelk S, McInerney JO, et al. Networks: expanding evolutionary thinking. Trends Genet. 2013;29(8):439\u201341.","journal-title":"Trends Genet"},{"key":"218_CR2","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. New York: Cambridge University Press; 2010."},{"issue":"1","key":"218_CR3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1104\/pp.16.01340","volume":"173","author":"BE Goulet","year":"2016","unstructured":"Goulet BE, Roda F, Hopkins R. Hybridization in plants: old ideas. New Techniq Plant Physiol. 2016;173(1):65\u201378.","journal-title":"New Techniq Plant Physiol"},{"issue":"7","key":"218_CR4","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1038\/nrmicro.2016.46","volume":"14","author":"SM McDonald","year":"2016","unstructured":"McDonald SM, Nelson MI, Turner PE, Patton JT. Reassortment in segmented RNA viruses: mechanisms and outcomes. Nat Rev Microbiol. 2016;14(7):448\u201360.","journal-title":"Nat Rev Microbiol"},{"issue":"1683","key":"218_CR5","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1098\/rspb.2009.1679","volume":"277","author":"L Boto","year":"2009","unstructured":"Boto L. Horizontal gene transfer in evolution: facts and challenges. Proc R Soc B Biol Sci. 2009;277(1683):819\u201327.","journal-title":"Proc R Soc B Biol Sci"},{"key":"218_CR6","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9432.001.0001","volume-title":"ReCombinatorics: the Algorithmics of ancestral recombination graphs and explicit phylogenetic networks","author":"D Gusfield","year":"2014","unstructured":"Gusfield D. ReCombinatorics: the Algorithmics of ancestral recombination graphs and explicit phylogenetic networks. Boston: MIT Press; 2014."},{"key":"218_CR7","doi-asserted-by":"crossref","unstructured":"LeMay M, Libeskind-Hadas R, Wu YC. A polynomial-time algorithm for minimizing the deep coalescence cost for level-1 species networks. bioRxiv. 2020.","DOI":"10.1101\/2020.11.04.368845"},{"key":"218_CR8","doi-asserted-by":"crossref","unstructured":"Markin A, Anderson TK, Vadali VS, Eulenstein O. Robinson-Foulds reticulation networks. In: Proceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics; 2019; p. 77\u201386.","DOI":"10.1145\/3307339.3342151"},{"key":"218_CR9","doi-asserted-by":"crossref","unstructured":"To TH, Scornavacca C. Efficient algorithms for reconciling gene trees and species networks via duplication and loss events. BMC Genomics. 2015;16(S10).","DOI":"10.1186\/1471-2164-16-S10-S6"},{"issue":"3","key":"218_CR10","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1093\/sysbio\/syx094","volume":"67","author":"LV Iersel","year":"2017","unstructured":"Iersel LV, Jones M, Scornavacca C. Improved maximum parsimony models for phylogenetic networks. Syst Biol. 2017;67(3):518\u201342.","journal-title":"Syst Biol"},{"key":"218_CR11","doi-asserted-by":"crossref","unstructured":"Zhu J, Yu Y, Nakhleh L. In the light of deep coalescence: revisiting trees within networks. BMC Bioinformat. 2016;17(S14).","DOI":"10.1186\/s12859-016-1269-1"},{"issue":"3","key":"218_CR12","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1093\/sysbio\/46.3.523","volume":"46","author":"WP Maddison","year":"1997","unstructured":"Maddison WP. Gene trees in species trees. Syst Biol. 1997;46(3):523\u201336.","journal-title":"Syst Biol"},{"issue":"12","key":"218_CR13","doi-asserted-by":"publisher","first-page":"i44","DOI":"10.1093\/bioinformatics\/btv234","volume":"31","author":"S Mirarab","year":"2015","unstructured":"Mirarab S, Warnow T. ASTRAL-II: coalescent-based species tree estimation with many hundreds of taxa and thousands of genes. Bioinformatics. 2015;31(12):i44\u201352.","journal-title":"Bioinformatics"},{"issue":"9","key":"218_CR14","doi-asserted-by":"publisher","first-page":"e1000501","DOI":"10.1371\/journal.pcbi.1000501","volume":"5","author":"C Than","year":"2009","unstructured":"Than C, Nakhleh L. Species tree inference by minimizing deep coalescences. PLoS Comput Biol. 2009;5(9):e1000501.","journal-title":"PLoS Comput Biol."},{"issue":"6","key":"218_CR15","doi-asserted-by":"publisher","first-page":"1685","DOI":"10.1109\/TCBB.2011.83","volume":"8","author":"L Zhang","year":"2011","unstructured":"Zhang L. From gene trees to species trees II: species tree inference by minimizing deep coalescence events. IEEE\/ACM Trans Comput Biol Bioinf. 2011;8(6):1685\u201391.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"2","key":"218_CR16","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1109\/TCBB.2013.22","volume":"10","author":"P G\u00f3recki","year":"2013","unstructured":"G\u00f3recki P, Eulenstein O, Tiuryn J. Unrooted tree reconciliation: a unified approach. IEEE\/ACM Trans Comput Biol Bioinf. 2013;10(2):522\u201336.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"1","key":"218_CR17","first-page":"3","volume":"10","author":"B Donati","year":"2015","unstructured":"Donati B, Baudet C, Sinaimeri B, Crescenzi P, Sagot MF. EUCALYPT: efficient tree reconciliation enumerator. Alg Mol Biol. 2015;10(1):3.","journal-title":"Alg Mol Biol."},{"issue":"3","key":"218_CR18","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1101\/gr.161968.113","volume":"24","author":"YC Wu","year":"2014","unstructured":"Wu YC, Rasmussen MD, Bansal MS, Kellis M. Most parsimonious reconciliation in the presence of gene duplication, loss, and deep coalescence using labeled coalescent trees. Genome Res. 2014;24(3):475\u201386.","journal-title":"Genome Res"},{"issue":"1","key":"218_CR19","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1109\/TCBB.2013.144","volume":"11","author":"P Gorecki","year":"2014","unstructured":"Gorecki P, Eulenstein O. Maximizing deep coalescence cost. IEEE\/ACM Trans Comput Biol Bioinf. 2014;11(1):231\u201342.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"218_CR20","doi-asserted-by":"crossref","unstructured":"Chaudhary R, Burleigh JG, Eulenstein O. Efficient error correction algorithms for gene tree reconciliation based on duplication, duplication and loss, and deep coalescence. In: BMC Bioinformatics. vol.\u00a013. BioMed Central; 2012. p. 1\u201310.","DOI":"10.1186\/1471-2105-13-S10-S11"},{"key":"218_CR21","doi-asserted-by":"crossref","unstructured":"Goodman M, et\u00a0al. Fitting the gene lineage into its species lineage, a parsimony strategy illustrated by cladograms constructed from globin sequences. 1979;28(2):132\u2013163.","DOI":"10.1093\/sysbio\/28.2.132"},{"issue":"9","key":"218_CR22","doi-asserted-by":"publisher","first-page":"819","DOI":"10.1093\/bioinformatics\/14.9.819","volume":"14","author":"RD Page","year":"1998","unstructured":"Page RD. GeneTree: comparing gene and species phylogenies using reconciled trees. Bioinformatics. 1998;14(9):819\u201320.","journal-title":"Bioinformatics"},{"issue":"1\u20133","key":"218_CR23","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1016\/j.tcs.2006.05.019","volume":"359","author":"P G\u00f3recki","year":"2006","unstructured":"G\u00f3recki P, Tiuryn J. DLS-trees: a model of evolutionary scenarios. Theoret Comput Sci. 2006;359(1\u20133):378\u201399.","journal-title":"Theoret Comput Sci"},{"issue":"1\u20132","key":"218_CR24","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2005.05.016","volume":"347","author":"P Bonizzoni","year":"2005","unstructured":"Bonizzoni P, Della Vedova G, Dondi R. Reconciling a gene tree to a species tree under the duplication cost model. Theoret Comput Sci. 2005;347(1\u20132):36\u201353.","journal-title":"Theoret Comput Sci"},{"issue":"11","key":"218_CR25","doi-asserted-by":"publisher","first-page":"1543","DOI":"10.1089\/cmb.2011.0174","volume":"18","author":"Y Yu","year":"2011","unstructured":"Yu Y, Warnow T, Nakhleh L. Algorithms for MDC-based multi-locus phylogeny inference: beyond rooted binary gene trees on single alleles. J Comput Biol. 2011;18(11):1543\u201359.","journal-title":"J Comput Biol"},{"key":"218_CR26","doi-asserted-by":"crossref","unstructured":"Paszek J, G\u00f3recki P. Genomic duplication problems for unrooted gene trees. BMC Genomics. 2016;17(S1).","DOI":"10.1186\/s12864-015-2308-4"},{"key":"218_CR27","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.jtbi.2017.01.024","volume":"418","author":"C Scornavacca","year":"2017","unstructured":"Scornavacca C, Mayol JCP, Cardona G. Fast algorithm for the reconciliation of gene trees and LGT networks. J Theor Biol. 2017;418:129\u201337.","journal-title":"J Theor Biol"},{"issue":"4","key":"218_CR28","doi-asserted-by":"publisher","first-page":"e1002660","DOI":"10.1371\/journal.pgen.1002660","volume":"8","author":"Y Yu","year":"2012","unstructured":"Yu Y, Degnan JH, Nakhleh L. The probability of a gene tree topology within a phylogenetic network with applications to hybridization detection. PLoS Genet. 2012;8(4):e1002660.","journal-title":"PLoS Genet"},{"key":"218_CR29","doi-asserted-by":"crossref","unstructured":"Than C, Ruths D, Nakhleh L. PhyloNet: a software package for analyzing and reconstructing reticulate evolutionary relationships. BMC Bioinformat. 2008;9(1).","DOI":"10.1186\/1471-2105-9-322"},{"issue":"5","key":"218_CR30","doi-asserted-by":"publisher","first-page":"738","DOI":"10.1093\/sysbio\/syt037","volume":"62","author":"Y Yu","year":"2013","unstructured":"Yu Y, Barnett RM, Nakhleh L. Parsimonious inference of hybridization in the presence of incomplete lineage sorting. Syst Biol. 2013;62(5):738\u201351.","journal-title":"Syst Biol"},{"issue":"5","key":"218_CR31","doi-asserted-by":"publisher","first-page":"1885","DOI":"10.1007\/s00285-019-01414-8","volume":"79","author":"M Hellmuth","year":"2019","unstructured":"Hellmuth M, Huber KT, Moulton V. Reconciling event-labeled gene trees with MUL-trees and species networks. J Math Biol. 2019;79(5):1885\u2013925. https:\/\/doi.org\/10.1007\/s00285-019-01414-8.","journal-title":"J Math Biol."},{"issue":"4","key":"218_CR32","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1109\/TCBB.2007.70270","volume":"6","author":"G Cardona","year":"2008","unstructured":"Cardona G, Rossell\u00f3 F, Valiente G. Comparison of tree-child phylogenetic networks. IEEE\/ACM Trans Comput Biol Bioinf. 2008;6(4):552\u201369.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"4","key":"218_CR33","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1109\/TCBB.2007.70270","volume":"6","author":"G Cardona","year":"2009","unstructured":"Cardona G, Rossello F, Valiente G. Comparison of tree-child phylogenetic networks. IEEE\/ACM Trans Comput Biol Bioinf. 2009;6(4):552\u201369.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"218_CR34","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1016\/j.jcss.2020.06.001","volume":"114","author":"G Cardona","year":"2020","unstructured":"Cardona G, Zhang L. Counting and enumerating tree-child networks and their subclasses. J Comput Syst Sci. 2020;114:84\u2013104.","journal-title":"J Comput Syst Sci"},{"issue":"10","key":"218_CR35","doi-asserted-by":"publisher","first-page":"3823","DOI":"10.1007\/s11538-019-00641-w","volume":"81","author":"Y Murakami","year":"2019","unstructured":"Murakami Y, van Iersel L, Janssen R, Jones M, Moulton V. Reconstructing tree-child networks from reticulate-edge-deleted subnetworks. Bull Math Biol. 2019;81(10):3823\u201363.","journal-title":"Bull Math Biol"},{"key":"218_CR36","doi-asserted-by":"crossref","unstructured":"Steel M. Phylogeny. Society for Industrial and Applied Mathematics; 2016. Available from: https:\/\/doi.org\/10.1137\/1.9781611974485.","DOI":"10.1137\/1.9781611974485"},{"issue":"5","key":"218_CR37","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00285-005-0365-z","volume":"52","author":"KT Huber","year":"2006","unstructured":"Huber KT, Moulton V. Phylogenetic networks from multi-labelled trees. J Math Biol. 2006;52(5):613\u201332.","journal-title":"J Math Biol"},{"issue":"6\u20137","key":"218_CR38","doi-asserted-by":"publisher","first-page":"1761","DOI":"10.1007\/s00285-016-0993-5","volume":"73","author":"KT Huber","year":"2016","unstructured":"Huber KT, Moulton V, Steel M, Wu T. Folding and unfolding phylogenetic trees and networks. J Math Biol. 2016;73(6\u20137):1761\u201380.","journal-title":"J Math Biol"},{"issue":"1","key":"218_CR39","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2004.12.012","volume":"335","author":"C Choy","year":"2005","unstructured":"Choy C, Jansson J, Sadakane K, Sung WK. Computing the maximum agreement of phylogenetic networks. Theoret Comput Sci. 2005;335(1):93\u2013107.","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"218_CR40","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1137\/140959948","volume":"29","author":"M Fischer","year":"2015","unstructured":"Fischer M, Van Iersel L, Kelk S, Scornavacca C. On computing the maximum parsimony score of a phylogenetic network. SIAM J Discret Math. 2015;29(1):559\u201385.","journal-title":"SIAM J Discret Math"},{"key":"218_CR41","doi-asserted-by":"publisher","first-page":"101959","DOI":"10.1016\/j.aam.2019.101959","volume":"113","author":"KT Huber","year":"2020","unstructured":"Huber KT, Scholz GE. Phylogenetic networks that are their own fold-ups. Adv Appl Math. 2020;113:101959. https:\/\/doi.org\/10.1016\/j.aam.2019.101959.","journal-title":"Adv Appl Math."},{"key":"218_CR42","doi-asserted-by":"crossref","unstructured":"Janssen R, Murakami Y. Linear time algorithm for tree-child network containment. In: International Conference on Algorithms for Computational Biology. Springer; 2020. p. 93\u2013107.","DOI":"10.1007\/978-3-030-42266-0_8"},{"issue":"Supplement1","key":"218_CR43","doi-asserted-by":"publisher","first-page":"i57","DOI":"10.1093\/bioinformatics\/btaa444","volume":"36","author":"EK Molloy","year":"2020","unstructured":"Molloy EK, Warnow T. FastMulRFS: fast and accurate species tree estimation under generic gene duplication and loss models. Bioinformatics. 2020;36(Supplement1):i57\u201365.","journal-title":"Bioinformatics."},{"issue":"4","key":"218_CR44","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1101\/gr.123901.111","volume":"22","author":"MD Rasmussen","year":"2012","unstructured":"Rasmussen MD, Kellis M. Unified modeling of gene duplication, loss, and coalescence using a locus tree. Genome Res. 2012;22(4):755\u201365.","journal-title":"Genome Res"},{"issue":"4","key":"218_CR45","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1093\/sysbio\/syq026","volume":"52","author":"K Hartmann","year":"2010","unstructured":"Hartmann K, Wong D, Stadler T. Sampling trees from evolutionary models. Syst Biol. 2010;52(4):465\u201376.","journal-title":"Syst Biol"},{"issue":"3","key":"218_CR46","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pgen.1005896","volume":"12","author":"C Sol\u00eds-Lemus","year":"2016","unstructured":"Sol\u00eds-Lemus C, An\u00e9 C. Inferring phylogenetic networks with maximum pseudolikelihood under incomplete lineage sorting. PLoS Genet. 2016;12(3):1\u201321.","journal-title":"PLoS Genet"},{"issue":"5","key":"218_CR47","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1093\/sysbio\/syv037","volume":"64","author":"AR Francis","year":"2015","unstructured":"Francis AR, Steel M. Which phylogenetic networks are merely trees with additional arcs? Syst Biol. 2015;64(5):768\u201377.","journal-title":"Syst Biol"},{"issue":"2","key":"218_CR48","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1093\/sysbio\/syv082","volume":"65","author":"D Mallo","year":"2015","unstructured":"Mallo D, De Oliveira Martins L, Posada D. SimPhy: phylogenomic simulation of gene, locus, and species trees. Syst Biol. 2015;65(2):334\u201344.","journal-title":"Syst Biol"},{"issue":"8","key":"218_CR49","doi-asserted-by":"publisher","first-page":"1879","DOI":"10.1093\/molbev\/msp098","volume":"26","author":"W Fletcher","year":"2009","unstructured":"Fletcher W, Yang Z. INDELible: a flexible simulator of biological sequence evolution. Mol Biol Evol. 2009;26(8):1879\u201388.","journal-title":"Mol Biol Evol"},{"issue":"3","key":"218_CR50","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1093\/sysbio\/syq010","volume":"59","author":"S Guindon","year":"2010","unstructured":"Guindon S, Dufayard JF, Vincent L, Anisimova M, Hordijk W, Gascuel O. New algorithms and methods to estimate maximum-likelihood phylogenies: assessing the performance of PhyML 3.0. Syst Biol. 2010;59(3):307\u201321.","journal-title":"Syst Biol"},{"issue":"4","key":"218_CR51","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1093\/bioinformatics\/btl634","volume":"23","author":"P G\u00f3recki","year":"2007","unstructured":"G\u00f3recki P, Tiuryn J. URec: a system for unrooted reconciliation. Bioinformatics. 2007;23(4):511\u20132.","journal-title":"Bioinformatics"},{"issue":"10","key":"218_CR52","doi-asserted-by":"publisher","first-page":"e66","DOI":"10.1093\/nar\/gkr087","volume":"39","author":"M Marcet-Houben","year":"2011","unstructured":"Marcet-Houben M, Gabald\u00f3n T. TreeKO: a duplication-aware algorithm for the comparison of phylogenetic trees. Nucleic Acids Res. 2011;39(10):e66\u2013e66.","journal-title":"Nucleic Acids Res"},{"issue":"1","key":"218_CR53","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12862-020-01734-0","volume":"21","author":"V Makarenkov","year":"2021","unstructured":"Makarenkov V, Mazoure B, Rabusseau G, Legendre P. Horizontal gene transfer and recombination analysis of SARS-CoV-2 genes helps discover its close relatives and shed light on its origin. BMC Ecol Evol. 2021;21(1):1\u201318.","journal-title":"BMC Ecol Evol."},{"issue":"suppl1","key":"218_CR54","first-page":"D32","volume":"39","author":"DA Benson","year":"2010","unstructured":"Benson DA, Karsch-Mizrachi I, Lipman DJ, Ostell J, Sayers EW. GenBank. Nucleic Acids Res. 2010;39(suppl1):D32\u20137.","journal-title":"Nucleic Acids Res"},{"issue":"13","key":"218_CR55","doi-asserted-by":"publisher","first-page":"30494","DOI":"10.2807\/1560-7917.ES.2017.22.13.30494","volume":"22","author":"Y Shu","year":"2017","unstructured":"Shu Y, McCauley J. GISAID: global initiative on sharing all influenza data-from vision to reality. Eurosurveillance. 2017;22(13):30494.","journal-title":"Eurosurveillance."},{"issue":"1","key":"218_CR56","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-5-113","volume":"5","author":"RC Edgar","year":"2004","unstructured":"Edgar RC. MUSCLE: a multiple sequence alignment method with reduced time and space complexity. BMC Bioinformat. 2004;5(1):1\u201319.","journal-title":"BMC Bioinformat"},{"issue":"4","key":"218_CR57","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1093\/oxfordjournals.molbev.a026334","volume":"17","author":"J Castresana","year":"2000","unstructured":"Castresana J. Selection of conserved blocks from multiple alignments for their use in phylogenetic analysis. Mol Biol Evol. 2000;17(4):540\u201352.","journal-title":"Mol Biol Evol"},{"issue":"21","key":"218_CR58","doi-asserted-by":"publisher","first-page":"2688","DOI":"10.1093\/bioinformatics\/btl446","volume":"22","author":"A Stamatakis","year":"2006","unstructured":"Stamatakis A. RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics. 2006;22(21):2688\u201390.","journal-title":"Bioinformatics"},{"key":"218_CR59","unstructured":"Waskom M, et\u00a0al. mwaskom\/seaborn: v0.8.1 (September 2017). Zenodo; 2017. Available from: https:\/\/doi.org\/10.5281\/zenodo.883859."}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00218-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-022-00218-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00218-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,13]],"date-time":"2022-11-13T20:25:27Z","timestamp":1668371127000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-022-00218-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,19]]},"references-count":59,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["218"],"URL":"https:\/\/doi.org\/10.1186\/s13015-022-00218-8","relation":{},"ISSN":["1748-7188"],"issn-type":[{"type":"electronic","value":"1748-7188"}],"subject":[],"published":{"date-parts":[[2022,5,19]]},"assertion":[{"value":"15 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"11"}}