Optimal algorithms for computing edge weights in planar split networks

V Moulton, A Spillner

Research output: Contribution to journalArticle

2 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)1-13
Number of pages13
JournalJournal of Applied Mathematics and Computing
Volume39
Issue number1-2
DOIs
Publication statusPublished - 2012

Cite this