AF: Small: Fast and accurate computational tools for large-scale evolutionary inference: a phylogenetic network approach

AF：小型：用于大规模进化推理的快速准确的计算工具：系统发育网络方法

• 批准号: 1714417
• 负责人: Kevin Liu
• 金额: $ 40.47万
• 依托单位: Michigan State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2017
• 资助国家: 美国
• 起止时间: 2017-08-15 至 2021-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1714417&HistoricalAwards=false
• 关键词: AF; Small; Fast; accurate; computational

A grand challenge in science is reconstructing the "Tree of Life", which is the phylogeny, or evolutionary history, of all species on Earth. The notion of a Tree of Life reflects Darwin's view of evolution as "tree-like", where bifurcating speciation results in an ancestral species giving rise to two genetically isolated descendant species. However, recent studies have challenged this view. "Non-tree-like" evolution due to inter-species gene flow - where DNA is shared between species existing at the same time - has significantly shaped the evolution of a far greater diversity of species than was ever thought possible, including humans and Neandertal, mice, and butterflies. In these cases, the phylogeny cannot be described by a tree, but is instead a more general structure known as a phylogenetic network. Our understanding of evolution and biology is at a crossroads. How frequently is the traditional assumption of tree-like evolution violated in the Tree of Life? What is the evolutionary role of gene flow? Applications include understanding the spread of antibiotic resistance among bacteria, which costs the U.S. over $35 billion and a loss of 23,000 lives annually, and pesticide resistance in weeds, mice, and other pests, which costs the U.S. billions of dollars annually. Phylogenetics, or the discipline which seeks to reconstruct evolutionary histories using biomolecular sequences and other biological data, can shed new light into these questions. Two ingredients are necessary for phylogenetic reconstruction and analysis: suitable biological data for the organisms under study, and computational methods capable of efficiently and accurately analyzing the data. Today, biological data abounds due to recent biotechnological advances, and large-scale datasets are common. However, computational methods have not kept pace. New computational frameworks are needed for fast and accurate phylogenetic network inference and analysis in the era of "big data". To address these challenges, this project will create new computational frameworks for fast and accurate network-based phylogenetic inference using large-scale genomic sequence datasets and evolutionary analysis of continuous biological data. The new methodologies will be validated using a comprehensive performance study. More broadly, this project will enable student training, scientific outreach, open-source software development, and scientific research that may yield new biological and biomedical discoveries.Phylogenies are typically inferred using computational analysis of biomolecular sequence data, and phylogenetic comparative methods are used for evolutionary analysis of continuous biological data (e.g., trait data). Today, "big data" challenges abound due to rapid advances in sequencing and related biotechnologies. In particular, large-scale datasets with hundreds of genomes are now common. The state of the art of phylogenetic inference therefore faces two critical scalability challenges: (1) the number of organisms in a study, and (2) greater evolutionary divergence reflecting the complex interplay of tree-like and non-tree-like evolution. For discrete sequence data, state-of-the-art methods address the second challenge, but are not scalable beyond inputs with a few dozen genomes; for continuous data, scalable approaches are needed to address the second challenge in the context of phylogenetic uncertainty and adaptive evolution. The proposed research creates new computational approaches that address both challenges for discrete sequence data and continuous data. The first objective is to create a novel computational framework for scalable phylogenetic network inference using large-scale genomic sequence data. The framework makes use of the multi-species network coalescent model to account for genetic drift, incomplete lineage sorting, and gene flow as well as traditional substitution-based models of sequence evolution. The framework builds on the PI's work on large-scale phylogenetic tree inference by adapting divide-and-conquer algorithms to the more general case of networks, resulting in accurate and efficient inference. The second objective is to develop novel stochastic models and methods for analyzing continuous character evolution on phylogenetic networks. The new models will generalize widely-used non-neutral models of continuous character evolution that assume tree-like evolution, and will be used to create new methods for phylogenetic inference using heterogeneous large-scale inputs. The third objective is to validate the new computational methodologies using new empirical and synthetic benchmarks. The empirical benchmarks include mouse, plant, and fungal datasets that have been produced through ongoing collaborations.

