CAREER: Algorithms for Domain-Level Analysis of Gene Family Evolution

生物体的基因组有助于确定其生物学特性。了解不同的基因如何进化和获得新的功能是一个基本的生物学问题，许多计算方法被用来研究基因家族如何随着时间的推移在不同的生物体中进化和变化。这些现有的方法假设基因是进化的基本单位，基因复制、基因丢失和水平基因转移等进化过程作用于整个基因，而不是部分基因。众所周知，大多数基因由一个或多个蛋白质结构域组成，这些结构域特征明确的功能单元可以在进化过程中独立地丢失或获得，而结构域改组是基因进化和获得新功能的主要机制之一。因此，对区域水平的进化事件进行适当的推断和解释对于理解基因如何进化和功能至关重要。拟议的研究将为解决这一关键问题的新的计算框架奠定方法论和算法基础。新的计算框架和算法将使更强大的比较基因组技术能够理解基因功能和生物学，并可能有助于改善人类健康和农业。拟议的研究将在未来许多年内塑造区域、基因和基因组进化研究的未来计算进展，并将推动在分子进化的其他领域开发更全面的计算模型。作为这项研究的一部分开发的算法将被实施到一个用户友好的软件包中，并免费提供。该项目将直接涉及两名研究生和最多十名本科生，向几名高中生介绍计算机科学、生物信息学和研究，并向许多高中科学教师提供关于计算机科学在生物学中的作用的培训。该项目将导致开发第一个域进化的“三叉树”模型，该模型明确地捕捉域、基因和物种级别进化的相互依赖。所提出的三叉树计算框架基于系统发育协调，其中的目标是找到给定基因树与物种树以及给定域树与基因树的最简约联合协调。由此产生的优化问题将使用各种算法技术来解决，包括动态编程、分支和界限、枚举和抽样以及局部搜索。该框架将领域级事件与基因级事件分离，并提供更准确且更易于解释的基因家族和领域家族进化的细粒度视图。具体目标包括：(I)开发三叉树计算框架和相应的算法，(Ii)通过考虑多重最优和域树错误来提高推理精度，以及(Iii)通过允许水平基因转移将三叉树框架扩展到微生物基因家族。

The genome of an organism helps to determine its biology. Understanding how different genes evolve and acquire new functions is a fundamental biological problem with many computational methods developed for studying how gene families evolve and change over time in different organisms. These existing methods assume that the gene is the basic unit of evolution and that evolutionary processes such as gene duplication, gene loss, and horizontal gene transfer act on entire genes, rather than on parts of genes. It is well known that most genes consist of one or more "protein domains," well-characterized functional units that can be independently lost or gained during evolution, and that domain shuffling is one of the primary mechanisms through which genes evolve and gain new functions. Proper inference and accounting of domain-level evolutionary events is therefore crucial to understanding how genes evolve and function. The proposed research will lay the methodological and algorithmic foundations for a novel computational framework that addresses this critical problem. The new computational framework and algorithms will enable more powerful comparative genomic techniques for understanding gene function and biology, and may also contribute to improvements in human health and agriculture. The proposed research will shape future computational advances in the study of domain, gene, and genome evolution for many years to come, and will also spur the development of more comprehensive computational models in other areas of molecular evolution. The algorithms developed as part of this research will be implemented into a user-friendly software package and made freely available. The project will directly involve two graduate and up to ten undergraduate students, introduce several high-school students to computer science, bioinformatics, and research, and provide training to many high-school science teachers on the role of computer science in biology. This project will lead to the development of the first "three-tree" model of domain evolution that explicitly captures the interdependence of domain-, gene-, and species-level evolution. The proposed three-tree computational framework is based on phylogenetic reconciliation, where the goal is to find a most parsimonious joint reconciliation of the given gene trees with the species tree and of the given domain trees with the gene trees. The resulting optimization problems will be solved using various algorithmic techniques including dynamic programming, branch and bound, enumeration and sampling, and local search. The framework will decouple domain-level events from gene-level events and provide a fine-grained view of gene family and domain family evolution that is both more accurate and much easier to interpret. Specific aims include: (i) development of the three-tree computational framework and corresponding algorithms, (ii) enhancing inference accuracy by accounting for multiple optima and domain tree errors, and (iii) extension of the three-tree framework to microbial gene families by allowing for horizontal gene transfer.