Combinatorial Algorithms and Structure in Phylogeny: A Chordal Graph Approach NSF:CCF 1017580 PI: Dan Gusfield, UC Davis The evolutionary history of a set of organisms is described by a tree called an evolutionary, or phylogenetic tree. Such trees display fundamental, evolutionary relationships between organisms, and are also used to display information and relationships outside of the field of evolution. as well. The Multi-State Perfect Phylogeny (MPP) problem is a computational and mathematical problem arising from the construction of such evolutionary trees. The MPP problem addresses the need to represent rich, multi-state properties of data in phylogenetic trees, rather than properties that only have two states (for example, present or absent). The MPP problem was initially defined in a 1974 paper that established a deep mathematical relationship between it and a subfield of the mathematical field called ``graph theory''. Graph theory is the study of collections of points and lines; the subfield of graph theory that is related to the MPP problem is called Chordal Graph Theory. Although the connection between the MPP problem and chordal graph theory has been known since 1974, that connection has not been widely used in the development of algorithms for the computational solution of the MPP problem and extensions of the MPP problem. This project focuses on exploiting and extending recent advances in chordal graph theory to develop practical computational methods to solve Multi-State Perfect Phylogeny problems and extensions of those problems. Building on recent work in the literature on chordal graph theory, the project will obtain new graph theoretic results for the MPP problem, and will use those mathematical results to obtain practical algorithms for MPP problems. This is a rare situation where a deep, elegant mathematical and algorithmic framework is available and appropriate for the study of an applied algorithmic problem. The project combines research in computer science algorithms, graph theory, and discrete optimization theory to produce effective means for reconstructing evolutionary histories, and for understanding the underlying mathematical structure of such histories. This theoretical work will be accompanied by the development of a suite of software tools that will be made available for other researchers interested in studying chordal graphs, MPP problems, treewidth problems, and related problems.
