Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor
Recovering normal networks from shortest inter-taxa distance information
Bordewich, Magnus; Huber, Katharina T.; Moulton, Vincent; Semple, Charles
Authors
Katharina T. Huber
Vincent Moulton
Charles Semple
Abstract
Phylogenetic networks are a type of leaf-labelled, acyclic, directed graph used by biologists to represent the evolutionary history of species whose past includes reticulation events. A phylogenetic network is tree–child if each non-leaf vertex is the parent of a tree vertex or a leaf. Up to a certain equivalence, it has been recently shown that, under two different types of weightings, edge-weighted tree–child networks are determined by their collection of distances between each pair of taxa. However, the size of these collections can be exponential in the size of the taxa set. In this paper, we show that, if we have no “shortcuts”, that is, the networks are normal, the same results are obtained with only a quadratic number of inter-taxa distances by using the shortest distance between each pair of taxa. The proofs are constructive and give cubic-time algorithms in the size of the taxa sets for building such weighted networks.
Citation
Bordewich, M., Huber, K. T., Moulton, V., & Semple, C. (2018). Recovering normal networks from shortest inter-taxa distance information. Journal of Mathematical Biology, 77(3), 571-594. https://doi.org/10.1007/s00285-018-1218-x
Journal Article Type | Article |
---|---|
Acceptance Date | Feb 6, 2018 |
Online Publication Date | Feb 24, 2018 |
Publication Date | Sep 30, 2018 |
Deposit Date | Feb 16, 2018 |
Publicly Available Date | Feb 24, 2019 |
Journal | Journal of Mathematical Biology |
Print ISSN | 0303-6812 |
Electronic ISSN | 1432-1416 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 77 |
Issue | 3 |
Pages | 571-594 |
DOI | https://doi.org/10.1007/s00285-018-1218-x |
Files
Accepted Journal Article
(315 Kb)
PDF
Copyright Statement
The final publication is available at Springer via https://doi.org/10.1007/s00285-018-1218-x
You might also like
Evaluating Gaussian Grasp Maps for Generative Grasping Models
(2022)
Conference Proceeding
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
(2022)
Journal Article
On the Maximum Agreement Subtree Conjecture for Balanced Trees
(2022)
Journal Article
Autoencoders Without Reconstruction for Textural Anomaly Detection
(2021)
Conference Proceeding
Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
(2021)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search