On the complexity of computing evolutionary trees

DOI10.1007/BFB0045080MaRDI QIDQ4364583zbMATH OpenFDO

Authors Jesper Jansson, Anna Östlin, Leszek Gąsieniec, Andrzej Lingas

Publication date 15 December 1997

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0045080

zbMATH Keywords

maximum homeomorphic agreement subtree problemmaximum inferred consensus tree problemtree optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational methods for problems pertaining to biology (92-08) Problems related to evolution (92D15)

Recommendations

• On the complexity of constructing evolutionary trees
• On the complexity of comparing evolutionary trees
• scientific article; zbMATH DE number 1303534

Cited in

(32)

• Approximation algorithms for constrained generalized tree alignment problem
• Testing the theory of evolution: A novel application of combinatorial optimization
• Computational complexity of inferring phylogenies from dissimilarity matrices
• The complexity of reconstructing trees from qualitative characters and subtrees
• Fourier calculus on evolutionary trees
• On the complexity of constructing evolutionary trees
• Constructing the maximum consensus tree from rooted Triples
• Evolutionary trees: An integer multicommodity max-flow -- min-cut theorem
• A robust model for finding optimal evolutionary tree
• Finding a maximum compatible tree is NP-hard for sequences and trees
• Encoding and constructing 1-nested phylogenetic networks with trinets
• Is the protein model assignment problem under linked branch lengths NP-hard?
• Approximating the maximum isomorphic agreement subtree is hard
• Evolutionary trees can be learned in polynomial time in the two-state general Markov model
• Aligning sequences via an evolutionary tree: complexity and approximation
• Finding a maximum likelihood tree is hard
• Efficiently Calculating Evolutionary Tree Measures Using SAT
• \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1303534 (Why is no real title available?)
• scientific article; zbMATH DE number 1305446 (Why is no real title available?)
• scientific article; zbMATH DE number 2079368 (Why is no real title available?)
• scientific article; zbMATH DE number 1754590 (Why is no real title available?)
• Selecting the branches for an evolutionary tree.
• Computing a consensus of multilabeled trees
• Theoretical Computer Science
• On contract-and-refine transformations between phylogenetic trees
• On the complexity of comparing evolutionary trees
• Heuristic algorithms in computational molecular biology
• Inferring DAGs and phylogenetic networks from least common ancestors
• A constructive algorithm for realizing a distance matrix
• Computing phylogenetic roots with bounded degrees and errors is NP-complete

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4364583)