NSF Young Investigator: Computational Problems in Evolutionary Tree Construction

这项工作的主要焦点是重建进化历史的算法领域。S的一组物种的进化史是用一棵有根的树来描述的，这棵树被称为进化树(又称进化树或系统发育树)，其中叶子代表S的物种，内部节点代表共同的祖先。文献中给出了构建系统发育树的各种方法，其中大多数都是基于最优化标准。也就是说，给出了一个用来评估给定系统发育的优化标准，目标是找到相对于该标准具有最优分数的系统发育。几乎所有的优化问题都被证明是关于该准则的NP-Hard分数。尽管如此，已经开发了过多的启发式方法来构建系统发育树。标准的操作方法是使用许多不同的构建树的方法来分析数据集，并比较这些方法的结果，以选择系统发育树。这项关于构建系统树的研究工作有三个基本组成部分：(1)开发一个全面的数学框架，可以用来比较现有的方法；(2)开发有效的算法，以有意义的输出构建系统树；以及(3)将这些技术应用于生物学和语言学问题。

The main focus of this work is in the area of algorithms for reconstructing evolutionary history. The evolutionary history for a set of species S is described by a rooted tree called an evolutionary tree (also called phylogenetic tree or phylogeny) in which the leaves represent the species in S and the internal nodes represent the common ancestors. There is a wide range of methods for constructing phylogenetic trees given in the literature, and most of these are based upon optimization criteria. That is, an optimization criterion is given with which to evaluate a given phylogeny, and the objective is to find a phylogeny with an optimal score with respect to that criterion. Almost all of the optimization problems have been shown to be NP-hard score with respect to that criterion. Despite this, a plethora of heuristics have been developed for constructing phylogenetic trees. The standard modus operandi is to analyze the data set using many different methods for tree construction, and compare the outcomes of these methods in order to select a phylogenetic tree. This research effort with respect to phylogeny construction has three basic components: (1) the development of a comprehensive mathematical framework by which current methodologies can be compared; (2) the development of efficient algorithms for phylogeny construction with meaningful output; and (3) application of these techniques to problems in biology and linguistics.