On the complexity of comparing evolutionary trees

DOI10.1016/S0166-218X(96)00062-5zbMath0876.92020WikidataQ60163444 ScholiaQ60163444MaRDI QIDQ5961623

Jotun J. Hein, Lusheng Wang, Zhang, Kaizhong, Tao Jiang

Publication date: 25 November 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

computational complexityNP-hardrecombinationcompatibilitycomparison of evolutionary treespolynomial-time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problems related to evolution (92D15) Applications of graph theory (05C90)

Related Items (46)

Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees ⋮ APPROXIMATING THE MAXIMUM ISOMORPHIC AGREEMENT SUBTREE IS HARD ⋮ Approximating the maximum agreement forest on \(k\) trees ⋮ A social choice approach to ordinal group activity selection ⋮ Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees ⋮ Bounding the number of hybridisation events for a consistent evolutionary history ⋮ A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ Analyzing and reconstructing reticulation networks under timing constraints ⋮ Computing the minimum number of hybridization events for a consistent evolutionary history ⋮ Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks ⋮ Exploring spaces of semi-directed level-1 networks ⋮ Extremal distances for subtree transfer operations in binary trees ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ Breaks, cuts, and patterns ⋮ Gene tree reconciliation including transfers with replacement is NP-hard and FPT ⋮ Convex Characters, Algorithms, and Matchings ⋮ Improved algorithms for maximum agreement and compatible supertrees ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ New results for the longest haplotype reconstruction problem ⋮ New reduction rules for the tree bisection and reconnection distance ⋮ Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees ⋮ Identifying approximately common substructures in trees based on a restricted edit distance ⋮ Maximum agreement and compatible supertrees ⋮ On the fixed parameter tractability of agreement-based phylogenetic distances ⋮ SUBTREE TRANSFER DISTANCE FOR DEGREE-D PHYLOGENIES ⋮ Stable and Pareto optimal group activity selection from ordinal preferences ⋮ Complexity issues in vertex-colored graph pattern matching ⋮ Computing nearest neighbour interchange distances between ranked phylogenetic trees ⋮ Computing the maximum agreement of phylogenetic networks ⋮ Approximating maximum agreement forest on multiple binary trees ⋮ Computing the rooted triplet distance between phylogenetic networks ⋮ Algorithms for parameterized maximum agreement forest problem on multiple trees ⋮ An Improved Approximation Algorithm for rSPR Distance ⋮ A 3-approximation algorithm for the subtree distance between phylogenies ⋮ Maximum Motif Problem in Vertex-Colored Graphs ⋮ Efficiently Calculating Evolutionary Tree Measures Using SAT ⋮ The maximum agreement forest problem: Approximation algorithms and computational experiments ⋮ Better Practical Algorithms for rSPR Distance and Hybridization Number ⋮ On the approximability of the maximum agreement subtree and maximum compatible tree problems ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ Fixed topology alignment with recombination ⋮ Faster exact computation of rSPR distance ⋮ Computing similarity between RNA structures ⋮ A New Algorithm for Inferring Hybridization Events Based on the Detection of Horizontal Gene Transfers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing evolution of sequences subject to recombination using parsimony
• Alignment of trees -- an alternative to tree edit
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Optimization, approximation, and complexity classes
• A mathematical foundation for the analysis of cladistic character compatibility
• Kaikoura tree theorems: Computing the maximum agreement subtree
• Finding a maximum compatible tree is NP-hard for sequences and trees
• Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
• Tree Compatibility and Inferring Evolutionary History
• Sparse Dynamic Programming for Evolutionary-Tree Comparison
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Efficient algorithms for inferring evolutionary trees

This page was built for publication: On the complexity of comparing evolutionary trees