1 line
37 KiB
Plaintext
1 line
37 KiB
Plaintext
{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,13]],"date-time":"2024-01-13T16:03:59Z","timestamp":1705161839081},"reference-count":74,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T00:00:00Z","timestamp":1691798400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T00:00:00Z","timestamp":1691798400000},"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"]},{"DOI":"10.13039\/501100009244","name":"Stockholm University","doi-asserted-by":"crossref"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Biosci."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Rooted acyclic graphs appear naturally when the phylogenetic relationship of a set <jats:italic>X<\/jats:italic> of taxa involves not only speciations but also recombination, horizontal transfer, or hybridization that cannot be captured by trees. A variety of classes of such networks have been discussed in the literature, including phylogenetic, level-1, tree-child, tree-based, galled tree, regular, or normal networks as models of different types of evolutionary processes. Clusters arise in models of phylogeny as the sets <jats:inline-formula><jats:alternatives><jats:tex-math>$${{\\,\\mathrm{\\texttt{C}}\\,}}(v)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:mrow>\n <mml:mrow>\n <mml:mspace \/>\n <mml:mi>C<\/mml:mi>\n <mml:mspace \/>\n <\/mml:mrow>\n <mml:mo>(<\/mml:mo>\n <mml:mi>v<\/mml:mi>\n <mml:mo>)<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of descendant taxa of a vertex <jats:italic>v<\/jats:italic>. The clustering system <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {C}_N$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:msub>\n <mml:mi>C<\/mml:mi>\n <mml:mi>N<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> comprising the clusters of a network <jats:italic>N<\/jats:italic> conveys key information on <jats:italic>N<\/jats:italic> itself. In the special case of rooted phylogenetic trees, <jats:italic>T<\/jats:italic> is uniquely determined by its clustering system <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {C}_T$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:msub>\n <mml:mi>C<\/mml:mi>\n <mml:mi>T<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Although this is no longer true for networks in general, it is of interest to relate properties of <jats:italic>N<\/jats:italic> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {C}_N$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:msub>\n <mml:mi>C<\/mml:mi>\n <mml:mi>N<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Here, we systematically investigate the relationships of several well-studied classes of networks and their clustering systems. The main results are correspondences of classes of networks and clustering systems of the following form: If <jats:italic>N<\/jats:italic> is a network of type <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {X}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:mi>X<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, then <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {C}_N$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:msub>\n <mml:mi>C<\/mml:mi>\n <mml:mi>N<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> satisfies <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {Y}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:mi>Y<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and conversely if <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {C}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:mi>C<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a clustering system satisfying <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {Y},$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:mrow>\n <mml:mi>Y<\/mml:mi>\n <mml:mo>,<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> then there is network <jats:italic>N<\/jats:italic> of type <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathbb {X}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:mi>X<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathscr {C}\\subseteq \\mathscr {C}_N$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n <mml:mrow>\n <mml:mi>C<\/mml:mi>\n <mml:mo>\u2286<\/mml:mo>\n <mml:msub>\n <mml:mi>C<\/mml:mi>\n <mml:mi>N<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.This, in turn, allows us to investigate the mutual dependencies between the distinct types of networks in much detail.<\/jats:p>","DOI":"10.1007\/s12064-023-00398-w","type":"journal-article","created":{"date-parts":[[2023,8,12]],"date-time":"2023-08-12T18:02:01Z","timestamp":1691863321000},"page":"301-358","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Clustering systems of phylogenetic networks"],"prefix":"10.1007","volume":"142","author":[{"given":"Marc","family":"Hellmuth","sequence":"first","affiliation":[]},{"given":"David","family":"Schaller","sequence":"additional","affiliation":[]},{"given":"Peter F.","family":"Stadler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,12]]},"reference":[{"key":"398_CR1","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0201008","volume":"1","author":"AV Aho","year":"1972","unstructured":"Aho AV, Garey MR, Ullman JD (1972) The transitive reduction of a directed graph. SIAM J Comput 1:131\u2013137. https:\/\/doi.org\/10.1137\/0201008","journal-title":"SIAM J Comput"},{"issue":"3","key":"398_CR2","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"AV Aho","year":"1981","unstructured":"Aho AV, Sagiv Y, Szymanski TG, Ullman JD (1981) Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J Comput 10(3):405\u2013421. https:\/\/doi.org\/10.1137\/0210030","journal-title":"SIAM J Comput"},{"issue":"1\u20132","key":"398_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3233\/FI-2014-1087","volume":"134","author":"A Alcal\u00e0","year":"2014","unstructured":"Alcal\u00e0 A, Llabr\u00e9s M, Rossell\u00f3 F, Rullan P (2014) Tree-child cluster networks. Fundam Inf 134(1\u20132):1\u201315. https:\/\/doi.org\/10.3233\/FI-2014-1087","journal-title":"Fundam Inf"},{"key":"398_CR4","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF02458841","volume":"51","author":"H-J Bandelt","year":"1989","unstructured":"Bandelt H-J, Dress AWM (1989) Weak hierarchies associated with similarity measures\u2014an additive clustering technique. Bull Math Biol 51:133\u2013166. https:\/\/doi.org\/10.1007\/BF02458841","journal-title":"Bull Math Biol"},{"key":"398_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0001-8708(92)90061-O","volume":"92","author":"H-J Bandelt","year":"1992","unstructured":"Bandelt H-J, Dress AWM (1992) A canonical decomposition theory for metrics on a finite set. Adv Math 92:47\u2013105. https:\/\/doi.org\/10.1016\/0001-8708(92)90061-O","journal-title":"Adv Math"},{"key":"398_CR6","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s00026-006-0271-0","volume":"10","author":"M Baroni","year":"2006","unstructured":"Baroni M, Steel M (2006) Accumulation phylogenies. Ann Comb 10:19\u201330. https:\/\/doi.org\/10.1007\/s00026-006-0271-0","journal-title":"Ann Comb"},{"key":"398_CR7","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s00026-004-0228-0","volume":"8","author":"M Baroni","year":"2004","unstructured":"Baroni M, Semple C, Steel M (2004) A framework for representing reticulate evolution. Ann Comb 8:391\u2013408. https:\/\/doi.org\/10.1007\/s00026-004-0228-0","journal-title":"Ann Comb"},{"key":"398_CR8","doi-asserted-by":"publisher","first-page":"1237","DOI":"10.1016\/j.dam.2007.05.024","volume":"156","author":"J-P Barth\u00e9lemy","year":"2008","unstructured":"Barth\u00e9lemy J-P, Brucker F (2008) Binary clustering. Discrete Appl Math 156:1237\u20131250. https:\/\/doi.org\/10.1016\/j.dam.2007.05.024","journal-title":"Discrete Appl Math"},{"key":"398_CR9","doi-asserted-by":"publisher","unstructured":"Bender MA, Pemmasani G, Skiena S, Sumazin P (2001) Finding least common ancestors in directed acyclic graphs. In: SODA \u201901: proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms, pp 845\u2013853. Society for Industrial and Applied Mathematics, Washington. https:\/\/doi.org\/10.5555\/365411.365795","DOI":"10.5555\/365411.365795"},{"key":"398_CR10","doi-asserted-by":"publisher","first-page":"1220","DOI":"10.1016\/j.dam.2007.05.023","volume":"156","author":"P Bertrand","year":"2008","unstructured":"Bertrand P (2008) Systems of sets such that each set properly intersects at most one other set\u2014application to cluster analysis. Discr Appl Math 156:1220\u20131236. https:\/\/doi.org\/10.1016\/j.dam.2007.05.023","journal-title":"Discr Appl Math"},{"key":"398_CR11","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1002\/widm.1096","volume":"3","author":"P Bertrand","year":"2013","unstructured":"Bertrand P, Diatta J (2013) Prepyramidal clustering and Robinsonian dissimilarities: one-to-one correspondences. WIREs Data Min Knowl Discov 3:290\u2013297. https:\/\/doi.org\/10.1002\/widm.1096","journal-title":"WIREs Data Min Knowl Discov"},{"key":"398_CR12","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/978-1-4939-0742-7_14","volume-title":"Clusters, orders, and trees: methods and applications","author":"P Bertrand","year":"2014","unstructured":"Bertrand P, Diatta J (2014) Weak hierarchies: a central clustering structure. In: Aleskerov F, Goldengorin B, Pardalos PM (eds) Clusters, orders, and trees: methods and applications. Springer, New York, pp 211\u2013230. https:\/\/doi.org\/10.1007\/978-1-4939-0742-7_14"},{"key":"398_CR13","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.aam.2016.04.004","volume":"78","author":"M Bordewich","year":"2016","unstructured":"Bordewich M, Semple C (2016) Reticulation-visible networks. Adv Appl Math 78:114\u2013141. https:\/\/doi.org\/10.1016\/j.aam.2016.04.004","journal-title":"Adv Appl Math"},{"key":"398_CR14","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s00285-015-0950-8","volume":"73","author":"M Bordewich","year":"2016","unstructured":"Bordewich M, Semple C (2016) Determining phylogenetic networks from inter-taxa distances. J Math Biol 73:283\u2013303. https:\/\/doi.org\/10.1007\/s00285-015-0950-8","journal-title":"J Math Biol"},{"key":"398_CR15","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s11634-009-0046-7","volume":"3","author":"F Brucker","year":"2009","unstructured":"Brucker F, G\u00e9ly A (2009) Parsimonious cluster systems. Adv Data Anal Classif 3:189\u2013204. https:\/\/doi.org\/10.1007\/s11634-009-0046-7","journal-title":"Adv Data Anal Classif"},{"key":"398_CR16","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, Marc H (2022) From modular decomposition trees to rooted median graphs. Discrete Appl Math 310:1\u20139. https:\/\/doi.org\/10.1016\/j.dam.2021.12.017","journal-title":"Discrete Appl Math"},{"issue":"1","key":"398_CR17","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/0095-8956(74)90047-1","volume":"17","author":"P Buneman","year":"1974","unstructured":"Buneman P (1974) A note on the metric properties of trees. J Comb Theory Ser B 17(1):48\u201350. https:\/\/doi.org\/10.1016\/0095-8956(74)90047-1","journal-title":"J Comb Theory Ser B"},{"key":"398_CR18","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1109\/TCBB.2007.70270","volume":"6","author":"G Cardona","year":"2009","unstructured":"Cardona G, Rossell\u00f3 F, Valiente G (2009) Comparison of tree-child phylogenetic networks. IEEE\/ACM Trans Comput Biol Bioinf 6:552\u2013569. https:\/\/doi.org\/10.1109\/TCBB.2007.70270","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"398_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.26493\/2590-9770.1260.989","volume":"2","author":"M Changat","year":"2019","unstructured":"Changat M, Narasimha-Shenoi PG, Stadler PF (2019) Axiomatic characterization of transit functions of weak hierarchies. Art Discrete Appl Math 2:1\u201301. https:\/\/doi.org\/10.26493\/2590-9770.1260.989","journal-title":"Art Discrete Appl Math"},{"key":"398_CR20","unstructured":"Changat M, Shanavas AV, Stadler PF (2022) Transit functions and clustering systems. Submitted"},{"issue":"4","key":"398_CR21","first-page":"433","volume":"3","author":"G Chartrand","year":"1967","unstructured":"Chartrand G, Harary F (1967) Planar permutation graphs. Ann Inst Henri Poincar\u00e9 B Calcul Prob Stat 3(4):433\u2013438","journal-title":"Ann Inst Henri Poincar\u00e9 B Calcul Prob Stat"},{"key":"398_CR22","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.entcs.2003.12.009","volume":"91","author":"C Choy","year":"2004","unstructured":"Choy C, Jansson J, Sadakane K, Sung W-K (2004) Computing the maximum agreement of phylogenetic networks. Electron Notes Theor Comput Sci 91:134\u2013147. https:\/\/doi.org\/10.1016\/j.entcs.2003.12.009","journal-title":"Electron Notes Theor Comput Sci"},{"key":"398_CR23","first-page":"201","volume-title":"Multidimensional data analysis proceedings","author":"E Diday","year":"1986","unstructured":"Diday E (1986) Orders and overlapping clusters in pyramids. In: De Leeuw J, Heiser W, Meulman J, Critchley F (eds) Multidimensional data analysis proceedings. DSWO Press, Leiden, pp 201\u2013234"},{"key":"398_CR24","doi-asserted-by":"publisher","volume-title":"Graph theory. Graduate texts in mathematics","author":"R Diestel","year":"2017","unstructured":"Diestel R (2017) Graph theory. Graduate texts in mathematics, vol 173. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-662-53622-3","DOI":"10.1007\/978-3-662-53622-3"},{"key":"398_CR25","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/j.tcs.2019.09.003","volume":"796","author":"J D\u00f6cker","year":"2019","unstructured":"D\u00f6cker J, Linz S, Semple C (2019) Displaying trees across two phylogenetic networks. Theor Comput Sci 796:129\u2013146. https:\/\/doi.org\/10.1016\/j.tcs.2019.09.003","journal-title":"Theor Comput Sci"},{"key":"398_CR26","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1090\/dimacs\/037\/19","volume-title":"Mathematical hierarchies and biology. DIMACS series in discrete mathematics and theoretical computer science","author":"AWM Dress","year":"1997","unstructured":"Dress AWM (1997) Towards a theory of holistic clustering. In: Mirkin B, McMorris FR, Roberts A, Fred SR (eds) Mathematical hierarchies and biology. DIMACS series in discrete mathematics and theoretical computer science, vol 37. American Mathematical Society, Providence, pp 271\u2013289. https:\/\/doi.org\/10.1090\/dimacs\/037\/19"},{"key":"398_CR27","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0304-0208(08)72924-4","volume":"12","author":"P Duchet","year":"1984","unstructured":"Duchet P (1984) Classical perfect graphs\u2014an introduction with emphasis on triangulated and interval graphs. Ann Discrete Math 12:67\u201396. https:\/\/doi.org\/10.1016\/S0304-0208(08)72924-4","journal-title":"Ann Discrete Math"},{"issue":"5","key":"398_CR28","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1093\/sysbio\/syv037","volume":"64","author":"AR Francis","year":"2015","unstructured":"Francis AR, Steel M (2015) Which phylogenetic networks are merely trees with additional arcs? Syst Biol 64(5):768\u2013777. https:\/\/doi.org\/10.1093\/sysbio\/syv037","journal-title":"Syst Biol"},{"key":"398_CR29","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/s00285-011-0456-y","volume":"65","author":"P Gambette","year":"2012","unstructured":"Gambette P, Huber KT (2012) On encodings of phylogenetic networks of bounded level. J Math Biol 65:157\u2013180. https:\/\/doi.org\/10.1007\/s00285-011-0456-y","journal-title":"J Math Biol"},{"key":"398_CR30","doi-asserted-by":"publisher","first-page":"1250004","DOI":"10.1142\/S0219720012500047","volume":"10","author":"P Gambette","year":"2012","unstructured":"Gambette P, Berry V, Paul C (2012) Quartets and unrooted phylogenetic networks. J Bioinform Comput Biol 10:1250004. https:\/\/doi.org\/10.1142\/S0219720012500047","journal-title":"J Bioinform Comput Biol"},{"key":"398_CR31","doi-asserted-by":"publisher","unstructured":"Gusfield D, Eddhu S, Langley C (2003) Efficient reconstruction of phylogenetic networks with constrained recombination. In: CSB \u201903: proceedings of the IEEE computer society conference on bioinformatics, pp 363\u2013374. IEEE Computer Society, Washington DC. https:\/\/doi.org\/10.1109\/CSB.2003.1227337","DOI":"10.1109\/CSB.2003.1227337"},{"key":"398_CR32","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/978-3-319-41324-2_21","volume-title":"Evolutionary biology: convergent evolution, evolution of complex traits, concepts and methods","author":"M Hellmuth","year":"2016","unstructured":"Hellmuth M, Wieseke N (2016) From sequence data including orthologs, paralogs, and xenologs to gene and species trees. In: Pontarotti P (ed) Evolutionary biology: convergent evolution, evolution of complex traits, concepts and methods. Springer, Cham, pp 373\u2013392. https:\/\/doi.org\/10.1007\/978-3-319-41324-2_21"},{"issue":"7","key":"398_CR33","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 H-P, Middendorf M, Stadler PF (2015) Phylogenomics with paralogs. Proc Natl Acad Sci USA 112(7):2058\u20132063. https:\/\/doi.org\/10.1073\/pnas.1412770112","journal-title":"Proc Natl Acad Sci USA"},{"issue":"5","key":"398_CR34","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 (2019) Reconciling event-labeled gene trees with MUL-trees and species networks. J Math Biol 79(5):1885\u20131925. https:\/\/doi.org\/10.1007\/s00285-019-01414-8","journal-title":"J Math Biol"},{"key":"398_CR35","doi-asserted-by":"publisher","unstructured":"Hellmuth M, Scholz GE (2021) Pseudo-cographs, polar-cats and level-1 network explainable graphs. Technical Report. arXiv arXiv:2112.05537. https:\/\/doi.org\/10.48550\/arXiv.1906.07430","DOI":"10.48550\/arXiv.1906.07430"},{"issue":"5","key":"398_CR36","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 (2006) Phylogenetic networks from multi-labelled trees. J Math Biol 52(5):613\u2013632. https:\/\/doi.org\/10.1007\/s00285-005-0365-z","journal-title":"J Math Biol"},{"issue":"3","key":"398_CR37","doi-asserted-by":"publisher","first-page":"714","DOI":"10.1007\/s00453-012-9659-x","volume":"66","author":"KT Huber","year":"2013","unstructured":"Huber KT, Moulton V (2013) Encoding and constructing 1-nested phylogenetic networks with trinets. Algorithmica 66(3):714\u2013738. https:\/\/doi.org\/10.1007\/s00453-012-9659-x","journal-title":"Algorithmica"},{"key":"398_CR38","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 (2018) Beyond representing orthology relations with trees. Algorithmica 80:73\u2013103. https:\/\/doi.org\/10.1007\/s00453-016-0241-9","journal-title":"Algorithmica"},{"key":"398_CR39","doi-asserted-by":"publisher","DOI":"10.1016\/j.aam.2019.101959","volume":"113","author":"KT Huber","year":"2020","unstructured":"Huber KT, Scholz GE (2020) Phylogenetic networks that are their own fold-ups. Adv Appl Math 113:101959. https:\/\/doi.org\/10.1016\/j.aam.2019.101959","journal-title":"Adv Appl Math"},{"issue":"1","key":"398_CR40","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s00453-015-0069-8","volume":"77","author":"KT Huber","year":"2017","unstructured":"Huber KT, Van Iersel L, Moulton V, Scornavacca C, Wu T (2017) Reconstructing phylogenetic level-1 networks from nondense binet and trinet sets. Algorithmica 77(1):173\u2013200. https:\/\/doi.org\/10.1007\/s00453-015-0069-8","journal-title":"Algorithmica"},{"key":"398_CR41","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/s000357-018-9279-5","volume":"36","author":"KT Huber","year":"2019","unstructured":"Huber KT, Moulton V, Wu T (2019) Hierarchies from lowest stable ancestors in nonbinary phylogenetic networks. J Classif 36:200\u2013231. https:\/\/doi.org\/10.1007\/s000357-018-9279-5","journal-title":"J Classif"},{"key":"398_CR42","doi-asserted-by":"publisher","unstructured":"Huber KT, van Iersel L, Janssen R, Jones M, Moulton V, Murakami Y, Semple C (2019) Orienting undirected phylogenetic networks. Technical Report. arXiv arXiv:1906.07430. https:\/\/doi.org\/10.48550\/arXiv.1906.07430","DOI":"10.48550\/arXiv.1906.07430"},{"key":"398_CR43","doi-asserted-by":"publisher","volume-title":"Algorithms in bioinformatics. WABI. Lecture notes in computer science","author":"DH Huson","year":"2008","unstructured":"Huson DH, Rupp R (2008) Summarizing multiple gene trees using cluster networks. In: Crandall KA, Lagergren J (eds) Algorithms in bioinformatics. WABI. Lecture notes in computer science, vol 5251. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-540-87361-7_25","DOI":"10.1007\/978-3-540-87361-7_25"},{"key":"398_CR44","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1093\/gbe\/evq077","volume":"3","author":"DH Huson","year":"2011","unstructured":"Huson DH, Scornavacca C (2011) A survey of combinatorial methods for phylogenetic networks. Genome Biol Evol 3:23\u201335. https:\/\/doi.org\/10.1093\/gbe\/evq077","journal-title":"Genome Biol Evol"},{"key":"398_CR45","doi-asserted-by":"publisher","volume-title":"Phylogenetic networks: concepts, algorithms and applications","author":"DH Huson","year":"2010","unstructured":"Huson DH, Rupp R, Scornavacca C (2010) Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press, Cambridge. https:\/\/doi.org\/10.1017\/CBO9780511974076","DOI":"10.1017\/CBO9780511974076"},{"key":"398_CR46","doi-asserted-by":"publisher","volume-title":"Ordinal and relational clustering. Interdisciplinary mathematical sciences","author":"MF Janowitz","year":"2010","unstructured":"Janowitz MF (2010) Ordinal and relational clustering. Interdisciplinary mathematical sciences, vol 10. World Scientific, Singapore","DOI":"10.1142\/7449"},{"issue":"1","key":"398_CR47","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.tcs.2006.06.022","volume":"363","author":"J Jansson","year":"2006","unstructured":"Jansson J, Sung W-K (2006) Inferring a level-1 phylogenetic network from a dense set of rooted triplets. Theor Comput Sci 363(1):60\u201368. https:\/\/doi.org\/10.1016\/j.tcs.2006.06.022","journal-title":"Theor Comput Sci"},{"issue":"5","key":"398_CR48","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1137\/S0097539704446529","volume":"35","author":"J Jansson","year":"2006","unstructured":"Jansson J, Nguyen NB, Sung W-K (2006) Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM J Comput 35(5):1098\u20131121. https:\/\/doi.org\/10.1137\/S0097539704446529","journal-title":"SIAM J Comput"},{"key":"398_CR49","volume-title":"Mathematical taxonomy","author":"N Jardine","year":"1971","unstructured":"Jardine N, Sibson R (1971) Mathematical taxonomy. Wiley, London"},{"issue":"1","key":"398_CR50","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/TCBB.2016.2615918","volume":"15","author":"L Jetten","year":"2018","unstructured":"Jetten L, van Iersel L (2018) Nonbinary tree-based phylogenetic networks. IEEE\/ACM Trans Comput Biol Bioinform 15(1):205\u2013217. https:\/\/doi.org\/10.1109\/TCBB.2016.2615918","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"398_CR51","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/j.tcs.2008.04.019","volume":"401","author":"IA Kanj","year":"2008","unstructured":"Kanj IA, Nakhleh L, Than C, Xia G (2008) Seeing the trees and their branches in the network is hard. Theor Comput Sci 401:153\u2013164. https:\/\/doi.org\/10.1016\/j.tcs.2008.04.019","journal-title":"Theor Comput Sci"},{"key":"398_CR52","doi-asserted-by":"publisher","first-page":"886","DOI":"10.1007\/s00453-012-9708-5","volume":"68","author":"S Kelk","year":"2014","unstructured":"Kelk S, Scornavacca C (2014) Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable. Algorithmica 68:886\u2013915. https:\/\/doi.org\/10.1007\/s00453-012-9708-5","journal-title":"Algorithmica"},{"key":"398_CR53","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, Kubato L, Wicke K (2022) Classes of explicit phylogenetic networks and their biological and mathematical significance. J Math Biol 84:47. https:\/\/doi.org\/10.1007\/s00285-022-01746-y","journal-title":"J Math Biol"},{"issue":"4","key":"398_CR54","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1007\/s00285-020-01533-7","volume":"81","author":"S Linz","year":"2020","unstructured":"Linz S, Semple C (2020) Caterpillars on three and four leaves are sufficient to reconstruct binary normal networks. J Math Biol 81(4):961\u2013980. https:\/\/doi.org\/10.1007\/s00285-020-01533-7","journal-title":"J Math Biol"},{"key":"398_CR55","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 (2019) Reconstructing tree-child networks from reticulate-edge-deleted subnetworks. Bull Math Biol 81:3823\u20133863. https:\/\/doi.org\/10.1007\/s11538-019-00641-w","journal-title":"Bull Math Biol"},{"key":"398_CR56","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/11567752_6","volume-title":"Transactions on computational systems biology II. Lecture notes in computer science","author":"L Nakhleh","year":"2005","unstructured":"Nakhleh L, Wang L-S (2005) Phylogenetic networks: properties and relationship to trees and clusters. In: Priami C, Zelikovsky A (eds) Transactions on computational systems biology II. Lecture notes in computer science, vol 3680. Springer, Berlin, pp 82\u201399. https:\/\/doi.org\/10.1007\/11567752_6"},{"key":"398_CR57","doi-asserted-by":"publisher","first-page":"1","DOI":"10.21136\/CMJ.1983.101849","volume":"33","author":"L Nebesk\u00fd","year":"1983","unstructured":"Nebesk\u00fd L (1983) On a certain numbering of the vertices of a hypergraph. Czechoslov Math J 33:1\u20136. https:\/\/doi.org\/10.21136\/CMJ.1983.101849","journal-title":"Czechoslov Math J"},{"key":"398_CR58","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1007\/s00285-018-1296-9","volume":"78","author":"JC Pons","year":"2019","unstructured":"Pons JC, Semple C, Steel M (2019) Tree-based networks: characterisations, metrics, and support trees. J Math Biol 78:899\u2013918. https:\/\/doi.org\/10.1007\/s00285-018-1296-9","journal-title":"J Math Biol"},{"key":"398_CR59","volume-title":"Phylogenetics. Oxford lecture series in mathematics and its applications","author":"C Semple","year":"2003","unstructured":"Semple C, Steel M (2003) Phylogenetics. Oxford lecture series in mathematics and its applications, vol 24. Oxford University Press, Oxford"},{"key":"398_CR60","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/s00285-021-01654-7","volume":"83","author":"C Semple","year":"2021","unstructured":"Semple C, Toft G (2021) Trinets encode orchard phylogenetic networks. J Math Biol 83:28. https:\/\/doi.org\/10.1007\/s00285-021-01654-7","journal-title":"J Math Biol"},{"issue":"3","key":"398_CR61","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/S0021-9800(69)80092-X","volume":"6","author":"JMS Sim\u00f5es-Pereira","year":"1969","unstructured":"Sim\u00f5es-Pereira JMS (1969) A note on the tree realizability of a distance matrix. J Comb Theory 6(3):303\u2013310. https:\/\/doi.org\/10.1016\/S0021-9800(69)80092-X","journal-title":"J Comb Theory"},{"key":"398_CR62","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0012-365X(76)80011-8","volume":"16","author":"WT Trotter","year":"1976","unstructured":"Trotter WT, Moore JI (1976) Characterization problems for graph partially ordered sets, lattices and families of sets. Discrete Math 16:361\u2013381. https:\/\/doi.org\/10.1016\/S0012-365X(76)80011-8","journal-title":"Discrete Math"},{"key":"398_CR63","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(72)90019-6","volume":"12","author":"A Tucker","year":"1972","unstructured":"Tucker A (1972) A structure theorem for the consecutive 1\u2019s property. J Comb Theory 12:153\u2013162. https:\/\/doi.org\/10.1016\/0095-8956(72)90019-6","journal-title":"J Comb Theory"},{"issue":"2","key":"398_CR64","doi-asserted-by":"publisher","first-page":"207","DOI":"10.5555\/3118782.3119218","volume":"60","author":"L van Iersel","year":"2011","unstructured":"van Iersel L, Kelk S (2011) Constructing the simplest possible phylogenetic network from triplets. Algorithmica 60(2):207\u2013235. https:\/\/doi.org\/10.5555\/3118782.3119218","journal-title":"Algorithmica"},{"issue":"7","key":"398_CR65","doi-asserted-by":"publisher","first-page":"1707","DOI":"10.1007\/s00285-013-0683-5","volume":"68","author":"L Van Iersel","year":"2014","unstructured":"Van Iersel L, Moulton V (2014) Trinets encode tree-child and level-2 phylogenetic networks. J Math Biol 68(7):1707\u20131729. https:\/\/doi.org\/10.1007\/s00285-013-0683-5","journal-title":"J Math Biol"},{"issue":"4","key":"398_CR66","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1109\/TCBB.2009.22","volume":"6","author":"L Van Iersel","year":"2009","unstructured":"Van Iersel L, Keijsper J, Kelk S, Stougie L, Hagen F, Boekhout T (2009) Constructing level-2 phylogenetic networks from triplets. IEEE\/ACM Trans Comput Biol Bioinf 6(4):667\u2013681. https:\/\/doi.org\/10.1109\/TCBB.2009.22","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"issue":"5","key":"398_CR67","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1007\/s11538-017-0275-4","volume":"79","author":"L Van Iersel","year":"2017","unstructured":"Van Iersel L, Moulton V, de Swart E, Wu T (2017) Binets: fundamental building blocks for phylogenetic networks. Bull Math Biol 79(5):1135\u20131154. https:\/\/doi.org\/10.1007\/s11538-017-0275-4","journal-title":"Bull Math Biol"},{"key":"398_CR68","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1007\/s11538-017-0275-4","volume":"79","author":"L van Iersel","year":"2017","unstructured":"van Iersel L, Moulton V, de Swart E, Wu T (2017) Binets: fundamental building blocks for phylogenetic networks. Bull Math Biol 79:1135\u20131154. https:\/\/doi.org\/10.1007\/s11538-017-0275-4","journal-title":"Bull Math Biol"},{"key":"398_CR69","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2022.106300","volume":"178","author":"L Van Iersel","year":"2022","unstructured":"Van Iersel L, Kole S, Moulton V, Nipius L (2022) An algorithm for reconstructing level-2 phylogenetic networks from trinets. Inf Process Lett 178:106300. https:\/\/doi.org\/10.1016\/j.ipl.2022.106300","journal-title":"Inf Process Lett"},{"key":"398_CR70","volume-title":"Introduction to graph theory","author":"DB West","year":"2001","unstructured":"West DB (2001) Introduction to graph theory, 2nd edn. Prentice Hall, Upper Saddle River","edition":"2"},{"key":"398_CR71","doi-asserted-by":"publisher","first-page":"785","DOI":"10.1109\/TCBB.2010.69","volume":"8","author":"S Willson","year":"2010","unstructured":"Willson S (2010) Regular networks can be uniquely constructed from their trees. IEEE\/ACM Trans Comput Biol Bioinf 8:785\u2013796. https:\/\/doi.org\/10.1109\/TCBB.2010.69","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"398_CR72","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/s11538-009-9449-z","volume":"72","author":"SJ Willson","year":"2010","unstructured":"Willson SJ (2010) Properties of normal phylogenetic networks. Bull Math Biol 72:340\u2013358. https:\/\/doi.org\/10.1007\/s11538-009-9449-z","journal-title":"Bull Math Biol"},{"issue":"7","key":"398_CR73","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1089\/cmb.2015.0228","volume":"23","author":"L Zhang","year":"2016","unstructured":"Zhang L (2016) On tree-based phylogenetic networks. J Comput Biol 23(7):553\u2013565. https:\/\/doi.org\/10.1089\/cmb.2015.0228","journal-title":"J Comput Biol"},{"key":"398_CR74","doi-asserted-by":"publisher","volume-title":"Bioinformatics and phylogenetics. Computational biology","author":"L Zhang","year":"2019","unstructured":"Zhang L (2019) Clusters, trees, and phylogenetic network classes. In: Warnow T (ed) Bioinformatics and phylogenetics. Computational biology, vol 29. Springer, Cham. https:\/\/doi.org\/10.1007\/978-3-030-10837-3_12","DOI":"10.1007\/978-3-030-10837-3_12"}],"container-title":["Theory in Biosciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12064-023-00398-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s12064-023-00398-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s12064-023-00398-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T17:17:38Z","timestamp":1696958258000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s12064-023-00398-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,12]]},"references-count":74,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["398"],"URL":"http:\/\/dx.doi.org\/10.1007\/s12064-023-00398-w","relation":{},"ISSN":["1431-7613","1611-7530"],"issn-type":[{"value":"1431-7613","type":"print"},{"value":"1611-7530","type":"electronic"}],"subject":["Applied Mathematics","Ecology, Evolution, Behavior and Systematics","Statistics and Probability"],"published":{"date-parts":[[2023,8,12]]},"assertion":[{"value":"28 April 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2023","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 that they have no conflict of interest","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}} |