Phylogenetic network-assisted rooting of unrooted gene trees

Jerzy Tiuryn (), Natalia Rutecka () and Paweł Górecki ()
Additional contact information
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

Journal of Combinatorial Optimization, 2024, vol. 47, issue 5, No 12, 27 pages

Abstract: 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.

Keywords: Phylogenetic network; Rooting; Unrooted gene tree; Unrooted reconciliation (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-024-01181-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:47:y:2024:i:5:d:10.1007_s10878-024-01181-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-024-01181-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().