Inferring Evolutionary History From DNA Sequences

DOI10.1137/S0097539791222171zbMath0829.92014MaRDI QIDQ4305354

Sampath Kannan, Tandy J. Warnow

Publication date: 17 January 1996

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

zbMATH Keywords

algorithmDNA sequencesevolutionary treesmolecular biologycharacter compatibility problemconstruction of phylogenetic treesquaternary characters

Mathematics Subject Classification ID

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

Related Items (16)

Sublinear approximate string matching and biological applications ⋮ The Birth and Early Years of Parameterized Complexity ⋮ A Basic Parameterized Complexity Primer ⋮ Efficient approximation of convex recolorings ⋮ On the Generalised Character Compatibility Problem for Non-branching Character Trees ⋮ A simple linear time algorithm for triangulating three-colored graphs ⋮ A simple characterization of the minimal obstruction sets for three-state perfect phylogenies ⋮ Recovering trees from well-separated multi-state characters. ⋮ Improved approximation algorithm for convex recoloring of trees ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Convex recolorings of strings and trees: Definitions, hardness results and algorithms ⋮ Minimizing phylogenetic number to find good evolutionary trees ⋮ Two strikes against perfect phylogeny ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs ⋮ Listing all potential maximal cliques of a graph

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