Results 1  10
of
11
Fixedparameter algorithms for maximum agreement forests
 SIAM Journal on Computing
"... Abstract. We present new and improved fixedparameter algorithms for computing maximum agreement forests (MAFs) of pairs of rooted binary phylogenetic trees. The size of such a forest for two trees corresponds to their subtree pruneandregraft distance and, if the agreement forest is acyclic, to th ..."
Abstract

Cited by 9 (3 self)
 Add to MetaCart
(Show Context)
Abstract. We present new and improved fixedparameter algorithms for computing maximum agreement forests (MAFs) of pairs of rooted binary phylogenetic trees. The size of such a forest for two trees corresponds to their subtree pruneandregraft distance and, if the agreement forest is acyclic, to their hybridization number. These distance measures are essential tools for understanding reticulate evolution. Our algorithm for computing maximum acyclic agreement forests is the first depthbounded search algorithm for this problem. Our algorithms substantially outperform the best previous algorithms for these problems. Key words. fixedparameter tractability, phylogenetics, subtree pruneandregraft distance, lateral gene transfer, hybridization, agreement forest.
A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees
, 2012
"... ..."
A first step towards computing all hybridization networks for two rooted binary phylogenetic trees
"... ..."
Approximation algorithms for nonbinary agreement forests
, 2012
"... Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest problem (MAF) asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest problem (MAAF) has the additional restrictio ..."
Abstract

Cited by 3 (3 self)
 Add to MetaCart
(Show Context)
Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest problem (MAF) asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest problem (MAAF) has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of MAF has a polynomialtime 4approximation and a fixedparameter tractable (exact) algorithm that runs in O(4kpoly(n)) time, where n = X and k is the number of components of the agreement forest minus one. Moreover, we show that a capproximation algorithm for nonbinary MAF and a dapproximation algorithm for the classical problem Directed Feedback Vertex Set (DFVS) can be combined to yield a d(c + 3)approximation for nonbinary MAAF. The algorithms for MAF have been implemented and made publicly available.
A quadratic kernel for computing the hybridization number of multiple trees
, 2013
"... It has recently been shown that the NPhard problem of calculating the minimum number of hybridization events that is needed to explain a set of rooted binary phylogenetic trees by means of a hybridization network is fixedparameter tractable if an instance of the problem consists of precisely two s ..."
Abstract

Cited by 3 (2 self)
 Add to MetaCart
It has recently been shown that the NPhard problem of calculating the minimum number of hybridization events that is needed to explain a set of rooted binary phylogenetic trees by means of a hybridization network is fixedparameter tractable if an instance of the problem consists of precisely two such trees. In this paper, we show that this problem remains fixedparameter tractable for an arbitrarily large set of rooted binary phylogenetic trees. In particular, we present a quadratic kernel.
Hybridization Number on Three Trees
, 2014
"... Phylogenetic networks are leaflabelled directed acyclic graphs that are used to describe nontreelike evolutionary histories and are thus a generalization of phylogenetic trees. The hybridization number of a phylogenetic network is the sum of all indegrees minus the number of nodes plus one. The Hy ..."
Abstract
 Add to MetaCart
Phylogenetic networks are leaflabelled directed acyclic graphs that are used to describe nontreelike evolutionary histories and are thus a generalization of phylogenetic trees. The hybridization number of a phylogenetic network is the sum of all indegrees minus the number of nodes plus one. The Hybridization Number problem takes as input a collection of phylogenetic trees and asks to construct a phylogenetic network that contains an embedding of each of the input trees and has a smallest possible hybridization number. We present an algorithm for the Hybridization Number problem on three binary phylogenetic trees on n leaves, which runs in time O(ckpoly(n)), with k the hybridization number of an optimal network and c some positive constant. For the case of two trees, an algorithm with running time O(3.18kn) was proposed before whereas an algorithm with running time O(ckpoly(n)) for more than two trees had prior to this article remained elusive. The algorithm for two trees uses the close connection to acyclic agreement forests to achieve a linear exponent in the running time, while previous algorithms for more than two trees (explicitly or implicitly) relied on a brute force search through all possible underlying network topologies, leading to running times that are not O(ckpoly(n)), for any c. The connection to acyclic agreement forests is much weaker for