Approximation Algorithms for Nonbinary Agreement Forests

L.J.J. van Iersel, S. Kelk, N. Lekic, L. Stougie

Research output: Scientific - peer-reviewArticle

Abstract

Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem 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 (maaf) problem 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 polynomial-time 4-approximation and a fixedparameter tractable (exact) algorithm that runs in O(4
Original languageEnglish
Pages (from-to)49-66
JournalSIAM Journal on Discrete Mathematics
Volume28
Issue number1
DOIs
StatePublished - 2014

Cite this

van Iersel, L.J.J.; Kelk, S.; Lekic, N.; Stougie, L. / Approximation Algorithms for Nonbinary Agreement Forests.

In: SIAM Journal on Discrete Mathematics, Vol. 28, No. 1, 2014, p. 49-66.

Research output: Scientific - peer-reviewArticle

@article{cece42f397cc4e009da9df5b51a341d6,
title = "Approximation Algorithms for Nonbinary Agreement Forests",
abstract = "Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem 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 (maaf) problem 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 polynomial-time 4-approximation and a fixedparameter tractable (exact) algorithm that runs in O(4",
author = "{van Iersel}, L.J.J. and S. Kelk and N. Lekic and L. Stougie",
year = "2014",
doi = "10.1137/120903567",
volume = "28",
pages = "49--66",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "1",

}

Approximation Algorithms for Nonbinary Agreement Forests. / van Iersel, L.J.J.; Kelk, S.; Lekic, N.; Stougie, L.

In: SIAM Journal on Discrete Mathematics, Vol. 28, No. 1, 2014, p. 49-66.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - Approximation Algorithms for Nonbinary Agreement Forests

AU - van Iersel,L.J.J.

AU - Kelk,S.

AU - Lekic,N.

AU - Stougie,L.

PY - 2014

Y1 - 2014

N2 - Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem 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 (maaf) problem 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 polynomial-time 4-approximation and a fixedparameter tractable (exact) algorithm that runs in O(4

AB - Given two rooted phylogenetic trees on the same set of taxa X, the Maximum Agreement Forest (maf) problem 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 (maaf) problem 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 polynomial-time 4-approximation and a fixedparameter tractable (exact) algorithm that runs in O(4

U2 - 10.1137/120903567

DO - 10.1137/120903567

M3 - Article

VL - 28

SP - 49

EP - 66

JO - SIAM Journal on Discrete Mathematics

T2 - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 1

ER -