Tools
Tools
Moulton, Vincent 
ORCID: https://orcid.org/0000-0001-9371-6435 and Spillner, Andreas
(2012)
Optimal algorithms for computing edge weights in planar split networks.
Journal of Applied Mathematics and Computing, 39 (1-2).
pp. 1-13.
ISSN 1598-5865
Abstract
In phylogenetics, biologists commonly compute split networks when trying to better understand evolutionary data. These graph-theoretical structures represent collections of weighted bipartitions or splits of a finite set, and provide a means to display conflicting evolutionary signals. The weights associated to the splits are used to scale the edges in the network and are often computed using some distance matrix associated with the data. In this paper we present optimal polynomial time algorithms for three basic problems that arise in this context when computing split weights for planar split-networks. These generalize algorithms that have been developed for special classes of split networks (namely, trees and outer-labeled planar networks). As part of our analysis, we also derive a Crofton formula for full flat split systems, structures that naturally arise when constructing planar split-networks.
| Item Type: | Article |
|---|---|
| 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 Faculty of Science > Research Groups > Computational Biology > Computational biology of RNA (former - to 2018) Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) |
| Depositing User: | Users 2731 not found. |
| Date Deposited: | 27 Sep 2011 13:09 |
| Last Modified: | 15 Jun 2023 23:36 |
| URI: | https://ueaeprints.uea.ac.uk/id/eprint/34898 |
| DOI: | 10.1007/s12190-011-0506-z |
Actions (login required)
 |
View Item |