IDEAS home Printed from https://ideas.repec.org/a/plo/pcbi00/1007347.html
   My bibliography  Save this article

Generation of Binary Tree-Child phylogenetic networks

Author

Listed:
  • Gabriel Cardona
  • Joan Carles Pons
  • Celine Scornavacca

Abstract

Phylogenetic networks generalize phylogenetic trees by allowing the modelization of events of reticulate evolution. Among the different kinds of phylogenetic networks that have been proposed in the literature, the subclass of binary tree-child networks is one of the most studied ones. However, very little is known about the combinatorial structure of these networks. In this paper we address the problem of generating all possible binary tree-child (BTC) networks with a given number of leaves in an efficient way via reduction/augmentation operations that extend and generalize analogous operations for phylogenetic trees, and are biologically relevant. Since our solution is recursive, this also provides us with a recurrence relation giving an upper bound on the number of such networks. We also show how the operations introduced in this paper can be employed to extend the evolutive history of a set of sequences, represented by a BTC network, to include a new sequence. An implementation in python of the algorithms described in this paper, along with some computational experiments, can be downloaded from https://github.com/bielcardona/TCGenerators.Author summary: Phylogenetic networks are widely used to represent evolutionary scenarios with reticulated events, and among them, the class of binary tree-child (BTC for short) networks is one of the most studied ones. Despite its importance, BTC networks, as mathematical objects, are not yet fully understood. In this paper we introduce two operations (reduction and augmentation) on the set of BTC networks that generalize well known operations on phylogenetic trees, and show how they can be used to analyze and synthesize any BTC network. Apart from the mathematical formulation of the problem, we exhibit how these operations can be used in biological applications to add a new sequence to a given BTC network. This can be useful, for instance, to update the network without redoing the whole search, or in a phylogenetic placement perspective. We also obtain a recursive formula for a bound on the number of such networks. We have implemented the algorithms in this paper, made them available on a public repository, and used this implementation to perform some computational simulations.

