Squirrel: Reconstructing semi-directed phylogenetic level-1 networks from four-leaved networks or sequence alignments DOI Creative Commons
Niels Holtgrefe, Katharina T. Huber, Leo van Iersel

et al.

bioRxiv (Cold Spring Harbor Laboratory), Journal Year: 2024, Volume and Issue: unknown

Published: Nov. 3, 2024

Abstract Phylogenetic networks model the evolutionary history of taxa while allowing for reticulate events such as hybridization and horizontal gene transfer. As is case phylogenetic trees, it often not possible to infer root location a network directly from biological data several models. Hence, we consider semi-directed (phylogenetic) networks: partially directed graphs without in which edges represent events. By specifying known outgroup, rooted topology can be recovered networks. We introduce algorithm S quirrel ( emi-directed Quarnet-based Inference Reconstruct Level-1 Networks) constructs level-1 full set quarnets (four-leaf networks). Our method also includes heuristic construct quarnet sequence alignments. To build quarnets, first builds tree, after repeatedly solves T ravelling alesman P roblem (TSP) replace each high-degree vertex by cycle. demonstrate ’s performance on randomly generated real sets, largest contains 29 aligned sequences close 1.7 Mpb long. The resulting are obtained standard laptop within few minutes. Lastly, prove that combinatorially consistent: given coming triangle-free network, guaranteed reconstruct original network. implemented Python, has an easy-to-use graphical user-interface takes alignments or input, freely available at https://github.com/nholtgrefe/squirrel .

Language: Английский

Squirrel: Reconstructing semi-directed phylogenetic level-1 networks from four-leaved networks or sequence alignments DOI Creative Commons
Niels Holtgrefe, Katharina T. Huber, Leo van Iersel

et al.

bioRxiv (Cold Spring Harbor Laboratory), Journal Year: 2024, Volume and Issue: unknown

Published: Nov. 3, 2024

Abstract Phylogenetic networks model the evolutionary history of taxa while allowing for reticulate events such as hybridization and horizontal gene transfer. As is case phylogenetic trees, it often not possible to infer root location a network directly from biological data several models. Hence, we consider semi-directed (phylogenetic) networks: partially directed graphs without in which edges represent events. By specifying known outgroup, rooted topology can be recovered networks. We introduce algorithm S quirrel ( emi-directed Quarnet-based Inference Reconstruct Level-1 Networks) constructs level-1 full set quarnets (four-leaf networks). Our method also includes heuristic construct quarnet sequence alignments. To build quarnets, first builds tree, after repeatedly solves T ravelling alesman P roblem (TSP) replace each high-degree vertex by cycle. demonstrate ’s performance on randomly generated real sets, largest contains 29 aligned sequences close 1.7 Mpb long. The resulting are obtained standard laptop within few minutes. Lastly, prove that combinatorially consistent: given coming triangle-free network, guaranteed reconstruct original network. implemented Python, has an easy-to-use graphical user-interface takes alignments or input, freely available at https://github.com/nholtgrefe/squirrel .

Language: Английский

Citations

1