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

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

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.