Top

Journal of Combinatorial Optimization

Published in:

01-07-2016

Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees

Authors: Feng Shi, Qilong Feng, Jie You, Jianxin Wang

Published in: Journal of Combinatorial Optimization | Issue 1/2016

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Given two rooted binary phylogenetic trees with identical leaf label-set, the maximum agreement forest (MAF) problem asks for a largest common subforest of the two trees. This problem has been studied extensively in the literature, and has been known to be NP-complete and MAX SNP-hard. The previously best ratio of approximation algorithms for this problem is 3. In this paper, we make full use of the special relations among leaves in phylogenetic trees and present an approximation algorithm with ratio 2.5 for the MAF problem on two rooted binary phylogenetic trees.

previous article Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs

next article Efficient approximation algorithms for computing k disjoint constrained shortest paths

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

The definitions for the study of MAFs have been kind of confusing. If size denotes the number of edges in a forest, then for a forest, the size is equal to the number of vertices minus the order. In particular, when the number of vertices is fixed, a forest of a large size means a small order of the forest.

Allen and Steel (2001) proved that the TBR distance between two unrooted binary phylogenetic trees is equal to the order of their MAF minus 1.

Allen B, Steel M (2001) Subtree transfer operations and their induced metrics on evolutionary trees. Ann Comb 5(1):1–15MathSciNetCrossRefMATH

Baroni M, Grnewald S, Moulton V, Semple C (2005) Bounding the number of hybridisation events for a consistent evolutionary history. J Math Biol 51(2):171–182MathSciNetCrossRefMATH

Bonet M, John R, Mahindru R, Amenta N (2006) Approximating subtree distances between phylogenies. J Comput Biol 13(8):1419–1434MathSciNetCrossRef

Bordewich M, McCartin C, Semple C (2008) A 3-approximation algorithm for the subtree distance between phylogenies. J Discret Algorithms 6(3):458–471MathSciNetCrossRefMATH

Bordewich M, Semple C (2005) On the computational complexity of the rooted subtree prune and regraft distance. Ann Comb 8(4):409–423MathSciNetCrossRefMATH

Buneman P (1971) The recovery of trees from measures of dissimilarity. In: Hodson F, Kendall D, Tauta P (eds) Mathematics in the archaeological and historical sciences. Edinburgh University Press, Edinburgh, pp 387–395

Chataigner F (2005) Approximating the maximum agreement forest on \(k\) trees. Inf Process Lett 93:239–244MathSciNetCrossRefMATH

Dudas G, Bedford T, Lycett S et al (2015) Reassortment between influenza B lineages and the emergence of a coadapted PB1-PB2-HA gene complex. Mol Biol Evol 32(1):162–172CrossRef

Hein J, Jiang T, Wang L, Zhang K (1996) On the complexity of comparing evolutionary trees. Discret Appl Math 71:153–169MathSciNetCrossRefMATH

Hallett M, McCartin C (2007) A faster FPT algorithm for the maximum agreement forest problem. Theory Comput Syst 41(3):539–550MathSciNetCrossRefMATH

Lersel LV, Kelk S, Lekic N, Stougie L (2014) Approximation algorithms for nonbinary agreement forests. SIAM J Discret Math 28(1):49–66MathSciNetCrossRefMATH

Li M, Tromp J, Zhang L (1996) On the nearest neighbour interchange distance between evolutionary trees. J Theor Biol 182(4):463–467CrossRef

Robinson D, Foulds L (1981) Comparison of phylogenetic trees. Math Biosci 53(1–2):131–147MathSciNetCrossRefMATH

Rodrigues E, Sagot M, Wakabayashi Y (2007) The maximum agreement forest problem: approximation algorithms and computational experiments. Theor Comput Sci 374(1–3):91–110MathSciNetCrossRefMATH

Rodrigues M, Sagot M, Wakabayashi Y (2001) Some approxiamtion results for the maximum agreement forest problem. In: Proceedings of RANDOM 2001 and APPROX 2001, LNCS, vol 2129, pp 159–169

Swofford D, Olsen G, Waddell P, Hillis D (1996) Phylogenetic inference. In: Molecular Systematics, 2nd edn. Sinauer, Associates, pp 407–513

Shi F, Chen J, Feng Q, Wang J (2014) Approximation algorithms for maximum agreement forest on multiple trees. In: Proceedings of 20th international computing and combinatorics conference, LNCS, vol 8591, pp 381–392

Whidden C, Beiko R, Zeh N (2011) Fixed-parameter and approximation algorithms for maximum agreement forests. CoRR. abs/1108.2664

Whidden C, Beiko R, Zeh N (2013) Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees. arXiv preprint arXiv:1305.0512

Whidden C, Zeh N (2009) A unifying view on approximation and FPT of agreement forests. In: Proceedings of the 9th workshop on algorithms in bioinformatics, LNCS, vol 5724, pp 390–401

Whidden C, Beiko R, Zeh N (2013) Fixed-parameter algorithms for maximum agreement forests. SIAM J Comput 42(4):1431–1466MathSciNetCrossRefMATH

Whidden C, Zeh N, Beiko R (2014) Supertrees based on the subtree prune-and-regraft distance. Syst Biol 63(4):566–581. doi:10.1093/sysbio/syu023 CrossRef

Whidden C, Frederick A, Matsen I (2015) Quantifying MCMC exploration of phylogenetic tree space. Syst Biol. doi:10.1093/sysbio/syv006

Title: Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees
Authors: Feng Shi
Qilong Feng
Jie You
Jianxin Wang
Publication date: 01-07-2016
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2016
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9921-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2016

Dynamic matchings in left vertex weighted convex bipartite graphs

List edge and list total coloring of planar graphs with maximum degree 8

Complexity of domination, hamiltonicity and treewidth for tree convex bipartite graphs

Algorithms for the workflow satisfiability problem engineered for counting constraints

A complexity dichotomy and a new boundary class for the dominating set problem

Strong minimum energy hierarchical topology in wireless sensor networks

Premium Partner