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

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