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

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

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.