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

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

• 批准号: 1421059
• 负责人: Jason Bakos
• 金额: $ 17.3万
• 依托单位: University of South Carolina at Columbia
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2018-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1421059&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序列的生成速度比使用现有计算技术和算法分析它们的速度要快。许多基因组应用程序执行的核心计算涉及模式匹配。该操作通常使用基于自动机的算法来实现，并且可以有效地映射到非通用平台上，例如现场可编程门阵列（FPGA）和Micron？最近宣布推出Automata Processor（AP）。然而，缺乏高层次的编程接口，这些设备阻碍了他们在生物信息学community.This项目填补了这一空白，开发新的几个基因组分析的程序化描述和映射到这两个非传统的架构。这项工作在几个方面推进了最先进的技术。在算法层面上，正在开发新的方法来解决基因组规模的直系推理和调控基序搜索的生物学问题。在计算抽象级别，研究人员正在设计一个扩展的有限自动机抽象适合支持不同的计算，并映射到它的新的和现有的计算内核。在硬件映射级别，自动机为基础的计算在FPGA和美光的有效部署自动调整技术？的AP正在开发中。 这个跨学科的项目将促进通过FPGA和美光？的自动机处理器由生物学家通过提供一个新的模式匹配例程库和一个高层次的基于自动机的编程接口，这些平台。此外，研究人员正在开发各种主题的教学材料，如基因组分析，模式匹配，自动机处理和高性能计算。最后，该项目为本科生和研究生提供研究机会和预生产硬件，跨学科培训和技术转移到行业。这项研究的结果将通过发布软件工具和在国际会议和期刊上发表来提供。