Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

Given a graph with colored vertices, the chromatic chordal completion problem asks whether the graph can be triangulated without introducing edges between vertices of the same color. This problem is equivalent to a fundamental problem in computational biology of determining whether a set of sequences can be derived in a perfect phylogeny (a tree representing evolutionary relationships which satisfies convexity constraints). For binary input, the connection between these two problems gives a concise necessary and sufficient condition for the existence of a perfect phylogeny, known as the four gamete test. In this talk, we extend this test to a necessary and sufficient condition for the existence of a perfect phylogeny on trinary input. This gives an algorithm which either constructs a perfect phylogeny if one exists, or outputs a small obstruction set if one does not exist. In proving these results, we establish fundamental structural features of the perfect phylogeny problem on three state characters.

Joint work with Dan Gusfield and Srinath Sridhar.