III: Small: Fast and Efficient Algorithms for Matrix Decompositions and Applications to Human Genetics

III：小：快速高效的矩阵分解算法及其在人类遗传学中的应用

• 批准号: 1319280
• 负责人: Petros Drineas
• 金额: $ 32.95万
• 依托单位: Rensselaer Polytechnic Institute
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-15 至 2016-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319280&HistoricalAwards=false
• 关键词: III; Small; Fast; Efficient; Algorithms

Linear algebraic algorithms, and in particular matrix decompositions, have proven extremely successful in the analysis of datasets in the form of matrices. Tools such as the Singular Value Decomposition (SVD) and the related Principal Components Analysis (PCA) have had a profound impact in diverse areas, ranging from web search engines to the physical sciences. Over the last decade, the introduction of randomization provided a new paradigm for the design and analysis of such algorithms. On the other hand, human genetics researchers are now finding out how truly different we are from one another. Large datasets describing the common patterns of human genetic variation may be easily thought of as matrices, with the rows representing individuals and the columns representing loci in the genome that correspond to common polymorphisms. The broader impact of such datasets can not be overemphasized: they are expected to be a key resource for researchers to use to find genes affecting health, disease, and responses to drugs and environmental factors, as well as understanding the evolutionary and biological history of our species. The main objective of this proposal is to bridge the gap between state-of-the-art algorithms for data analysis developed in the theoretical computer science and applied mathematics communities and the application of such algorithms to the analysis of the increasingly larger volume of datasets in the human genetics community. The particular focus of our proposal is, from an algorithmic perspective, the design and analysis of (supervised and unsupervised) randomized algorithms for the so-called CX matrix factorization, and, from a population genetics perspective, the selection of ancestry informative and disorder associated markers, as well as ancestry and affection status prediction. This work will have immediate impact in the analysis of population genetics data. The results will be disseminated to a broad community of applied mathematicians, theoretical computer scientists, and population geneticists

线性代数算法，特别是矩阵分解，在分析矩阵形式的数据集方面已经被证明是非常成功的。奇异值分解（SVD）和相关的主成分分析（PCA）等工具在从网络搜索引擎到物理科学的各个领域都产生了深远的影响。在过去的十年里，随机化的引入为这类算法的设计和分析提供了一个新的范例。另一方面，人类遗传学研究人员现在正在发现我们彼此之间的真正差异。描述人类遗传变异的共同模式的大型数据集可以很容易地被认为是矩阵，其中行代表个体，列代表基因组中与共同多态性相对应的位点。这些数据集的广泛影响怎么强调都不为过：它们有望成为研究人员用来寻找影响健康、疾病和对药物和环境因素的反应的基因，以及了解我们物种的进化和生物历史的关键资源。本提案的主要目标是弥合理论计算机科学和应用数学社区开发的最先进的数据分析算法与将这些算法应用于分析人类遗传学社区日益庞大的数据集之间的差距。从算法的角度来看，我们建议的重点是设计和分析（监督和无监督）随机算法，用于所谓的CX矩阵分解，从群体遗传学的角度来看，祖先信息和疾病相关标记的选择，以及祖先和情感状态预测。这项工作将对群体遗传学数据的分析产生直接影响。研究结果将被广泛传播给应用数学家、理论计算机科学家和群体遗传学家