AF: Small: Algorithms in Phylogenetics

系统发生树，也被称为系统发生，代表了物种集合的进化史。建造这样的树是为了了解生命的起源。系统发生学有几个实际用途。例如，通过比较和利用进化相关物种之间的信息，它们为生物学家提供了一种预测基因功能的工具。它们还有助于追踪病毒或癌细胞等快速发展的生物体的变化。从基因数据构建系统发育树提出了主要的计算问题。每个已知的任务公式都会导致一个棘手的（NP-hard）问题。此外，数据是稀缺的：不是所有物种的每个基因都被测序，也不是每个物种都有相同的一组基因。因此，为了建立全面的系统发育，我们必须将来自不同基因的信息拼凑在一起。更复杂的是，基因进化并不总是符合物种形成的历史。事实上，由于基因的重复和丢失，以及基因的水平转移，基因系统发育相互冲突的情况并不少见。提出的研究解决了系统发育中由于数据稀缺和冲突而产生的数学和算法问题。在相互关联的主题中，我们将探索的是冲突的检测，树木之间不相似度量的属性，以及树木集合中共同模式的识别。我们的一部分工作将集中在超树问题上，其目标是将部分重叠的物种集合的树集合合并成一个单一的系统发育-一个超树-用于组合的物种集合。我们将研究超树方法能满足和不能满足的性质，并对重要类超树问题的可解实例进行数学表征。我们将使用后者来识别参数化，在这些参数化下，某些问题变得易于处理。我们在系统发育数据库中挖掘共同模式的方法将使生物学家能够识别物种之间有充分支持的进化关系，并发现“流氓分类群”；即，其存在从根本上改变系统发育分析结果的物种。我们还将研究多标记树（每个物种可以出现多次的树）的超树构建和数据挖掘，这些树现在在系统发育数据库中很常见。

Phylogenetic trees, also known as phylogenies, represent the evolutionary history of sets of species. The construction of such trees is an attempt to understand the origin of life. Phylogenies have several practical uses. For instance, they offer biologists a tool to predict gene function, by comparing and leveraging information among species related by evolution. They also help to track changes in rapidly developing organisms such as viruses or cancer cells. Building phylogenetic trees from gene data poses major computational problems. Every known formulation of the task leads to an intractable (NP-hard) problem. Further, data is scarce: not every gene has been sequenced for all species, and not every species has the same set of genes. Thus, to build comprehensive phylogenies, we must piece together information from different genes. Complicating matters even further, gene evolution does not always conform to the history of speciation. In fact, due to gene duplication and loss, and horizontal gene transfer, it is not rare for gene phylogenies to be in conflict with each other.The proposed research addresses the mathematical and algorithmic problems that arise from data scarcity and conflict in phylogenetics. Among the interrelated themes we will explore are the detection of conflict, the properties of dissimilarity measures between trees, and the identification of common patterns in collections of trees. A portion of our work will center on the supertree problem, where the goal is to amalgamate a collection of trees for partially overlapping sets of species into a single phylogeny -a supertree- for the combined set of species. We will investigate the properties a supertree method can and cannot satisfy, and develop mathematical characterizations of the solvable instances of important classes of supertree problems. We will use the latter to identify parameterizations under which certain problems become tractable. Our methods for mining phylogenetic databases for common patterns will enable biologists to identify well-supported evolutionary relationships among species and to spot "rogue taxa"; i.e., species whose presence radically alters the result of a phylogenetic analysis. We will also investigate supertree construction and data mining for multi-labeled trees (trees where each species can occur multiple times), which are now commonplace in phylogenetic databases.