IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v47y2024i5d10.1007_s10878-024-01181-3.html
   My bibliography  Save this article

Phylogenetic network-assisted rooting of unrooted gene trees

Author

Listed:
  • Jerzy Tiuryn

    (Institute of Informatics, University of Warsaw)

  • Natalia Rutecka

    (Institute of Informatics, University of Warsaw)

  • Paweł Górecki

    (Institute of Informatics, University of Warsaw)

Abstract

Gene trees inferred from molecular sequence alignments are typically unrooted, and determining the most credible rooting edge is a classical problem in computational biology. One approach to solve this problem is unrooted reconciliation, where the rooting edge is postulated based on the split of the root from a given species tree. In this paper, we propose a novel variant of the gene tree rooting problem, where the gene tree root is inferred using a phylogenetic network of the species present in the gene tree. To obtain the best rooting, unrooted reconciliation can be applied, where the unrooted gene tree is jointly reconciled with a set of splits inferred from the network. However, the exponential size of the set induced by display trees of the network makes this approach computationally prohibitive. To address this, we propose a broader and easier-to-control set of splits based on the structural properties of the network. We then derive exact mathematical formulas for the rooting problem and propose two general rooting algorithms to handle cases where the input network does not meet the initial requirements. Our experimental study based on simulated gene trees and networks demonstrates that our algorithms infer gene tree rootings correctly or with a small error in most cases.

Suggested Citation

  • Jerzy Tiuryn & Natalia Rutecka & Paweł Górecki, 2024. "Phylogenetic network-assisted rooting of unrooted gene trees," Journal of Combinatorial Optimization, Springer, vol. 47(5), pages 1-27, July.
    • Handle: RePEc:spr:jcomop:v:47:y:2024:i:5:d:10.1007_s10878-024-01181-3
    DOI: 10.1007/s10878-024-01181-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-024-01181-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-024-01181-3?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Taylor Wade & L Thiberio Rangel & Soumya Kundu & Gregory P Fournier & Mukul S Bansal, 2020. "Assessing the accuracy of phylogenetic rooting methods on prokaryotic gene families," PLOS ONE, Public Library of Science, vol. 15(5), pages 1-22, May.
    2. Uyen Mai & Erfan Sayyari & Siavash Mirarab, 2017. "Minimum variance rooting of phylogenetic trees and implications for species tree reconstruction," PLOS ONE, Public Library of Science, vol. 12(8), pages 1-19, August.
    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.

      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:spr:jcomop:v:47:y:2024:i:5:d:10.1007_s10878-024-01181-3. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

      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.