Collaborative Research: Principal Component Analysis over Tree Spaces and Its Applications to Phylogenomics

系统基因组学是一个相对较新的领域，它试图在全基因组的尺度上理解生物体之间的进化关系。进化生物学的核心问题之一是更好地理解生物之间的关系，通常以系统发育树的形式进行总结。通常用于发展这些树的方法往往最适合近亲生物，当序列相对较短时；例如，将单个基因的DNA序列应用于一组哺乳动物。当比较亲缘关系较远的生物体或来自大部分基因组的数据时，现有的技术可能会失效。由于现代技术可以快速而廉价地产生基因组规模的序列数据，因此迫切需要为这种大规模高维数据量身定制更好的分析工具。在大规模数据中寻找一般模式的最流行的统计方法，如主成分分析（PCA），假设数据所在的空间是平坦的，就像欧几里得的平面几何一样。然而，可能的系统发育树的空间具有明显的非欧几里得几何形状，其表面更类似于用橡胶片制成的折纸图形。该项目的目标是开发替代类型的主成分，以及计算它们的方法，这些方法考虑到系统发育树数学空间的不寻常结构特征。PCA是一种统计方法，它将高维欧几里得空间中的数据点置于较低维平面上，从而最小化数据集中每个点与其在平面上的正交投影之间的平方和。它已被用于统计分析的高维数据点聚类，它是在欧几里德向量空间中进行降维的最简单和最健壮的方法之一。然而，它假定欧几里得向量空间的性质。在一组固定的物种上所有可能的系统发生的空间不能形成欧几里得向量空间，因此PCA必须在树空间的几何结构中重新表述。受T. Nye在2011年关于构建第一主成分或主测地线的工作的启发，pi提出了两个不同度量下的几何对象，它们代表k阶主成分：(1)在Billera-Holmes-Vogtman （BHV）度量下，树空间中k+1个点的加权Frechet平均值的轨迹，其权重在相关的概率单纯形上变化；(2)通过热带几何中的热带度量（称为max-plus代数），树空间中k+1个点的热带凸包。本课题的第一个目的是证明树空间上BHV度量和热带度量下主成分分析的性质。然后，第二个目标是开发有效的算法来计算/近似它们。将进行仿真研究以证明这些算法的良好性能。然后，pi将把这些算法应用于经验数据集，例如顶复合体（包括疟疾在内的寄生肺泡动物门）和非洲腔棘鱼基因组，以及纽约流感的血凝素序列。更广泛的影响将包括建议本科生实现软件产品的算法和用户界面。这些研究经验将补充作为当前夏威夷EPSCoR项目组成部分正在开发的新数据科学项目。夏季项目的一部分工作还将用于与附近高中的科学和工程项目合作开发数据分析课程模块。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Phylogenomics is a relatively new field that seeks to understand evolutionary relationships between organisms at the scale of the whole genome. One of the central questions in evolutionary biology is a better understanding of the relationships between organisms, usually summarized in the form of a phylogenetic tree. The methods in common use for developing these trees tend to work best for closely related organisms, and when the sequences are relatively short; for example, the DNA sequence for a single gene applied to a collection of mammals. When comparing more distantly related organisms, or data from large portions of the genome, current techniques can break down. Since modern technology can quickly and cheaply produce genome-scale sequence data, there is a pressing need for better analytical tools tailored to this large-scale high-dimensional data. The most popular statistical methods for finding general patterns in large-scale data, such as Principal Component Analysis (PCA), make the assumption that the space where the data lies is flat, like the plane geometry of Euclid. However, the space of possible phylogenetic trees has a decidedly non-Euclidean geometry, with a surface more akin to an origami figure made with a sheet of rubber. The goal of this project is to develop alternative types of principal components, and methods to calculate them, which take into account the unusual structural features of the mathematical space of phylogenetic trees.PCA is a statistical method that takes data points in a high dimensional Euclidean space into a lower dimensional plane which minimizes the sum of squares between each point in the data set and their orthogonal projection onto the plane. It has been used for clustering high dimensional data points for statistical analysis and it is one of the simplest and most robust ways of doing dimensionality reduction in a Euclidean vector space. However, it assumes the properties of a Euclidean vector space. The space of all possible phylogenies on a fixed set of species does not form a Euclidean vector space, so PCA must be reformulated in the geometry of a tree-space. Motivated by the previous work by T. Nye in 2011 on construction of the first principal component, or principal geodesic, the PIs propose two geometric objects under different metrics which represent a k-th order principal component: (1) the locus of the weighted Frechet mean of k+1 points in a tree-space, where the weights vary over the associated probability simplex, under the Billera-Holmes-Vogtman (BHV) metric and (2) the tropical convex hull of k+1 points in a tree-space via the tropical metric in tropical geometry known as the max-plus algebra. The first aim of this project is to prove properties of the PCA under the BHV metric and the PCA under the tropical metric over tree-spaces. Then, the second aim is to develop efficient algorithms to compute/approximate them. Simulation studies will be conducted to show these algorithms perform well. Then the PIs will apply these algorithms to empirical data sets, such as Apicomplexa, a phylum of parasitic alveolates including malaria, and African coelacanth genomes, and sequences of hemagglutinin for influenza from New York. The broader impact will include advising undergraduate students for the implementation of the algorithms and user interfaces of the software products. These research experiences will complement a new Data Science program being developed as a component of the current Hawaii EPSCoR program. A portion of the summer effort will also be used to collaborate with nearby high school science and engineering programs in the development of data analysis lesson modules.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.