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

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

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.