SQUIRREL: Reconstructing semi-directed phylogenetic level-1 networks from four-leaved networks or sequence alignments

Tools

Holtgrefe, Niels, Huber, Katharina, van Iersel, Leo, Jones, Mark, Martin, Samuel and Moulton, Vincent (2025) SQUIRREL: Reconstructing semi-directed phylogenetic level-1 networks from four-leaved networks or sequence alignments. Molecular Biology and Evolution, 42 (4). ISSN 0737-4038

[thumbnail of Squirrel_manuscript_biorxiv2] PDF (Squirrel_manuscript_biorxiv2) - Draft Version
Restricted to Repository staff only until 9 March 2026.
Request a copy
[thumbnail of msaf067]
Preview
 PDF (msaf067) - Accepted Version
Available under License Creative Commons Attribution.
Download (3MB) | Preview

Abstract

With the increasing availability of genomic data, biologists aim to find more accurate descriptions of evolutionary histories influenced by secondary contact, where diverging lineages reconnect before diverging again. Such reticulate evolutionary events can be more accurately represented in phylogenetic networks than in phylogenetic trees. Since the root location of phylogenetic networks cannot be inferred from biological data under several evolutionary models, we consider semi-directed (phylogenetic) networks: partially directed graphs without a root in which the directed edges represent reticulate evolutionary events. By specifying a known outgroup, the rooted topology can be recovered from such networks. We introduce the algorithm Squirrel (Semi-directed Quarnet-based Inference to Reconstruct Level-1 Networks) which constructs a semi-directed level-1 network from a full set of quarnets (four-leaf semi-directed networks). Our method also includes a heuristic to construct such a quarnet set directly from sequence alignments. We demonstrate Squirrel's performance through simulations and on real sequence data sets, the largest of which contains 29 aligned sequences close to 1.7 Mb long. The resulting networks are obtained on a standard laptop within a few minutes. Lastly, we prove that Squirrel is combinatorially consistent: given a full set of quarnets coming from a triangle-free semi-directed level-1 network, it is guaranteed to reconstruct the original network. Squirrel is implemented in Python, has an easy-to-use graphical user interface that takes sequence alignments or quarnets as input, and is freely available at https://github.com/nholtgrefe/squirrel.

Item Type: Article
Additional Information: Data Availability Statement: The generated networks, Python scripts, sequence alignments and numerical results of the experiments in this paper are available at https://github.com/nholtgrefe/squirrel. Funding Information: This work received funding from grants OCENW.M.21.306 (N.H., L.v.I., and M.J.) and OCENW.KLEIN.125 (L.v.I. and M.J.) of the Dutch Research Council (NWO). Part of this work was done while some of the authors were in residence at the Institute for Computational and Experimental Research in Mathematics (ICERM) in Providence (RI, USA) during the Theory, Methods, and Applications of Quantitative Phylogenomics program [supported by grant DMS-1929284 of the National Science Foundation (NSF)].
Uncontrolled Keywords: network reconstruction,quarnet,rooted phylogenetic network,semi-directed phylogenetic network,sequence alignment,traveling salesman problem,genetics,ecology, evolution, behavior and systematics,molecular biology ,/dk/atira/pure/subjectarea/asjc/1300/1311
Faculty \ School: Faculty of Science > School of Computing Sciences
UEA Research Groups: Faculty of Science > Research Groups > Norwich Epidemiology Centre
Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Faculty of Science > Research Groups > Computational Biology
Related URLs:
Depositing User: LivePure Connector
Date Deposited: 31 Mar 2025 10:32
Last Modified: 23 Apr 2025 11:30
URI: https://ueaeprints.uea.ac.uk/id/eprint/98904
DOI: 10.1093/molbev/msaf067

Actions (login required)

View Item View Item