Related Experiment Video
Updated: Jun 4, 2026

A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
Extensions and improvements to the chordal graph approach to the multistate perfect phylogeny problem
1Graduate Group, Department of Computer Science, University of California, 2063 Kemper Hall, 1 Shields Avenue, Davis, CA 95616, USA. rsgysel@ucdavis.edu
Abstract:
The multistate perfect phylogeny problem is a classic problem in computational biology. When no perfect phylogeny exists, it is of interest to find a set of characters to remove in order to obtain a perfect phylogeny in the remaining data. This is known as the character removal problem. We show how to use chordal graphs and triangulations to solve the character removal problem for an arbitrary number of states, which was previously unsolved. We outline a preprocessing technique that speeds up the computation of the minimal separators of a graph. Minimal separators are used in our solution to the missing data character removal problem and to Gusfield's solution of the perfect phylogeny problem with missing data.
Related Concept Videos
Phylogeny
Evolutionary Relationships through Genome Comparisons
Phylogenetic Trees
Phylogenetic Trees
Microbial Phylogeny
Synteny and Evolution
Around 80 million years ago, the human and mice lineages diverged from the common ancestor. During the course of evolution, the ancestral chromosome underwent...

