SHF: Small: Collaborative Research: The Automata Programming Paradigm for Genomic Analysis

SHF：小型：协作研究：基因组分析的自动机编程范式

• 批准号: 1421765
• 负责人: Michela Becchi
• 金额: $ 34.82万
• 依托单位: University of Missouri-Columbia
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1421765&HistoricalAwards=false
• 关键词: SHF; Small; Collaborative; Research; Automata

Inferring knowledge from genetic data will drive future advances in the life sciences. However, DNA sequences are being generated faster than they can be analyzed with existing computing technologies and algorithms. The core computations performed by many genomic applications involve pattern matching. This operation is normally implemented using automata-based algorithms and can be efficiently mapped onto non-general purpose platforms such as Field Programmable Gate Arrays (FPGA) and Micron?s recently announced Automata Processor (AP). However, the lack of high-level programming interfaces for these devices hampers their adoption in the bioinformatics community.This project fills this gap by developing novel programmatic descriptions of several genomic analyses and mapping them onto these two non-traditional architectures. The work advances the state-of-the-art in several ways. At an algorithmic level, new methods to address the biological problems of genome-scale orthology inference and regulatory motif search are being developed. At a computational abstraction level, the researchers are designing an extended finite automaton abstraction suitable to support diverse computations, and are mapping new and existing computational kernels onto it. At a hardware mapping level, automatic tuning techniques for the effective deployment of automata-based computations on FPGA and Micron?s AP are being developed. This interdisciplinary project will facilitate the adoption of FPGA and Micron?s Automata Processor by biologists by providing a new library of pattern matching routines and a high-level automata-based programming interface for these platforms. In addition, the researchers are developing instructional material in a variety of topics, such as genomic analysis, pattern matching, automata processing and high-performance computing. Finally, this project provides research opportunities and access to pre-production hardware to undergraduate and graduate students, interdisciplinary training, and technology transfer to industry. The results of this research will be made available through the release of software tools and publication in international conferences and journals.

从基因数据推断知识将推动未来生命科学的进步。然而，DNA序列的生成速度比现有计算技术和算法无法分析的速度更快。许多基因组应用程序执行的核心计算涉及模式匹配。这种操作通常使用基于自动机的算法来实现，并且可以有效地映射到非通用平台上，例如现场可编程门阵列和美光S最近推出的自动机处理器(AP)。然而，这些设备缺乏高级编程接口，阻碍了它们在生物信息学社区的采用。该项目通过开发几个基因组分析的新颖编程描述并将它们映射到这两个非传统架构来填补这一空白。这项工作在几个方面推进了最先进的技术。在算法层面上，正在开发新的方法来解决基因组规模的正交学推断和调控基序搜索的生物学问题。在计算抽象层面，研究人员正在设计一种扩展的有限自动机抽象，适合于支持不同的计算，并将新的和现有的计算内核映射到它上。在硬件映射层面，正在开发自动调整技术，以便在现场可编程门阵列和美光S AP上有效地部署基于自动机的计算。这个跨学科项目将为生物学家提供一个新的模式匹配例程程序库和一个基于高级自动机的编程接口，从而促进生物学家采用现场可编程门阵列和美光S自动机处理器。此外，研究人员正在开发各种主题的教学材料，如基因组分析、模式匹配、自动机处理和高性能计算。最后，该项目为本科生和研究生提供了研究机会和前期生产硬件，提供了跨学科培训，并向行业转移了技术。这项研究的结果将通过发布软件工具和在国际会议和期刊上发表来公布。