2013/05/07 by Gysel, Rob
#Combinatorics (math.CO) #Computational Engineering #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #FOS: Mathematics #Finance #Quantitative Methods (q-bio.QM) #and Science (cs.CE)
paper · doi:10.48550/arxiv.1305.1375
The perfect phylogeny problem is a classic problem in computational biology, where we seek an unrooted phylogeny that is compatible with a set of qualitative characters. Such a tree exists precisely when an intersection graph associated with the character set, called the partition intersection graph, can be triangulated using a restricted set of fill edges. Semple and Steel used the partition intersection graph to characterize when a character set has a unique perfect phylogeny. Bordewich, Huber, and Semple showed how to use the partition intersection graph to find a maximum compatible set of characters. In this paper, we build on these results, characterizing when a unique perfect phylogeny exists for a subset of partial characters. Our characterization is stated in terms of minimal triangulations of the partition intersection graph that are uniquely representable, also known as ur-chordal graphs. Our characterization is motivated by the structure of ur-chordal graphs, and the fact that the block structure of minimal triangulations is mirrored in the graph that has been triangulated.