Suggested Citation

  • Gabriel Cardona & Joan Carles Pons & Celine Scornavacca, 2019. "Generation of Binary Tree-Child phylogenetic networks," PLOS Computational Biology, Public Library of Science, vol. 15(9), pages 1-29, September.
  • Handle: RePEc:plo:pcbi00:1007347
    DOI: 10.1371/journal.pcbi.1007347
    as

    Download full text from publisher

    File URL: https://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.1007347
    Download Restriction: no

    File URL: https://journals.plos.org/ploscompbiol/article/file?id=10.1371/journal.pcbi.1007347&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pcbi.1007347?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Philippe Gambette & Leo van Iersel & Mark Jones & Manuel Lafond & Fabio Pardi & Celine Scornavacca, 2017. "Rearrangement moves on rooted phylogenetic networks," PLOS Computational Biology, Public Library of Science, vol. 13(8), pages 1-21, August.
    2. Meng, Chen & Kubatko, Laura Salter, 2009. "Detecting hybrid speciation in the presence of incomplete lineage sorting using gene tree incongruence: A model," Theoretical Population Biology, Elsevier, vol. 75(1), pages 35-45.
    3. Editors The, 2007. "From the Editors," Basic Income Studies, De Gruyter, vol. 2(1), pages 1-5, June.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Eloi Laurent, 2010. "Environmental justice and environmental inequalities: A European perspective," Working Papers hal-01069412, HAL.
    2. Laurent, Catherine E. & Berriet-Solliec, Marielle & Kirsch, Marc & Labarthe, Pierre & Trouve, Aurelie, 2010. "Multifunctionality Of Agriculture, Public Policies And Scientific Evidences: Some Critical Issues Of Contemporary Controversies," APSTRACT: Applied Studies in Agribusiness and Commerce, AGRIMBA, vol. 4(01-2), pages 1-6.
    3. Juan Carlos Conesa & Timothy J. Kehoe & Kim J. Ruhl, 2007. "Modeling great depressions: the depression in Finland in the 1990s," Quarterly Review, Federal Reserve Bank of Minneapolis, vol. 31(Nov), pages 16-44.
    4. Adilson Carlos Yoshikuni & José Eduardo Ricciardi Favaretto & Alberto Luiz Albertin & Fernando de Souza Meirelles, 2022. "How can Strategy-as-Practice Enable Innovation under the Influence of Environmental Dynamism?," RAC - Revista de Administração Contemporânea (Journal of Contemporary Administration), ANPAD - Associação Nacional de Pós-Graduação e Pesquisa em Administração, vol. 26(1), pages 200131-2001.
    5. Paola Gatti & Chiara Ghislieri & Claudio G Cortese, 2017. "Relationships between followers’ behaviors and job satisfaction in a sample of nurses," PLOS ONE, Public Library of Science, vol. 12(10), pages 1-16, October.
    6. repec:spo:wpmain:info:hdl:2441/eu4vqp9ompqllr09hi4ijb1r1 is not listed on IDEAS
    7. Premand, Patrick & Brodmann, Stefanie & Almeida, Rita & Grun, Rebekka & Barouni, Mahdi, 2016. "Entrepreneurship Education and Entry into Self-Employment Among University Graduates," World Development, Elsevier, vol. 77(C), pages 311-327.
    8. D. K. Choudhury, 2019. "Standard Critical Path and Selection of Most Economic and Quality Contractors for Construction of Thermal Power Plant: A Case Study in NTPC," Metamorphosis: A Journal of Management Research, , vol. 18(2), pages 103-118, December.
    9. Ayanlade Ayansina & Olugbade Adeoye Nathaniel & Babatimehin Oyekanmi, 2013. "Intra-annual climate variability and malaria transmission in Nigeria," Bulletin of Geography. Socio-economic Series, Sciendo, vol. 21(21), pages 7-19, September.
    10. Timothy B Smith & Connor Workman & Caleb Andrews & Bonnie Barton & Matthew Cook & Ryan Layton & Alexandra Morrey & Devin Petersen & Julianne Holt-Lunstad, 2021. "Effects of psychosocial support interventions on survival in inpatient and outpatient healthcare settings: A meta-analysis of 106 randomized controlled trials," PLOS Medicine, Public Library of Science, vol. 18(5), pages 1-25, May.
    11. V. Vandenberghe & F. Waltenberg & M. Rigo, 2013. "Ageing and employability. Evidence from Belgian firm-level data," Journal of Productivity Analysis, Springer, vol. 40(1), pages 111-136, August.
    12. Nicola F. Müller & Kathryn E. Kistler & Trevor Bedford, 2022. "A Bayesian approach to infer recombination patterns in coronaviruses," Nature Communications, Nature, vol. 13(1), pages 1-9, December.
    13. Amelie F. Constant, 2019. "Return, Circular, and Onward Migration Decisions in a Knowledge Society," CESifo Working Paper Series 7913, CESifo.
    14. Peter M. Bednar & Christine Welch, 0. "Socio-Technical Perspectives on Smart Working: Creating Meaningful and Sustainable Systems," Information Systems Frontiers, Springer, vol. 0, pages 1-18.
    15. Lopera Baena, Maria Adelaida, 2016. "Evidence of Conditional and Unconditional Cooperation in a Public Goods Game: Experimental Evidence from Mali," VfS Annual Conference 2016 (Augsburg): Demographic Change 145797, Verein für Socialpolitik / German Economic Association.
    16. Haile, Kaleab K. & Nillesen, Eleonora & Tirivayi, Nyasha, 2020. "Impact of formal climate risk transfer mechanisms on risk-aversion: Empirical evidence from rural Ethiopia," World Development, Elsevier, vol. 130(C).
    17. Chloe N. East & Sarah Miller & Marianne Page & Laura R. Wherry, 2023. "Multigenerational Impacts of Childhood Access to the Safety Net: Early Life Exposure to Medicaid and the Next Generation's Health," American Economic Review, American Economic Association, vol. 113(1), pages 98-135, January.
    18. Luyao Wang & Hong Fan & Yankun Wang, 2018. "Estimation of consumption potentiality using VIIRS night-time light data," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-19, October.
    19. Elisabeth Paul & Céline Deville & Oriane Bodson & N'koué Emmanuel Sambiéni & Ibrahima Thiam & Marc Bourgeois & Valéry Ridde & Fabienne Fecher, 2019. "How is equity approached in universal health coverage? An analysis of global and country policy documents in Benin and Senegal," ULB Institutional Repository 2013/298047, ULB -- Universite Libre de Bruxelles.
    20. Håvard T Rydland & Erlend L Fjær & Terje A Eikemo & Tim Huijts & Clare Bambra & Claus Wendt & Ivana Kulhánová & Pekka Martikainen & Chris Dibben & Ramunė Kalėdienė & Carme Borrell & Mall Leinsalu & Ma, 2020. "Educational inequalities in mortality amenable to healthcare. A comparison of European healthcare systems," PLOS ONE, Public Library of Science, vol. 15(7), pages 1-17, July.
    21. David Card & Jochen Kluve & Andrea Weber, 2010. "Active Labour Market Policy Evaluations: A Meta-Analysis," Economic Journal, Royal Economic Society, vol. 120(548), pages 452-477, November.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:plo:pcbi00:1007347. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ploscompbiol (email available below). General contact details of provider: https://journals.plos.org/ploscompbiol/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.