Inference of Markovian Properties of Molecular Sequences Using Shotgun Reads and Applications

高通量下一代测序（NGS）技术产生了大量的片段化基因组序列，彻底改变了遗传学和基因组学研究。已经使用NGS对数千个个体基因组和宏基因组进行了测序，所述个体基因组和宏基因组由来自各种环境的个体生物体的天然混合物组成。这些发展在理解复杂疾病的遗传基础、环境对公共健康的影响、环境变化（如全球变暖和污染）对环境的影响以及包括病毒在内的病原体的检测方面发挥了重要作用。开发充分利用NGS数据的分析方法对于促进公共卫生、改善环境和加强国家安全至关重要。虽然在分析国家一般统计数据方面取得了重大进展，但在现有分析工具与通过分析国家一般统计数据可以实现的全部潜力之间仍存在很大差距。该研究项目旨在进一步推进最近开发的统计和计算方法，用于使用NGS读数比较基因组和宏基因组，而不需要组装成基因组，避免许多使组装成为问题的陷阱。这项研究将使计算工具更加有效和强大，并将利用它们来分析宏基因组数据，以研究环境因素对海洋微生物群落的影响。算法和结果都将通过网络传播。本研究的结果将对不同环境下的基因组学和宏基因组学研究具有重要意义。更详细地说，将开发基于NGS短读段的分子序列马尔可夫性质推断的统计和计算方法，然后将该方法用于研究个体基因组和宏基因组样本之间的关系。首先，将发展估计阶和转移概率矩阵及其渐近分布的方法。还将开发推断可变长度马尔可夫链（VLMC）的方法。第二，考虑到序列的马尔可夫链（MC）特性，新的无约束统计量将被开发用于研究基因组序列之间的关系。将开发用于选择单词长度的迭代方法。第三，从NGS读取衍生的马尔可夫链模型将用于识别宏基因组群落中的物种或菌株，并基于MC模型比较宏基因组样品。最后，将开发一套与基于NGS读数的MC推断以及基因组和宏基因组数据分析的应用相关的计算机算法。该项目的广泛影响包括基于NGS数据的基因组和宏基因组比较的计算工具，以及供公众使用的软件包，跨统计学和生物学多个学科的研究生和本科生培训，以及K-12教师和学生的外联讲座。

High throughput next generation sequencing (NGS) technologies generate enormous amounts of fragmented genome sequences, revolutionizing genetic and genomics research. Thousands of individual genomes and metagenomes consisting of natural mixtures of individual organisms from various environments have been sequenced using NGS. These developments play essential roles in understanding the genetic basis of complex diseases, the effects of environment on public health, the impacts of environmental changes such as global warming and pollution on the environments, and the detection of pathogens including viruses. Development of analytical methods to make full use of NGS data is essential in advancing public health, improving the environment, and strengthening national security. Although significant progress has been made in the analysis of NGS data, there are still wide gaps between the current available analytical tools and the full potential that can be achieved through the analysis of NGS data. This research project aims to further advance recently-developed statistical and computational methods for the comparison of genomes and metagenomes using NGS reads, without the need for assembly into genomes, avoiding many pitfalls that make assembly problematic. The research will make the computational tools more efficient and powerful and will employ them to analyze metagenomic data to study the effects of environmental factors on marine microbial communities. Both the algorithms and results will be disseminated through the web. The results from this study will be important for both genomics and metagenomics studies under a variety of environments.In more detail, statistical and computational methods for the inference of Markovian properties of molecular sequences based on NGS short reads will be developed and the methods will then be used to study the relationships among individual genomes and metagenomic samples. Firstly, methods to estimate the order and the transition probability matrix and their asymptotic distributions will be developed. Methods to infer variable length Markov chains (VLMC) will also be developed. Secondly, new alignment-free statistics taking into account the Markov chain (MC) properties of the sequences will be developed to study the relationships among genome sequences. Iterative approaches for choosing the word length will be developed. Thirdly, Markov chain models derived from NGS reads will be used to identify species or strains in metagenomic communities and to compare metagenomic samples based on the MC models. Finally, a suite of computer algorithms related to the inference of MCs based on NGS reads and applications to genome and metagenomic data analysis will be developed. The broad impacts of the project include computational tools for genome and metagenome comparison based on NGS data together with software packages for public usage, graduate and undergraduate training across multiple disciplines of statistics and biology, and outreach lectures for K-12 teachers and students.