A simple characterization of the minimal obstruction sets for three-state perfect phylogenies

作者：Shutters Brad^*; Fernandez Baca David

来源：Applied Mathematics Letters, 2012, 25(9): 1226-1229.

DOI：10.1016/j.aml.2012.02.060

• Computational biology
• Phylogenetics
• Perfect phylogeny

We give a characterization of the minimal obstruction sets for the existence of a perfect phylogeny for a set of three-state characters that can be inferred by testing each pair of characters. This leads to a O(m(2)n + p) time algorithm for outputting all p minimal obstruction sets for a set of m three-state characters over a set of n taxa.

• 出版日期2012-9