Experimental and Theoretical Analyses of Tree Distance Distributions

树距离分布的实验和理论分析

• 批准号: 1417820
• 负责人: Sean Cleary
• 金额: $ 24万
• 依托单位: CUNY City College
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-01 至 2019-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1417820&HistoricalAwards=false
• 关键词: Experimental; Theoretical; Analyses; Tree; Distance

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.

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