2012 | OriginalPaper | Chapter
Reducing Problems in Unrooted Tree Compatibility to Restricted Triangulations of Intersection Graphs
Authors : Rob Gysel, Kristian Stevens, Dan Gusfield
Published in: Algorithms in Bioinformatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The compatibility problem is the problem of determining if a set of unrooted trees are compatible, i.e. if there is a supertree that represents all of the trees in the set. This fundamental problem in phylogenetics is NP-complete but fixed-parameter tractable in the number of trees. Recently, Vakati and Fernández-Baca showed how to efficiently reduce the compatibility problem to determining if a specific type of constrained triangulation exists for a non-chordal graph derived from the input trees, mirroring a classic result by Buneman for the closely related Perfect-Phylogeny problem. In this paper, we show a different way of efficiently reducing the compatibility problem to that of determining if another type of constrained triangulation exists for a new non-chordal intersection graph. In addition to its conceptual contribution, such reductions are desirable because of the extensive and continuing literature on graph triangulations, which has been exploited to create algorithms that are efficient in practice for a variety of Perfect-Phylogeny problems. Our reduction allows us to frame the compatibility problem as a minimal triangulation problem (in particular, as a chordal graph sandwich problem) and to frame a maximization variant of the compatibility problem as a minimal triangulation problem.