Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Kernelizations for the Hybridization Number Problem on Multiple Nonbinary Trees
verfasst von : Leo van Iersel, Steven Kelk
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
A well-studied problem in phylogenetics is to determine the minimum number of hybridization events necessary to explain conflicts among several evolutionary trees, e.g. from different genes. An evolutionary history with hybridization events (or, more generally, reticulations) can be described by a rooted leaf-labelled directed acyclic graph, which is called a phylogenetic network. The reticulation number of such a phylogenetic network can be defined as the sum of all indegrees minus the number of vertices plus one. The considered problem can now formally be stated as follows. Given a finite set \(X\), a collection \(\mathcal {T}\) of rooted phylogenetic trees on \(X\) and \(k\in \mathbb {N}^{+}\), the Hybridization Number problem asks if there exists a rooted phylogenetic network on \(X\) that displays all trees from \(\mathcal {T}\) and has reticulation number at most \(k\). We show that Hybridization Number admits a kernel of size \(4k(5k)^t\) if \(\mathcal {T}\) contains \(t\) (not necessarily binary) rooted phylogenetic trees. In addition, we show a slightly different kernel of size \(20k^2(\varDelta ^+-1)\) with \(\varDelta ^+\) the maximum outdegree of the input trees.