×

zbMATH — the first resource for mathematics

Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees. (English) Zbl 1303.68154
Summary: We study parameterized algorithms and approximation algorithms for the maximum agreement forest problem, which, for two given leaf-labeled trees, is to find a maximum forest that is a subgraph of both trees. The problem was motivated by research in phylogenetics. For parameterized algorithms, while the problem is known to be fixed-parameter tractable for binary trees, it was an open problem whether the problem is still fixed-parameter tractable for general trees. We resolve this open problem by developing an \(O(3^k n)\)-time parameterized algorithm for general trees. Our techniques on tree structures also lead to a polynomial-time approximation algorithm of ratio 3 for the problem, giving the first constant-ratio approximation algorithm for general trees.

MSC:
68W25 Approximation algorithms
92D15 Problems related to evolution
Software:
rSPR
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allen, B. L.; Steel, M., Subtree transfer operations and their induced metrics on evolutionary trees, Ann. Comb., 5, 1, 1-15, (2001) · Zbl 0978.05023
[2] Amir, A.; Keselman, D., Maximum agreement subtree in a set of evolutionary trees: metrics and efficient algorithms, SIAM J. Comput., 26, 6, 1656-1669, (1997) · Zbl 0885.68071
[3] Bapteste, E.; O’Malley, M. A.; Beiko, R. G.; Ereshefsky, M.; Gogarten, J. P.; Franklin-Hall, L.; Lapointe, F.-J.; Dupre, J.; Dagan, T.; Boucher, Y.; Martin, W., Prokaryotic evolution and the tree of life are two different things, Biol. Direct, 4, 34, (2009)
[4] Bonet, M. L.; John, K. St.; Mahindru, R.; Amenta, N., Approximating subtree distances between phylogenies, J. Comput. Biol., 13, 8, 1419-1434, (2006)
[5] Bordewich, M.; McCartin, C.; Semple, C., A 3-approximation algorithm for the subtree distance between phylogenies, J. Discrete Algorithms, 6, 3, 458-471, (2008) · Zbl 1171.05317
[6] Bordewich, M.; Semple, C., On the computational complexity of the rooted subtree prune and regraft distance, Ann. Comb., 8, 4, 409-423, (2005) · Zbl 1059.05035
[7] Chataigner, F., Approximating the maximum agreement forest on k trees, Inform. Process. Lett., 93, 5, 239-244, (2005) · Zbl 1173.68601
[8] DasGupta, B.; He, X.; Jiang, T.; Li, M.; Tromp, J., On the linear-cost subtree-transfer distance between phylogenetic trees, Algorithmica, 25, 2-3, 176-195, (1999) · Zbl 0952.68113
[9] Downey, R. G.; Fellows, M. R., Parameterized complexity, (1999), Springer New York · Zbl 0914.68076
[10] Farach, M.; Thorup, M., Fast comparison of evolutionary trees, (SODA, (1994)), 481-488 · Zbl 0869.92013
[11] Hallett, M.; McCartin, C., A faster FPT algorithm for the maximum agreement forest problem, Theory Comput. Syst., 41, 3, 539-550, (2007) · Zbl 1148.68049
[12] Hein, J.; Jiang, T.; Wang, L.; Zhang, K., On the complexity of comparing evolutionary trees, Discrete Appl. Math., 71, 1-3, 153-169, (1996) · Zbl 0876.92020
[13] Hon, W.-K.; Lam, T.-W., Approximating the nearest neighbor interchange distance for evolutionary trees with non-uniform degrees, (COCOON, (1999)), 61-70
[14] Kliman, R. M.; Andolfatto, P.; Coyne, J. A.; Depaulis, F.; Kreitman, M.; Berry, A. J.; McCarter, J.; Wakeley, J.; Hey, J., The population genetics of the origin and divergence of the drosophila simulans complex species, Genetics, 156, 1913-1931, (2000)
[15] Lin, G. N.; Zhang, C.; Xu, D., Polytomy identification in microbial phylogenetic reconstruction, BMC Syst. Biol., 5, Suppl 3, S2, (2011)
[16] Linz, S.; Semple, C., Hybridization in nonbinary trees, IEEE/ACM Trans. Comput. Biol. Bioinf., 6, 30-45, (2009)
[17] Rodrigues, E. M.; Sagot, M. F.; Wakabayashi, Y., Some approximation results for the maximum agreement forest problem, (RANDOM-APPROX, (2001)), 159-169 · Zbl 1001.92038
[18] Rodrigues, E. M.; Sagot, M. F.; Wakabayashi, Y., The maximum agreement forest problem: approximation algorithms and computational experiments, Theoret. Comput. Sci., 374, 1-3, 91-110, (2007) · Zbl 1164.68039
[19] Wheeler, D. L.; Chappey, C.; Lash, A. E.; Leipe, D. D.; Madden, T. L.; Schuler, G. D.; Tatusova, T. A.; Rapp, B. A., Database resources of the national center for biotechnology information, Nucleic Acids Res., 28, 10-14, (2000)
[20] Whidden, C.; Beiko, R. G.; Zeh, N., Fixed-parameter algorithms for maximum agreement forests, SIAM J. Comput., 42, 4, 1431-1466, (2013) · Zbl 1311.68079
[21] Whidden, C.; Zeh, N., A unifying view on approximation and FPT of agreement forests, (WABI, (2009)), 390-402
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.