BIGDATA: F: Metric-space Positioning Systems for Symbolic Data Science

下一代DNA测序技术产生的数据集是“大数据”的缩影。结果文件通常相当大，几乎完全由符号（即非数字）短DNA序列组成。相比之下，最广泛使用的机器学习算法需要数值数据集来学习。不幸的是，无论是传统的还是先进的数字表示符号数据的方法，都经常受到高维或大量运行时间要求的影响，这阻碍了强大的机器学习算法在现代生物学问题上的应用。为了克服这些关键问题，本项目解决了确定“正确”维度的基本问题，在该维度中嵌入用于数据挖掘或分类任务的符号数据。它通过一种让人想起全球定位系统（GPS）的方法，用数字表示符号数据集，但在更一般的环境中实现了这一点。除了探索现代生物学的应用之外，该项目还将研究如何在大型网络中预测传播的来源（即“归零点”）。这可能有助于管理员确定如何最好地应对新的流行病和网络威胁。此外，该项目将密切指导本科生和研究生成为成熟的数据科学家。其研究结果将以笔记、开源软件和视频讲座的形式传播给公众，包括科罗拉多数据科学团队的学生，该团队鼓励女性和代表性不足的少数民族参与工程教育。就像GPS使用三边测量来定位地球上任何地方的接收器一样，有限度量空间包含解析集，即通过多边测量唯一识别空间中每个点的点集（即集合中点的距离向量）。与任何解析集R相关联，存在从其周围度量空间到维数为|R|的欧氏空间的一对一变换，即R的基数。因此，最小的解析集归纳出其周围空间的最低维表示。重要的是，即使当环境度量空间有限但呈指数级大时，其度量维度通常比其基数小得多。然而，在各种情况下，确定度量维度是一个np困难问题。基于这个抽象的乘法概念，本项目将：(1)评估计算汉明图度量维的计算复杂性，并描述各种随机图模型的度量维，以指导开发新的高效算法来近似该数量；(2)探索乘法的松弛和约束，包括近似和概率算法，以将乘法的应用范围扩展到其他有限但大的度量空间；最后(3)提供多重增殖的概念证明，以学习基因组序列中不相邻的依赖区域，为历史上难以捉摸的病毒目标开发分类器，并确定信息或疾病在大型网络中的传播来源。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Next-generation DNA sequencing technologies produce datasets that are the epitome of "big data." Resulting files are typically quite large, consisting almost entirely of symbolic (i.e., non-numeric) short DNA sequences. In contrast, the most widely used machine learning algorithms require numerical datasets to learn. Unfortunately, both traditional and cutting-edge methods to numerically represent symbolic data often suffer from high-dimensionality or substantial running time requirements, which hinder the application of powerful machine learning algorithms to modern biological questions. To overcome these crucial issues, this project addresses the fundamental problem of determining the "right" dimension in which to embed symbolic data for a data-mining or classification task. It does so by representing symbolic datasets numerically via a method reminiscent of Global Positioning Systems (GPS) but in a far more general setting. Besides exploring modern biology applications, the project will also investigate how to predict the source of a spread (i.e., ground zero) over large networks. This may assist administrators in determining how best to respond to new epidemics and cyber-threats. Additionally, the project will closely mentor undergraduate and graduate students to become mature data scientists. Its findings will be communicated as notes, open-source software, and video-lectures available to the general public, including students in the Colorado Data Science Team, which encourages the participation of women and under-represented minorities in Engineering education.Much like GPS uses trilateration to locate a receiver anywhere on the planet, finite metric spaces contain resolving sets, that is sets of points that uniquely identify every point in the space via multilateration (i.e., the vector of distances to points in the set). Associated with any resolving set R, there is a one-to-one transformation from its ambient metric space to a Euclidean space of dimension |R|, the cardinality of R. The smallest resolving set thus induces the lowest-dimensional representation of its ambient space. Importantly, even when the ambient metric space is finite but exponentially large, its metric dimension is often much smaller than its cardinality. Determining the metric dimension is, however, an NP-hard problem in a variety of contexts. Building on this abstracted notion of multilateration, this project will: (1) assess the computational complexity of calculating the metric dimension of Hamming graphs, and characterize the metric dimension of various random graph models to guide the development of new and efficient algorithms to approximate this quantity; (2) explore relaxations and constraints of multilateration, including approximate and probabilistic algorithms, to expand the reach of applications of multilateration to other finite but large metric spaces; and finally (3) provide proofs-of-concept of multilateration to learn non-contiguous regions of dependencies in genomic sequences, develop classifiers for historically elusive virus targets, and identify the source of spread of information or disease in large networks.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.