Experimental and Theoretical Analyses of Tree Distance Distributions

大型数据集出现在科学和工程学科的广泛环境中。将如此庞大的数据集组织成可以有效搜索或理解的形式可能非常困难。一种常见的方法是基于“分而治之”的方法，在这种方法中，连续划分大数据集，经过一些步骤后，每个数据块中的数据量变得更加易于处理。例如，在连续将具有万亿个条目的数据集减半20次之后，每个剩余部分中将有大约一千个条目。这种连续的划分过程可以自然地由称为二叉树的分支结构表示。为了提高效率，每一步都要将每一部分大致分成两半;否则，并非所有的部分都将缩小到更易于管理的大小。树也是一种基本的结构，可以在广泛的环境中显示层次关系，从刚才描述的数据存储和搜索技术到生物学中的进化过程建模。树距离测量两棵树的不同程度，并且在评估两棵可能的树同意或不同意的程度时很重要。有许多不同的树距离，它们在它们测量的树共性的哪些方面、它们在不同应用中的重要性以及它们的计算难度方面有所不同。该项目旨在更好地了解树木上多种距离测量的分布。该项目研究用于数据和磁盘存储技术等计算环境的有序树，以及生物和其他科学研究中出现的无序树。分布的统计特性，包括平均值，方差和渐近性质，提出了困难的挑战，将接近实验和通过精确和渐近组合方法。该项目还致力于计算树距离的新方法，这些方法对系统发育应用和计算可行都很重要。对树平衡中使用的旋转操作的更好理解可能会导致用于广泛计算类别的树的改进算法，这是许多大型数据库结构的效率的基础。该项目通过了解距离的分布来了解如何缩放树木距离，使研究生物学问题的科学家更好地理解树木重建工作的结果。该项目涉及尖端研究项目的本科生研究人员，无论是在大规模计算实验的发展，并在开发这些问题的答案的理论基础。该奖项由数学科学部计算数学计划共同资助，由生物多样性和生态系统动力学计划在生物局DEB司。

Large data sets arise in a wide range of settings across scientific and engineering disciplines. Organizing such large data sets into forms where they can be effectively searched or understood can be very difficult. A common method is based upon the "divide and conquer" approach, in which successive division of large data sets leads, after some steps, to the amount of data in each piece being much more tractable. For example, after successively halving a data set with a trillion entries 20 times, there would be about a thousand entries in each remaining piece. Such successive division processes can be represented naturally by a branching structure known as a binary tree. It is important for efficiency that each step divides the pieces roughly in half; otherwise not all of the pieces will shrink to more manageable sizes. Trees also are a fundamental structure showing hierarchical relationships in a broad range of settings, from the data storage and searching technique just described to modeling evolutionary processes in biology. Tree distances measure how different two trees are and are important in assessing the degree to which two possible trees agree or disagree. There a number of different tree distances, which vary in what aspects of tree commonality they measure, their importance in different applications, and in their difficulty of calculation. This project seeks to better understand the distribution of multiple measures of distance on trees.This project studies both ordered trees, used in computational settings such as data and disk storage techniques, and unordered trees, arising in biological and other scientific studies. The statistical properties of the distribution, including averages, variance and asymptotic properties, present difficult challenges and will be approached both experimentally and via exact and asymptotic combinatorial methods. The project also works on new approaches to compute tree distances that are both important for phylogenetic applications and computationally feasible. Greater understanding of rotation operations used in tree balancing may lead to improved algorithms for trees used in broad classes of computation, underlying the efficiency of many large database structures. The project develops understanding of how to scale tree distances by understanding the distribution of distances, giving scientists studying biological questions better understanding for interpreting results of tree reconstruction efforts. The project involves undergraduate researchers in cutting-edge research projects, both in the development of large-scale computational experiments and in developing the theoretical foundations of the answers to these questions. This award by the Computational Mathematics Program of the Division of Mathematical Sciences is co-funded by the Biodiversity and Ecosystem Dynamics Program in the DEB Division of the BIO Directorate.