Which phylogenetic networks are merely trees with additional arcs?

2015/02/25 by Francis, Andrew R., Steel, Mike · 2 citations
#Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Populations and Evolution (q-bio.PE)

paper · doi:10.48550/arxiv.1502.07045

Abstract

A binary phylogenetic network may or may not be obtainable from a tree by the addition of directed edges (arcs) between tree arcs. Here, we establish a precise and easily tested criterion (based on `2-SAT') that efficiently determines whether or not any given network can be realized in this way. Moreover, the proof provides a polynomial-time algorithm for finding one or more trees (when they exist) on which the network can be based. A number of interesting consequences are presented as corollaries; these lead to some further relevant questions and observations, which we outline in the conclusion.

Cited by

• Colorings of unrooted tree-based networks and related graphs
• Characterizing semi-directed phylogenetic networks and their multi-rootable variants

Related

• Tree-based networks: characterisations, metrics, and support trees
• Is this network proper forest-based?
• Path Partitions of Phylogenetic Networks
• Which Phylogenetic Networks are Level-k Networks with Additional Arcs? Structure and Algorithms
• Unrooted non-binary tree-based phylogenetic networks