COMPUTATIONAL METHODS FOR MICROBIAL NEXT GENERATION RE-SEQUENCING DATA

过去或现在存在的绝大多数生命（统称为微生物或微生物）是肉眼看不见的，包括病毒在内，形成了庞大而复杂的群落。描述这些群落中存在的物种特征、基因组组成和遗传变异一直是“宏基因组学”的主要焦点，“宏基因组学”是对来自环境、动物或人类的混合样本进行基因组研究，例如，来自动物肠道或土壤微生物生态系统。当代测序技术（下一代测序，NGS）已经大规模并行化了遗传物质中核苷酸顺序的测定，从而使我们能够快速对不同微生物进行测序。这带来了前所未有的规模探索微生物群落和遗传多样性的潜力。计算方法在NGS数据的分析、校准和组装中起着核心作用。然而，产生的数据量超出了我们常规分析的能力，更不用说进行适当的比较分析了。软件的缺乏是因为大多数研究工作都是针对从下一代序列数据中组装单个完整基因组。然而，对于微生物，“超深”测序揭示了许多有趣的问题，涉及群落中存在的序列多样性和种群变异。新兴的方法旨在以类似拼图游戏的方式构建NGS reads的从头组装（每个read是对应于基因组区域的单个序列片段），其中将所有匹配的片段连接在一起构建图像。在从头组装中，基因组序列是通过将匹配的短片段分配在一起来构建的。大多数现有的NGS数据从头组装方法都广泛使用了de Bruijn图方法。然而，为非常大的NGS数据集构建de Bruijn图是非常苛刻的，因为它们需要大量的计算资源。在这个项目中，我们建议开发新的计算方法，通过将单个NGS读数重新转换为数字序列（并直接处理这些转换/压缩的数据）来压缩它们，这将对所有类型的微生物数据集普遍有用。为了做到这一点，我们将探索用图形表示短读序列数据的新方法，并应用已建立的数学方法进行有效的数据挖掘。我们将解决的特殊问题是NGS数据集的组装，在分析中需要考虑样本的变化。在宏基因组学数据中，读数之间的差异既对应于不同的微生物物种，也对应于单个物种或病毒种群内的差异。一个特别重要的焦点是在没有参考序列的情况下组装基因组的能力（从头组装），因为许多微生物通常无法获得适当的参考基因组，即使有参考序列，基因组结构在一个物种内也可能有所不同。

The overwhelming majority of life that has existed or exists is invisible to the naked eye (collectively termed the microbes, or microorganisms) and, including the viruses, forms large and complex communities. Characterising the species present, genome composition and genetic variation in these communities has been a major focus of 'metagenomics', the genomic study of mixed samples from the environment, or from animals or humans, for example, from an animal's gut or a soil microbial ecosystems. Contemporary sequencing technologies (next generation sequencing, NGS) have massively parallelized the determination of nucleotide order within genetic material resulting in our ability to rapidly sequence different microbes. This introduces the potential to explore microbial communities and genetic diversity on a scale that was previously unprecedented. Computational methods play a central role in the analysis, alignment and assembly of NGS data. However, the amount of data being generated is outstripping our ability to analyse them routinely, let alone carry out appropriate comparative analysis. This lack of software arises because most research effort is being directed at assembling single complete genomes from next generation sequence data. However, with microbes many interesting questions concern the diversity of sequences present in a community and population variation, revealed by 'ultra-deep' sequencing. Emerging approaches aim to build a de novo assembly of the NGS reads (each read is an individual sequence fragment corresponding to a region of a genome) in a similar fashion to a jigsaw puzzle where a picture is constructed by joining all the matching pieces together. In de novo assembly the genome sequence is constructed by allocating matching short reads together. The majority of the existing de novo assembly approaches for NGS data make extensive use of the de Bruijn graph method. However, building de Bruijn graphs for very large NGS data sets is very demanding because they require hefty computational resources. In this project we propose to develop novel computational methods, based on compressing the individual NGS reads by recasting them as numerical sequences (and working with this transformed/compressed data directly) that will be generically useful for all types of microbial data sets. In order to do this we will explore novel methods for representing short-read sequence data graphically and apply established mathematical approaches for efficient data mining. The particular problem we will address is the assembly of NGS data sets where the variation in the sample needs to be considered in the analysis. In metagenomics data variation between reads corresponds to both distinct microbial species and variation within individual species or viral populations. A particularly important focus is the ability to assembly a genome without a reference sequence for comparison (de novo assembly) as an appropriate reference genome is frequently not available for many microbes and, even when a reference is available, genome architecture can vary within a species.