Optimal algorithms for computing edge weights in planar split networks

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

Full text not available from this repository. (Request a copy)

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 View Item