III:Small:Algorithms for Tandem Repeat Variant Discovery Using Next Generation Sequencing Data

III:Small：使用下一代测序数据发现串联重复变异的算法

• 批准号: 1017621
• 负责人: Gary Benson
• 金额: $ 50万
• 依托单位: Trustees of Boston University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-08-15 至 2015-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1017621&HistoricalAwards=false
• 关键词: III; Small; Algorithms; Tandem; Repeat

A tandem repeat (TR) is any pattern of nucleotides which occurs as repeating, consecutive copies along a DNA molecule. Often, the pattern copies are not identical. A TR can be polymorphic, that is, it can be different across individuals in a population: 1) the number of copies may be different, 2) the arrangement of non-identical copies may be dfferent, and 3) the copies may contain different small mutations. TR variants are known to affect important biological processes, such as chromatin structure, gene plasticity, gene expression, and disease states, so their discovery is crucial for correctly understanding complex bio-molecular interactions. While a conservative estimate suggests that 100,000 human TRs may be polymorphic, until recently, genome-wide study of TR polymorphism, in humans and other organisms, has been too difficult and costly, with the result that the true extent of polymorphism and its effects are unknown. New genome sequencing technologies offer the first real opportunity to fill in the details of TR diversity. These technologies sequence millions of high quality, short DNA fragments in a singleexperiment. Current sequencing projects are producing many billions of reads rich in TR variant information. Yet, current read mapping algorithms,which attempt to assign each read to its proper location on the reference genome, are not designed to detect TR variants. This project has three central goals: 1. Algorithm Development; 2.Genome Studies; 3. Variation Curation in a public database. Strategies will be developed to accurately and efficiently map TR-containing reads to reference genome TR loci. Anticipated algorithmic developments include: 1) Optimization of tree-based alignment, for use when millions of short, disjoint sequences must be aligned to each other. The reads and references can each be merged into separate Patricia tree data structures and alignment computed between tree nodes, thereby eliminating redundant computation in the prefixes of the two sequence sets. 2) Production of space-saving, Burrows Wheeler transforms (BWT) of the most redundant tree parts by employing approximate shortest common superstrings (SCS) for the two sequence sets. 3) Development of an efficient Four-Russians style block computation for edit distance alignment in the trees by exploiting redundancy inherent in the small alphabet and block input scores, 4) Development of a bounding computation for edit-distance based on efficient, bit-register computation of longest common subsequence (LCS) alignment, and 5) Parallelization of all algorithms for further efficiency with multi-core processors, Single Instruction, Multiple Data (SIMD) bit-register computations, and highly parallel graphics processing units (GPUs). Data from six recently published whole human genomes, two human centenarian genomes, and the 1000 genomes project will be analyzed to discover TR variants. An internet-accessible, public database and analysis platform for curation and display of TR variants will be developed.The TR variant discovery software and all data sets produced will directly enhance the infrastructure for TR diversity research in genome biology, genome evolution, and comparative genomics. The software and data will be freely available to the research community through a high capacity website maintained in the PI's lab at Boston University. The PI will participate in a variety of activities that link research and education and support participation by members of underrepresented groups, including provision of opportunities in research for graduate and undergraduate students, participation in high school enrichment and curriculum development projects, and editorship of an international journal engaged in the dissemination of bioinformatics research.

串联重复（TR）是核苷酸的任何模式，它沿着DNA分子重复，连续复制。通常，模式副本是不相同的。一个TR可以是多态的，也就是说，它在一个群体中的个体之间可能是不同的：1)拷贝的数量可能不同，2)非相同拷贝的排列可能不同，3)拷贝可能包含不同的小突变。已知TR变异会影响重要的生物过程，如染色质结构、基因可塑性、基因表达和疾病状态，因此它们的发现对于正确理解复杂的生物分子相互作用至关重要。尽管保守估计有10万个人类TR可能是多态性的，但直到最近，在人类和其他生物体中对TR多态性进行全基因组研究过于困难和昂贵，其结果是多态性的真正程度及其影响是未知的。新的基因组测序技术提供了第一个真正的机会来填补TR多样性的细节。这些技术在一次实验中对数百万个高质量的短DNA片段进行测序。目前的测序项目正在产生数十亿个富含TR变异信息的reads。然而，目前的读取映射算法，试图将每个读取分配到参考基因组上的适当位置，并没有设计用于检测TR变异。这个项目有三个中心目标：1。算法开发;2.基因组研究;3. 公共数据库中的变异管理。将制定策略，以准确有效地将含有TR的reads映射到参考基因组的TR位点。预期的算法发展包括：1)优化基于树的对齐，用于数百万个短的，不相交的序列必须彼此对齐。读取和引用可以分别合并到单独的Patricia树数据结构中，并在树节点之间计算对齐，从而消除了两个序列集前缀中的冗余计算。2)为了节省空间，对两个序列集采用近似最短公共超弦（SCS）对最冗余树部分进行Burrows Wheeler变换（BWT）。3)通过利用小字母和块输入分数固有的冗余，开发了一种高效的四俄罗斯风格的块计算，用于树中的编辑距离对齐；4)开发了一种基于最长公共子序列（LCS）对齐的高效位寄存器计算的编辑距离边界计算；5)并行化所有算法，以提高多核处理器的效率，单指令，多数据（SIMD）位寄存器计算，以及高度并行图形处理单元（gpu）。将分析最近发表的6个人类全基因组、2个人类百岁老人基因组和1000个基因组计划的数据，以发现TR变异。将开发一个可访问互联网的公共数据库和分析平台，用于管理和显示TR变体。TR变异发现软件和所产生的所有数据集将直接增强基因组生物学、基因组进化和比较基因组学中TR多样性研究的基础设施。软件和数据将通过波士顿大学PI实验室维护的高容量网站免费提供给研究界。PI将参与将研究与教育联系起来的各种活动，并支持代表性不足的群体成员的参与，包括为研究生和本科生提供研究机会，参与高中充实和课程开发项目，以及编辑从事传播生物信息学研究的国际期刊。