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

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

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.