Locating a tree in a phylogenetic network

Type of content
Discussion / Working Papers
Publisher's DOI/URI
Thesis discipline
Degree name
Publisher
University of Canterbury
Journal Title
Journal ISSN
Volume Title
Language
Date
2010
Authors
Iersel, Leo van
Semple, Charles
Steel, M. A.
Abstract

Phylogenetic trees and networks are leaf-labelled graphs that are used to describe evolutionary histories of species. The TREE CONTAINMENT problem asks whether a given phylogenetic tree is embedded in a given phylogenetic network. Given a phylogenetic network and a cluster of species, the CLUSTER CONTAINMENT problem asks whether the given cluster is a cluster of some phylogenetic tree embedded in the network. Both problems are known to be NP-complete in general. In this article, we consider the restriction of these problems to several well-studied classes of phylogenetic networks. We show that TREE CONTAINMENT is polynomial-time solvable for normal networks, for binary tree-child networks, and for level-k networks. On the other hand, we show that, even for tree-sibling, time-consistent, regular networks, both TREE CONTAINMENT and CLUSTER CONTAINMENT remain NP-complete.

Description
Citation
Keywords
algorithms, computational complexity, phylogenetic trees, phylogenetic networks
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Fields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics
Rights
All Rights Reserved