Inferring Evolutionary History From DNA Sequences

DOI10.1137/S0097539791222171MaRDI QIDQ4305354zbMATH OpenFDO

Authors Sampath Kannan, Tandy J. Warnow

Publication date 17 January 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539791222171

zbMATH Keywords

algorithmcharacter compatibility problemconstruction of phylogenetic treesDNA sequencesevolutionary treesmolecular biologyquaternary characters

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational methods for problems pertaining to biology (92-08) Biochemistry, molecular biology (92C40) Problems related to evolution (92D15) Protein sequences, DNA sequences (92D20)

Recommendations

• Tree Compatibility and Inferring Evolutionary History
• scientific article; zbMATH DE number 437563
• Computational complexity of inferring phylogenies from dissimilarity matrices

Cited in

(25)

• Phylogenetic inference from binary sequences reduced by primary DNA sequences
• The computational complexity of inferring rooted phylogenies by parsimony
• Computational complexity of inferring phylogenies from dissimilarity matrices
• Reconstructing a history of recombinations from a set of sequences
• Sublinear approximate string matching and biological applications
• Recovering trees from well-separated multi-state characters.
• The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
• Listing all potential maximal cliques of a graph
• Efficient approximation of convex recolorings
• The birth and early years of parameterized complexity
• A basic parameterized complexity primer
• scientific article; zbMATH DE number 437563 (Why is no real title available?)
• Tree Compatibility and Inferring Evolutionary History
• Constructing Computer Virus Phylogenies
• A simple characterization of the minimal obstruction sets for three-state perfect phylogenies
• Solving graph problems via potential maximal cliques: an experimental evaluation of the Bouchitté-Todinca algorithm
• A simple linear time algorithm for triangulating three-colored graphs
• Two strikes against perfect phylogeny
• On the Generalised Character Compatibility Problem for Non-branching Character Trees
• Reconstructing Chromosomal Evolution
• Efficient algorithms for inferring evolutionary trees
• Minimizing phylogenetic number to find good evolutionary trees
• Reconstructing ultrametric trees from noisy experiments
• Improved approximation algorithm for convex recoloring of trees
• Convex recolorings of strings and trees: Definitions, hardness results and algorithms

This page was built for publication: Inferring Evolutionary History From DNA Sequences

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