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

AF：小：系统发育中的组合算法和结构：弦图方法

• 批准号: 1017580
• 负责人: Daniel Gusfield
• 金额: $ 36.21万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017580&HistoricalAwards=false
• 关键词: AF; Small; Combinatorial; Algorithms; Structure

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.

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