AF: Small: Combinatorial Algorithms and Structure in Phylogeny: A Chordal Graph Approach

系统发育中的组合算法和结构：弦图方法NSF：CCF 1017580PI：Dan Gusfield，UC Davis一组生物的进化历史由一棵称为进化树或系统发育树的树来描述。这种树显示了有机体之间的基本进化关系，也被用来显示进化领域之外的信息和关系。也是。多态完美进化树(MPP)问题是在构建这种进化树的过程中产生的一个计算和数学问题。MPP问题解决了在系统发育树中表示数据的丰富、多状态属性的需求，而不是只有两种状态(例如，存在或不存在)的属性。MPP问题最初是在1974年的一篇论文中定义的，这篇论文建立了它与数学领域的一个子域--图论--之间的深刻数学关系。图论是对点和线的集合的研究；图论中与MPP问题相关的子域称为弦图理论。虽然MPP问题和弦图理论之间的联系自1974年就已为人所知，但这种联系还没有被广泛应用于MPP问题的计算解和MPP问题的扩展的算法的开发中。这个项目集中于开发和扩展弦图理论的最新进展，以开发实用的计算方法来解决多状态完美系统发生问题及其扩展。基于最近关于弦图理论的文献工作，该项目将获得MPP问题的新的图论结果，并将使用这些数学结果来获得MPP问题的实用算法。这是一种罕见的情况，在这种情况下，有一个深入、优雅的数学和算法框架可用，并且适合研究应用算法问题。该项目结合了计算机科学算法、图论和离散优化理论的研究，为重建进化历史和理解这些历史的潜在数学结构提供了有效的手段。这项理论工作将伴随着一套软件工具的开发，这些工具将提供给其他对研究弦图、MPP问题、树宽问题和相关问题感兴趣的研究人员。

Combinatorial Algorithms and Structure in Phylogeny: A Chordal Graph Approach NSF:CCF 1017580PI: 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.