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

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