III: Small: Bit-Parallel Algorithms for Sequence Alignment and Applications in Detecting Human Genetic Variation and Bacterial Strain Typing

III：小：序列比对的位并行算法及其在检测人类遗传变异和细菌菌株分型中的应用

• 批准号: 1423022
• 负责人: Gary Benson
• 金额: $ 56.08万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-10-01 至 2019-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423022&HistoricalAwards=false
• 关键词: III; Small; Bit; Parallel; Algorithms

This project underscores the close link between the ability to do high throughput sequencing and the wide range of applications that are critical to understanding the biological world. Data analysis is the bottleneck in sequences. This project will lead to new efficiencies in sequence comparison and will lead to a new compendium of genetic variation. This work will provide support for both graduate students and undergraduate students, the latter especially through a new site the PI has established to recruit students from underrepresented groups. The BitPal algorithms will be widely distributed and facility sequence alignment in a variety of areas. The work also directly enhances the infrastructure for research in genomics, while the new protocol will facilitate the epidemiological study of pathogenic infections and analysis of biothreat agents. The deluge of genomic sequence data has outpaced the growing speed of modern computers. For sequence analysis programs, such as VNTRseek, to keep pace with data growth, extremely high efficiency algorithms are required. This project will develop a novel class of bit-parallel alignment algorithms which exploit the inherent parallelism in computer logic operations and will yield dramatic acceleration of sequence comparison tasks. The project will achieve the following: A variety of multi-purpose, high-efficiency bit-parallel alignment algorithms will be designed and implemented for CPU and GPU (graphical processing unit) architectures. A website will be created for easy download and use of the computer code implementing the algorithms. The bit-parallel techniques to be developed are novel and represent an extension of a successful method to a larger class of problems. The algorithms will be widely applicable in bioinformatics and other fields that involve text comparison. Implementation in GPUs will expand the domain of this underutilized computing architecture. The bit-parallel algorithms will be used to replace less efficient algorithms in VNTRseek and TRF, in order to accelerate the analysis of large data sets. Initial analysis will identify VNTRs in 380 human genomes (moderate to high coverage) from the 1000 Genomes Project. Additional genomes will be analyzed as they become available. An online database will be created to store the VNTR data and provide online tools for VNTR analysis. Genome wide occurrence of VNTRs is currently unknown. The VNTRseek analysis of human genomes will result in an entirely new compendium of human genetic variation. A bacterial strain typing protocol will be developed for pathogenic bacteria, based on multilocus VNTR analysis (MLVA), using high-throughput sequencing data as an alternative to slower techniques. This will facilitate the epidemiological study of pathogenic bacterial infrections and the analysis of biothreat agents for national security.

该项目强调了高通量测序能力与对理解生物世界至关重要的广泛应用之间的密切联系。 数据分析是测序的瓶颈。 该项目将导致新的效率在序列比较，并将导致一个新的简编的遗传变异。这项工作将为研究生和本科生提供支持，后者特别是通过PI建立的新网站从代表性不足的群体中招募学生。 Bitmap算法将广泛分布，并在各个领域进行序列比对。 这项工作还直接加强了基因组学研究的基础设施，而新的协议将促进病原体感染的流行病学研究和生物威胁剂的分析。 基因组序列数据的泛滥已经超过了现代计算机的增长速度。对于序列分析程序，如VNTRseek，为了跟上数据增长的步伐，需要极高效率的算法。这个项目将开发一类新的位并行对齐算法，利用计算机逻辑操作中固有的并行性，并将产生显着的加速序列比较任务。 该项目将实现以下目标：将为CPU和GPU（图形处理单元）架构设计和实现各种多用途，高效率的位并行对齐算法。将创建一个网站，方便下载和使用实现算法的计算机代码。要开发的位并行技术是新颖的，代表了一个成功的方法扩展到更大的一类问题。该算法在生物信息学等涉及文本比较的领域具有广泛的应用前景。在GPU中的实现将扩展这种未充分利用的计算架构的领域。位并行算法将被用来取代VNTRseek和TRF中效率较低的算法，以加速大型数据集的分析。初步分析将确定来自1000个基因组计划的380个人类基因组中的VNTR（中到高覆盖率）。其他基因组将在可用时进行分析。将建立一个在线数据库来存储VNTR数据，并为VNTR分析提供在线工具。VNTR的全基因组发生率目前尚不清楚。对人类基因组的VNTRseek分析将产生一个全新的人类遗传变异纲要。将基于多位点VNTR分析（MLVA），使用高通量测序数据作为较慢技术的替代方案，为致病菌开发细菌菌株分型方案。这将有助于病原性细菌感染的流行病学研究和国家安全生物威胁剂的分析。