科学的一个重大挑战是重建“生命之树”，这是地球上所有物种的繁衍史或进化史。"生命之树“的概念反映了达尔文的进化“树状”观点，即物种分化导致一个祖先物种产生两个遗传上隔离的后代物种。然而，最近的研究挑战了这一观点。由于物种间的基因流动（DNA在同时存在的物种之间共享）而导致的“非树状”进化显著地塑造了物种多样性的进化，其多样性远远超过以往任何时候的想象，包括人类和尼安德特人，老鼠和蝴蝶。在这些情况下，系统发育不能用树来描述，而是一个更一般的结构，称为系统发育网络。我们对进化和生物学的理解正处于十字路口。在《生命之树》中，有多少次违背了树状进化的传统假设？基因流在进化中的作用是什么？应用包括了解细菌中抗生素耐药性的传播，这使美国每年损失超过350亿美元，并造成23，000人死亡，以及杂草，老鼠和其他害虫的杀虫剂耐药性，这使美国每年损失数十亿美元。系统发生学，或试图利用生物分子序列和其他生物数据重建进化历史的学科，可以为这些问题提供新的线索。系统发育重建和分析需要两个要素：所研究的生物体的合适的生物学数据，以及能够有效和准确地分析数据的计算方法。今天，由于最近的生物技术进步，生物数据丰富，大规模数据集很常见。然而，计算方法没有跟上步伐。在“大数据”时代，需要新的计算框架来进行快速准确的系统发育网络推断和分析。为了应对这些挑战，该项目将使用大规模基因组序列数据集和连续生物数据的进化分析创建新的计算框架，用于快速准确的基于网络的系统发育推断。将利用一项全面的业绩研究来验证新的方法。更广泛地说，该项目将使学生培训，科学推广，开源软件开发和科学研究，可能产生新的生物和生物医学发现。系统发育通常使用生物分子序列数据的计算分析来推断，系统发育比较方法用于连续生物数据的进化分析（例如，性状数据）。今天，由于测序和相关生物技术的快速发展，“大数据”挑战比比皆是。特别是，具有数百个基因组的大规模数据集现在很常见。因此，系统发育推断的最新技术面临两个关键的可扩展性挑战：（1）研究中的生物体数量，以及（2）更大的进化分歧，反映了树状和非树状进化的复杂相互作用。对于离散序列数据，最先进的方法解决了第二个挑战，但不能扩展到几十个基因组的输入之外;对于连续数据，需要可扩展的方法来解决系统发育不确定性和适应性进化背景下的第二个挑战。拟议的研究创造了新的计算方法，解决了离散序列数据和连续数据的挑战。第一个目标是使用大规模基因组序列数据创建一个新的可扩展系统发育网络推理的计算框架。该框架利用多物种网络结合模型来解释遗传漂变、不完全谱系排序和基因流以及传统的基于替代的序列进化模型。该框架建立在PI在大规模系统发育树推理方面的工作基础上，通过将分治算法适应于更一般的网络情况，从而实现准确和高效的推理。第二个目标是开发新的随机模型和方法，用于分析系统发育网络上的连续字符进化。新的模型将推广广泛使用的非中性模型的连续字符进化，假设树状进化，并将用于创建新的方法，系统发育推断使用异构的大规模输入。第三个目标是使用新的经验和合成基准来验证新的计算方法。经验基准包括通过持续合作产生的小鼠，植物和真菌数据集。

项目成果

Statistical analysis of GC-biased gene conversion and recombination hotspots in eukaryotic genomes: a phylogenetic hidden Markov model-based approach

真核基因组中GC偏向基因转换和重组热点的统计分析：基于系统发育隐马尔可夫模型的方法

• DOI: 10.1145/3459930.3469509
• 发表时间: 2021
• 期刊: Proceedings of ACM BCB 2021
• 作者: Gao, Meijun;Liu, Kevin J.
• 通讯作者: Liu, Kevin J.

Coal-Miner: A Statistical Method for GWA Studies of Quantitative Traits with Complex Evolutionary Origins

• DOI: 10.1145/3107411.3107490
• 发表时间: 2017-08
• 期刊: Proceedings of the 8th ACM International Conference on Bioinformatics, Computational Biology,and Health Informatics
• 作者: Hussein A. Hejase;N. V. Pol;G. Bonito;P. Edger;Kevin J. Liu

Non-parametric and semi-parametric support estimation using SEquential RESampling random walks on biomolecular sequences

使用生物分子序列上的 SEequential RESampling 随机游走进行非参数和半参数支持估计

• DOI: 10.1186/s13015-020-00167-0
• 发表时间: 2020
• 期刊: Algorithms for Molecular Biology
• 影响因子: 1
• 作者: Wang, Wei;Smith, Jack;Hejase, Hussein A.;Liu, Kevin J.
• 通讯作者: Liu, Kevin J.

An Application of Random Walk Resampling to Phylogenetic HMM Inference and Learning

随机游走重采样在系统发育 HMM 推理和学习中的应用

• DOI: 10.1109/tnb.2020.2991302
• 发表时间: 2020
• 期刊: IEEE Transactions on NanoBioscience
• 影响因子: 3.9
• 作者: Wang, Wei;Wuyun, Qiqige;Liu, Kevin J.
• 通讯作者: Liu, Kevin J.

Scalable Statistical Introgression Mapping Using Approximate Coalescent-Based Inference

使用基于近似合并的推理的可扩展统计渗入映射

• DOI: 10.1145/3307339.3343352
• 发表时间: 2019
• 期刊: Computational Biology and Health Informatics
• 作者: Wuyun, Qiqige;VanKuren, Nicholas W.;Kronforst, Marcus;Mullen, Sean P.;Liu, Kevin J.
• 通讯作者: Liu, Kevin J.